키푸 퀀텀의 이스카이 퀀텀 최적화기로 시장 분할 문제를 해결하세요

참고

Qiskit Functions 는 IBM Quantum® Premium Plan, Flex 요금제 및 On-Prem ( IBM Quantum Platform API를 통해) 요금제 사용자에게만 제공되는 실험적 기능입니다. 프리뷰 릴리스 상태이며 변경될 수 있습니다.

예상 사용 시간: Heron r2 프로세서에서 20초. (참고: 이는 추정치일 뿐입니다. 런타임은 다를 수 있습니다.)

배경

이 튜토리얼에서는 키푸 퀀텀의 이스케이 양자 최적화 도구 [1] 를 사용하여 마켓 분할 문제를 해결하는 방법을 설명합니다. 시장 분할 문제는 정확한 수요 목표를 달성하기 위해 시장을 균형 잡힌 판매 지역으로 분할해야 하는 실제 리소스 할당 과제를 나타냅니다.

시장 분할 과제

시장 분할 문제는 리소스 할당에 있어 놀라울 정도로 간단하지만 계산상으로는 엄청난 도전 과제입니다. $m$ 제품을 $n$ 서로 다른 시장에서 판매하고 각 시장에서 특정 제품 묶음(행렬 $A$ 의 열로 표시됨)을 구매하는 회사가 있다고 가정해 보겠습니다. 비즈니스 목표는 이러한 시장을 두 개의 균형 잡힌 판매 지역으로 분할하여 각 지역이 모든 제품에 대한 총 수요의 정확히 절반을 받도록 하는 것입니다.

수학적 공식:

이진 할당 벡터 $x$ 를 구합니다:

$x_j = 1$ 지역 A에 시장 $j$ 할당
$x_j = 0$ $j$ 시장을 지역 B에 할당합니다
$Ax = b$ 제약 조건이 충족되어야 하며, 여기서 $b$ 은 목표 판매량(일반적으로 제품당 총 수요의 절반)을 나타냅니다

비용 함수:

이 문제를 해결하기 위해 제곱 제약 조건 위반을 최소화합니다:

$C(x) = ||Ax - b||^2 = \sum_{i=1}^{m} \left(\sum_{j=1}^{n} A_{ij}x_j - b_i\right)^2$

상황:

$A_{ij}$ 시장에서 $i$ 제품의 판매를 나타냅니다 $j$
$x_j \in \{0,1\}$ 는 마켓의 이진 할당입니다 $j$
$b_i$ 는 각 지역의 제품 $i$ 에 대한 목표 판매량입니다
모든 제약 조건이 충족되면 비용은 정확히 0이 됩니다

합계의 각 항은 특정 제품에 대한 목표 매출의 제곱 편차를 나타냅니다. 이 비용 함수를 확장하면 다음과 같은 결과를 얻을 수 있습니다:

$C(x) = x^T A^T A x - 2b^T A x + b^T b$

$b^T b$ 은 상수이므로 $C(x)$ 을 최소화하는 것은 이차함수 $x^T A^T A x - 2b^T A x$ 를 최소화하는 것과 같으며, 이는 정확히 QUBO(Quadratic Unconstrained Binary Optimization) 문제입니다.

계산 복잡성:

이 문제는 간단한 비즈니스 해석에도 불구하고 놀라운 계산 난해성을 보여줍니다:

소규모 실패 : 기존의 혼합 정수 프로그래밍 솔버는 1시간의 타임아웃 [4] 내에 7개 이하의 제품을 가진 인스턴스에서 실패합니다
기하급수적인 성장 : 솔루션 공간이 기하급수적으로 증가하여( $2^n$ 가능한 과제) 무차별 접근 방식이 불가능해집니다

이러한 심각한 계산 장벽은 영역 계획 및 자원 할당과의 실질적인 관련성과 결합되어 시장 분할 문제를 양자 최적화 알고리즘의 이상적인 벤치마크로 만듭니다 [4].

이스케이의 접근 방식이 독특한 이유는 무엇인가?

Iskay 옵티마이저는 양자 최적화의 중요한 진보를 보여주는 bf-DCQO(바이어스 필드 디지털화 역전파 양자 최적화) 알고리즘 [1] 을 사용합니다:

회로 효율성 : Bf-DCQO 알고리즘은 놀라운 게이트 감소를 달성합니다 [1] :

디지털 양자 어닐링(DQA) 대비 최대 10배 적은 얽힘 게이트 수
훨씬 더 얕은 회로가 가능합니다:
- 양자 실행 중 오류 누적 감소
- 현재 양자 하드웨어에서 더 큰 문제를 해결할 수 있는 능력
- 오류 완화 기술 필요 없음

비변수적 설계 : 약 100회의 반복이 필요한 가변 알고리즘과 달리 bf-DCQO는 일반적으로 약 10회의 반복만 필요합니다 [1]. 다음과 같은 기능을 통해 이룰 수 있습니다.

측정된 상태 분포로부터 지능적인 바이어스 필드 계산
이전 솔루션에 가까운 에너지 상태에서 각 반복을 시작합니다
로컬 검색과 클래식 후처리 통합

역당화 프로토콜 : 이 알고리즘은 짧은 진화 시간 동안 원치 않는 양자 여기를 억제하는 역당화 조건을 통합하여 빠른 전환에도 시스템이 기저 상태에 가깝게 유지될 수 있도록 합니다 [1].

요구사항

이 튜토리얼을 시작하기 전에 다음이 설치되어 있는지 확인하세요:

키스킷 IBM 런타임 (pip install qiskit-ibm-runtime)
Qiskit Functions (pip install qiskit-ibm-catalog)
NumPy (pip install numpy)
요청 (pip install requests)
옵트 매퍼 키스킷 애드온 (pip install qiskit-addon-opt-mapper)

또한 Qiskit Functions Catalog 에서 이스케이 퀀텀 옵티마이저 기능에 액세스해야 합니다.

설정

먼저 이 튜토리얼에 필요한 모든 패키지를 가져옵니다.

import os
import tempfile
import time
from typing import Tuple, Optional

import numpy as np
import requests

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

print("All required libraries imported successfully")

IBM Quantum 자격 증명 구성

자격 증명 정의 IBM Quantum® Platform 자격 증명을 정의합니다. 필요한 사항은 다음과 같습니다.

API 토큰 : 44자 API 키 IBM Quantum Platform
인스턴스 CRN : IBM Cloud® 인스턴스 식별자

token = "<YOUR_API_KEY>"
instance = "<YOUR_INSTANCE_CRN>"

1단계: 고전적 입력을 양자 문제에 매핑하기

먼저 고전적인 문제를 양자 호환 표현에 매핑하는 것으로 시작합니다. 이 단계에는 다음이 포함됩니다:

Iskay 퀀텀 옵티마이저에 연결하기
마켓 분할 문제 로드 및 공식화
이를 해결할 bf-DCQO 알고리즘 이해하기

Iskay Quantum Optimizer에 연결

먼저 Qiskit Functions Catalog 에 접속하여 Iskay 퀀텀 옵티마이저를 로드합니다. 이스케이 옵티마이저는 양자 하드웨어에서 최적화 문제를 해결하기 위해 bf-DCQO 알고리즘을 구현하는 키푸 퀀텀에서 제공하는 양자 함수입니다.

catalog = QiskitFunctionsCatalog(token=token, instance=instance)
iskay_solver = catalog.load("kipu-quantum/iskay-quantum-optimizer")

print("Iskay optimizer loaded successfully")
print("Ready to solve optimization problems using bf-DCQO algorithm")

문제를 로드하고 공식화하다

문제 데이터 형식 이해하기

QOBLIB(양자 최적화 벤치마킹 라이브러리) [2] 의 문제 인스턴스는 간단한 텍스트 형식으로 저장됩니다. 대상 인스턴스 ms_03_200_177.dat 의 실제 콘텐츠를 살펴보겠습니다:

3 20
60   92  161   53   97    2   75   81    6  139  132   45  108  112  181   93  152  200  164   51 1002
176  196   41  143    2   88    0   79   10   71   75  148   82  135   34  187   33  155   58   46  879
68   68  179  173  127  163   48   49   99   78   44   52  173  131   73  198   84  109  180   95 1040

형식 구조:

첫 번째 줄: 3 20
- 3 = 제품 수(행렬의 제약 조건/행) $A$ )
- 20 = 시장 수(행렬의 변수/열 $A$ )
다음 3줄: 계수 행렬 $A$ 및 대상 벡터 $b$
- 각 줄에는 21개의 숫자가 있습니다. 처음 20개는 행 계수, 마지막은 목표입니다
- 선 2: 60 92 161 ... 51 | 1002
  - 처음 20개의 숫자: 20개 시장에서 각각 제품 1의 판매량
  - 마지막 번호(1002): 한 지역의 제품 1에 대한 목표 판매량
- 행 3: 176 196 41 ... 46 | 879
  - 시장 및 타겟별 제품 2 판매(879)
- 4번 라인: 68 68 179 ... 95 | 1040
  - 시장 및 타겟별 제품 3 판매(1040)

비즈니스 통역:

마켓 0 판매량: 제품 1 60개, 제품 2 176개, 제품 3 68개
마켓 1 판매량: 제품 1 92개, 제품 2 196개, 제품 3 68개
그리고 20개 시장 모두에 대해...
목표 : 20개 시장을 두 지역으로 분할하여 각 지역에 제품 1은 1002개, 제품 2는 879개, 제품 3은 1040개를 정확히 배치합니다

QUBO 변환

제약 조건에서 QUBO로: 수학적 변환

양자 최적화의 힘은 제약이 있는 문제를 제약이 없는 이차적 형태로 변환하는 데 있습니다 [4]. 시장 분할 문제의 경우, 평등 제약 조건을 변환합니다

$Ax = b$

여기서 $x ∈ \{0,1\}^n$ , 제약 조건 위반에 대한 벌칙을 적용하여 QUBO로 전환합니다.

페널티 방법: $Ax = b$ 을 정확히 유지해야 하므로 위반의 제곱을 최소화합니다: $f(x) = ||Ax - b||^2$

모든 제약 조건이 충족되면 정확히 0이 됩니다. 대수적으로 확장하기: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

QUBO 목표: $b^T b$ 는 상수이므로 최적화가 됩니다: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

핵심 인사이트: 이 변환은 근사치가 아닌 정확한 수치입니다. 등식 제약 조건은 보조 변수나 페널티 매개변수 없이 자연스럽게 이차식으로 제곱되므로 양자 솔버에게 수학적으로 우아하고 계산적으로 효율적입니다 [4]. OptimizationProblem 클래스를 사용하여 제약된 문제를 정의한 다음, qiskit_addon_opt_mapper 패키지에서 OptimizationProblemToQubo 을 사용하여 QUBO 형식으로 변환하겠습니다. 이렇게 하면 페널티 기반 변환이 자동으로 처리됩니다.

데이터 로딩 및 QUBO 변환 기능 구현

이제 세 가지 유틸리티 함수를 정의합니다:

parse_marketsplit_dat() - .dat 파일 형식을 구문 분석하고 행렬 $A$ 및 $b$
fetch_marketsplit_data() - QOBLIB 리포지토리에서 직접 문제 인스턴스 다운로드

def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:
    """
    Parse a market split problem from a .dat file format.

    Parameters
    ----------
    filename : str
        Path to the .dat file containing the market split problem data.

    Returns
    -------
    A : np.ndarray
        Coefficient matrix of shape (m, n) where m is the number of products
        and n is the number of markets.
    b : np.ndarray
        Target vector of shape (m,) containing the target sales per product.
    """
    with open(filename, "r", encoding="utf-8") as f:
        lines = [
            line.strip()
            for line in f
            if line.strip() and not line.startswith("#")
        ]

    if not lines:
        raise ValueError("Empty or invalid .dat file")

    # First line: m n (number of products and markets)
    m, n = map(int, lines[0].split())

    # Next m lines: each row of A followed by corresponding element of b
    A, b = [], []
    for i in range(1, m + 1):
        values = list(map(int, lines[i].split()))
        A.append(values[:-1])  # First n values: product sales per market
        b.append(values[-1])  # Last value: target sales for this product

    return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)


def fetch_marketsplit_data(
    instance_name: str = "ms_03_200_177.dat",
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Fetch market split data directly from the QOBLIB repository.

    Parameters
    ----------
    instance_name : str
        Name of the .dat file to fetch (default: "ms_03_200_177.dat").

    Returns
    -------
    A : np.ndarray or None
        Coefficient matrix if successful, None if failed.
    b : np.ndarray or None
        Target vector if successful, None if failed.
    """
    url = f"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}"

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".dat", delete=False, encoding="utf-8"
        ) as f:
            f.write(response.text)
            temp_path = f.name

        try:
            return parse_marketsplit_dat(temp_path)
        finally:
            os.unlink(temp_path)
    except Exception as e:
        print(f"Error: {e}")
        return None, None

문제 인스턴스 로드

이제 QOBLIB [2에서] 특정 문제 인스턴스 ms_03_200_177.dat 를 로드합니다. 이 인스턴스에는

3개 제품(제약 조건)
20개 시장(이진 결정 변수)
1백만 개 이상의 가능한 시장 과제 ( $2^{20} = 1,048,576$ )

# Load the problem instance
instance_name = "ms_03_200_177.dat"
A, b = fetch_marketsplit_data(instance_name=instance_name)

if A is not None:
    print("Successfully loaded problem instance from QOBLIB")
    print("\nProblem Instance Analysis:")
    print("=" * 50)
    print(f"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}")
    print(f"   → {A.shape[0]} products (constraints)")
    print(f"   → {A.shape[1]} markets (decision variables)")
    print(f"Target Vector b: {b}")
    print("   → Target sales per product for each region")
    print(
        f"Solution Space: "
        f"2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

QUBO 형식으로 변환

이제 제약된 최적화 문제를 QUBO 형식으로 변환합니다:

# Create optimization problem
ms = OptimizationProblem(instance_name.replace(".dat", ""))

# Add binary variables (one for each market)
ms.binary_var_list(A.shape[1])

# Add equality constraints (one for each product)
for idx, rhs in enumerate(b):
    ms.linear_constraint(A[idx, :], sense="==", rhs=rhs)

# Convert to QUBO with penalty parameter
qubo = OptimizationProblemToQubo(penalty=1).convert(ms)

print("QUBO Conversion Complete:")
print("=" * 50)
print(f"Number of variables: {qubo.get_num_vars()}")
print(f"Constant term: {qubo.objective.constant}")
print(f"Linear terms: {len(qubo.objective.linear.to_dict())}")
print(f"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}")

QUBO를 Iskay 형식으로 변환

이제 QUBO 객체를 키푸 퀀텀의 이스케이 옵티마이저에 필요한 사전 형식으로 변환해야 합니다.

problem 및 problem_type 인수는 다음과 같은 형식의 최적화 문제를 인코딩합니다

\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}

여기서,

C(x_1, ... , x_n) = a + \sum_{i} b_i x_i + \sum_{i, j} c_{i, j} x_i x_j + ... + \sum_{k_1, ..., k_m} g_{k_1, ..., k_m} x_{k_1} ... x_{k_m}

problem_type = "binary" 을 선택하면 비용 함수가 binary 형식으로 지정되며, 이는 $D = \{0, 1\}^{n}$ 과 같이 비용 함수가 QUBO/HUBO 공식으로 작성됨을 의미합니다.
반면에 problem_type = "spin" 을 선택하면 비용 함수가 Ising 공식으로 작성되며, 여기서 $D = \{-1, 1\}^{n}$ .

문제의 계수는 다음과 같이 사전에서 인코딩해야 합니다:

\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \quad (i \neq j) \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"}&: \quad &g_{k_1, ..., k_m}, \quad (k_1 \neq k_2 \neq \dots \neq k_m) \\ \nonumber &\texttt{\}} \end{align}

사전의 키는 반복되지 않는 정수의 유효한 튜플을 포함하는 문자열이어야 한다는 점에 유의하세요. 이진 문제의 경우, 저희도 알고 있습니다:

x_i^2 = x_i

의 경우 $i=j$ ( $x_i \in \{0,1\}$ 은 $x_i \cdot x_i = x_i$ 을 의미하므로 ). 따라서 QUBO 공식에서 선형 기여도 $b_i x_i$ 와 대각선 이차 기여도 $c_{i,i} x_i^2$ 가 모두 있는 경우 이 용어는 단일 선형 계수로 결합되어야 합니다:

변수의 총 선형 계수 $x_i$ : $b_i + c_{i,i}$

이는 다음을 의미합니다.

"(i, )" 같은 선형 용어에는 원래 선형 계수 + 대각선 이차 계수가 포함됩니다
"(i, i)" 같은 대각선 2진법 용어는 최종 사전에 나타나지 않아야 합니다
"(i, j)" 와 같이 대각선을 벗어난 사칙연산 용어만 $i \neq j$ 을 별도의 항목으로 포함해야 합니다

예시: 예: QUBO에 $3x_1 + 2x_1^2 + 4x_1 x_2$ 이 있는 경우 이스케이 사전이 포함되어야 합니다:

"(0, )": 5.0 ( $3 + 2 = 5$ 결합 )
"(0, 1)": 4.0 (대각선 외 용어)

"(0, )": 3.0 및 "(0, 0)": 2.0 에 대한 별도의 항목이 아닙니다.

# Convert QUBO to Iskay dictionary format:

# Create empty Iskay input dictionary
iskay_input_problem = {}

# Convert QUBO to Iskay dictionary format
iskay_input_problem = {"()": qubo.objective.constant}

for i in range(qubo.get_num_vars()):
    for j in range(i, qubo.get_num_vars()):
        if i == j:
            # Add linear term (including diagonal quadratic contribution)
            iskay_input_problem[f"({i}, )"] = float(
                qubo.objective.linear.to_dict().get(i)
            ) + float(qubo.objective.quadratic.to_dict().get((i, i)))
        else:
            # Add off-diagonal quadratic term
            iskay_input_problem[f"({i}, {j})"] = float(
                qubo.objective.quadratic.to_dict().get((i, j))
            )

# Display Iskay dictionary summary
print("Iskay Dictionary Format:")
print("=" * 50)
print(f"Total coefficients: {len(iskay_input_problem)}")
print(f"  • Constant term: {iskay_input_problem['()']}")
print(
    f"  • Linear terms: "
    f"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: "
    f"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

# Get first 10 and last 5 items properly
items = list(iskay_input_problem.items())
first_10 = list(enumerate(items[:10]))
last_5 = list(enumerate(items[-5:], start=len(items) - 5))

for i, (key, value) in first_10 + last_5:
    coeff_type = (
        "constant"
        if key == "()"
        else "linear"
        if ", )" in key
        else "quadratic"
    )
    print(f"  {key}: {value} ({coeff_type})")
print("  ...")
print("\n✓ Problem ready for Iskay optimizer!")

bf-DCQO 알고리즘 이해하기

최적화를 실행하기 전에 Iskay를 구동하는 정교한 양자 알고리즘인 bf-DCQO(바이어스 필드 디지털화 역전파 양자 최적화) [1] 를 이해해 보겠습니다.

bf-DCQO란 무엇인가요?

bf-DCQO는 최종 양자 해밀턴의 기저 상태 (최저 에너지 상태)에서 문제 해가 인코딩되는 양자 시스템의 시간 진화를 기반으로 합니다 [1]. 이 알고리즘은 양자 최적화의 근본적인 문제를 해결합니다:

도전 과제 : 기존의 단열 양자 컴퓨팅은 단열 정리에 따라 접지 상태 조건을 유지하기 위해 매우 느린 진화가 필요합니다. 문제의 복잡성이 증가함에 따라 점점 더 깊은 양자 회로가 필요하며, 이는 더 많은 게이트 연산과 누적된 오류로 이어집니다.

솔루션 : bf-DCQO는 역당뇨 프로토콜을 사용하여 접지 상태 충실도를 유지하면서 빠른 진화를 가능하게 하여 회로 깊이를 획기적으로 줄입니다.

수학적 체계

이 알고리즘은 비용 함수를 최소화합니다:

$\min_{(x_1,x_2,...,x_n) \in D} C(x_1,x_2,...,x_n)$

여기서 $D = \{0,1\}^n$ 는 바이너리 변수이고:

$C(x) = a + \sum_i b_i x_i + \sum_{i,j} c_{ij} x_i x_j + ... + \sum g_{k_1,...,k_m} x_{k_1}...x_{k_m}$

시장 분할 문제의 경우 비용 함수는 다음과 같습니다:

$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$

당뇨병 억제 항목의 역할

역당성 용어는 양자 진화 과정에서 원치 않는 여기를 억제하기 위해 시간 의존적 해밀턴에 도입된 추가 용어입니다. 이것이 중요한 이유는 다음과 같습니다:

단열 양자 최적화에서는 시간 의존적 해밀턴에 따라 시스템을 진화시킵니다:

$H(t) = \left(1 - \frac{t}{T}\right) H_{\text{initial}} + \frac{t}{T} H_{\text{problem}}$

여기서 $H_{\text{problem}}$ 은 최적화 문제를 인코딩합니다. 빠른 진화 중에 지상 상태를 유지하기 위해 반대되는 조건을 추가합니다:

$H_{\text{CD}}(t) = H(t) + H_{\text{counter}}(t)$

이러한 반당뇨병 용어는 다음과 같은 기능을 합니다:

원치 않는 전환을 억제합니다 : 빠른 진화 중에 양자 상태가 들뜬 상태로 점프하는 것을 방지합니다
진화 시간을 단축할 수 있습니다: 단열성을 위반하지 않고 훨씬 빠르게 최종 상태에 도달할 수 있습니다
회로 깊이를 줄입니다 : 짧은 진화는 더 적은 게이트와 오류 감소로 이어집니다

Bf-DCQO는 디지털 양자 열처리 [1] 보다 최대 10배 적은 수의 얽힘 게이트를 사용하므로 오늘날의 잡음이 많은 양자 하드웨어에 실용적입니다.

편향장 반복 최적화

많은 반복을 통해 회로 파라미터를 최적화하는 변형 알고리즘과 달리 bf-DCQO는 약 10회의 반복으로 수렴하는 바이어스 필드 유도 방식을 사용합니다 [1] :

반복 프로세스:

초기 양자 진화 : 역진화 프로토콜을 구현하는 양자 회로로 시작하세요
측정 : 양자 상태를 측정하여 비트스트링에 대한 확률 분포를 얻습니다
바이어스 필드 계산 : 측정 통계를 분석하고 각 큐비트에 대한 최적의 바이어스 필드( $h_i$ )를 계산합니다: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$
다음 반복 : 바이어스 필드는 다음 반복을 위해 해밀턴을 수정합니다: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

이를 통해 이전에 찾은 좋은 솔루션 근처에서 시작하여 일종의 "양자 로컬 검색"을 효과적으로 수행할 수 있습니다
수렴 : 솔루션 품질이 안정화되거나 최대 반복 횟수에 도달할 때까지 반복합니다

주요 이점 : 각 반복은 매개변수 공간을 무작위로 탐색해야 하는 변형 방법과 달리 이전 측정의 정보를 통합하여 최적의 솔루션을 향한 의미 있는 진전을 제공합니다.

통합된 고전적 후처리

양자 최적화가 수렴한 후 Iskay는 고전적인 로컬 검색 후처리를 수행합니다:

비트 플립 탐색 : 최상의 측정 솔루션에서 체계적으로 또는 무작위로 비트 뒤집기
에너지 평가 : 각 수정된 솔루션에 대해 $C(x)$ 계산
욕심 많은 선택 : 비용 함수를 낮추는 개선 사항 수용
여러 번 통과하기 : 여러 패스 수행( postprocessing_level)으로 제어

이 하이브리드 접근 방식은 하드웨어 결함 및 판독 오류로 인한 비트 플립 오류를 보완하여 잡음이 많은 양자 디바이스에서도 고품질 솔루션을 보장합니다.

왜 bf-DCQO가 현재 하드웨어에서 뛰어난 성능을 보이는가

Bf-DCQO 알고리즘은 특히 오늘날의 잡음이 많은 중간 규모 양자(NISQ) 디바이스에서 탁월한 성능을 발휘하도록 설계되었습니다 [1] :

오류 복원력 : 더 적은 수의 게이트(10배 감소)로 오류 누적을 획기적으로 줄임
오류 완화 기술이 필요하지 않습니다 : 알고리즘의 고유한 효율성 덕분에 값비싼 오류 완화 기술이 필요하지 않습니다 [1]
확장성 : 직접 큐비트 매핑을 통해 최대 156개의 큐비트(156개의 이진 변수) 문제를 처리할 수 있습니다 [1]
검증된 성능 : 벤치마크 MaxCut 및 HUBO 인스턴스에서 100% 근사화 비율 달성 [1]

이제 마켓 분할 문제에서 이 강력한 알고리즘이 실제로 작동하는 모습을 확인해 보겠습니다!

2단계: 양자 하드웨어 실행을 위한 문제 최적화

Bf-DCQO 알고리즘은 회로 최적화를 자동으로 처리하여 대상 백엔드에 맞게 특별히 설계된 역역학 조건으로 얕은 양자 회로를 생성합니다.

최적화 구성

Iskay 옵티마이저는 최적화 문제를 효과적으로 해결하기 위해 몇 가지 주요 매개변수를 필요로 합니다. 각 파라미터와 양자 최적화 프로세스에서 각 파라미터의 역할을 살펴보겠습니다:

필수 매개변수

매개변수	유형	설명	예
문제점	`Dict[str, float]`	문자열 키 형식의 QUBO 계수	`{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}`
문제_type	`str`	형식 사양: QUBO의 경우 `"binary"` , Ising의 경우 `"spin"`	`"binary"`
백엔드_이름	`str`	대상 양자 디바이스	`"ibm_fez"`

핵심 개념

문제 형식 : 변수는 시장 할당을 나타내는 이진(0/1)이므로 "binary" 을 사용합니다.
백엔드 선택 : 필요에 따라 사용 가능한 QPU(예: "ibm_fez")를 선택하고 리소스 인스턴스를 계산합니다.
QUBO 구조 : 문제 사전에는 수학적 변환의 정확한 계수가 포함되어 있습니다.

고급 옵션 (선택 사항)

Iskay는 옵션 매개변수를 통해 미세 조정 기능을 제공합니다. 기본값은 대부분의 문제에 대해 잘 작동하지만 특정 요구 사항에 맞게 동작을 사용자 지정할 수 있습니다:

매개변수	유형	기본값	설명
샷	`int`	10000	반복당 양자 측정값(높을수록 정확도 높음)
숫자_이터레이션	`int`	1,000만	알고리즘 반복(반복 횟수가 많을수록 솔루션 품질이 향상될 수 있음)
사용_세션	`bool`	예	대기열 시간 단축을 위해 IBM 세션 사용
시드_트랜스파일러	`int`	없음	재현 가능한 양자 회로 컴파일을 위한 설정
직접_QUBIT_mapping	`bool`	아니오	가상 큐비트를 물리적 큐비트에 직접 매핑하기
job_tags	`List[str]`	없음	작업 추적용 사용자 지정 태그
전처리_LEVEL	`int`	0	문제 사전 처리 강도(0~3) - 아래 세부 정보 참조
후처리_LEVEL	`int`	2	솔루션 정제 수준(0-2) - 아래 세부 정보 참조
트랜스필레이션_레벨	`int`	0	트랜스파일러 최적화 평가판(0~5) - 아래 세부 정보 참조
트랜스파일_only	`bool`	아니오	전체 실행을 실행하지 않고 회로 최적화 분석

전처리 수준(0~3 ): 현재 하드웨어의 일관성 시간에 맞출 수 없는 큰 문제에 특히 중요합니다. 전처리 수준이 높을수록 문제 변환의 근사치를 통해 회로 깊이가 얕아집니다:

레벨 0 : 정확하고 긴 회로
레벨 1 : 정확도와 근사치 사이의 균형이 양호하여 각도가 하위 10% 백분위수인 게이트만 잘라냅니다
레벨 2 : 약간 더 높은 근사치, 각도가 하위 20% 백분위수인 게이트를 잘라내고 번역에 approximation_degree=0.95 사용
레벨 3 : 최대 근사치 수준, 하위 30% 백분위수에서 게이트를 잘라내고 트랜스퓔레이션에 approximation_degree=0.90 사용

트랜스파일링 레벨(0-5 ): 양자 회로 컴파일을 위한 고급 트랜스파일러 최적화 트라이얼을 제어합니다. 이로 인해 클래식 오버헤드가 증가할 수 있으며 경우에 따라서는 회로 깊이가 변경되지 않을 수도 있습니다. 기본값 2 은 일반적으로 가장 작은 회로로 연결되며 상대적으로 빠릅니다.

레벨 0 : 분해된 DCQO 회로 최적화(레이아웃, 라우팅, 스케줄링)
레벨 1 : PauliEvolutionGate 의 최적화 후 분해된 DCQO 회로 ( max_trials=10 )
레벨 2 : PauliEvolutionGate 의 최적화 후 분해된 DCQO 회로 ( max_trials=15 )
레벨 3 : PauliEvolutionGate 의 최적화 후 분해된 DCQO 회로 ( max_trials=20 )
레벨 4 : PauliEvolutionGate 의 최적화 후 분해된 DCQO 회로 ( max_trials=25 )
레벨 5 : PauliEvolutionGate 의 최적화 후 분해된 DCQO 회로 ( max_trials=50 )

포스트 프로세싱 레벨(0-2 ): 로컬 검색의 다양한 욕심 패스 횟수로 비트 플립 오류를 보정하는 클래식 최적화 정도를 제어합니다:

레벨 0 : 1 패스
레벨 1 : 2패스
레벨 2 : 3 패스

트랜스파일 전용 모드 : 이제 전체 양자 알고리즘 실행을 실행하지 않고 회로 최적화를 분석하려는 사용자가 사용할 수 있습니다.

사용자 지정 구성 예시

다양한 설정으로 Iskay를 구성하는 방법은 다음과 같습니다:

custom_options = {
    # Higher shot count for better statistics
    "shots": 15_000,

    # More iterations for solution refinement
    "num_iterations": 12,

    # Light preprocessing for problem simplification
    "preprocessing_level": 1,

    # Maximum postprocessing for solution quality
    "postprocessing_level": 2,

    # Using higher transpilation level for circuit optimization
    "transpilation_level": 3,

    # Fixed seed for reproducible results
    "seed_transpiler": 42,

    # Custom tracking tags
    "job_tags": ["market_split"]
}

이 튜토리얼에서는 대부분의 기본 파라미터를 유지하고 바이어스 필드 반복 횟수만 변경하겠습니다:

# Specify the target backend
backend_name = "ibm_fez"

# Set the number of bias-field iterations and set a tag to identify the jobs
options = {
    "num_iterations": 3,  # Change number of bias-field iterations
    "job_tags": ["market_split_example"],  # Tag to identify jobs
}

# Configure Iskay optimizer
iskay_input = {
    "problem": iskay_input_problem,
    "problem_type": "binary",
    "backend_name": backend_name,
    "options": options,
}

print("Iskay Optimizer Configuration:")
print("=" * 40)
print(f"  Backend: {backend_name}")
print(f"  Problem: {len(iskay_input['problem'])} terms")
print("  Algorithm: bf-DCQO")

3단계: `Qiskit primitives` 명령어로 실행합니다

이제 IBM Quantum 하드웨어에서 실행되도록 문제를 제출합니다. Bf-DCQO 알고리즘이 작동합니다:

반당뇨 조건으로 얕은 양자 회로 구성하기
바이어스 필드 최적화를 통해 약 10회의 반복을 실행합니다
로컬 검색으로 고전적인 후처리 수행
최적의 시장 할당 반환

# Submit the optimization job
print("Submitting optimization job to Kipu Quantum...")
print(
    f"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms"
)
print(
    "Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)"
)

job = iskay_solver.run(**iskay_input)

print("\nJob successfully submitted!")
print(f"Job ID: {job.job_id}")
print("Optimization in progress...")
print(
    f"The bf-DCQO algorithm will efficiently explore "
    f"{2**A.shape[1]:,} possible assignments"
)

작업 상태 모니터링

최적화 작업의 현재 상태를 확인할 수 있습니다. 가능한 상태는 다음과 같습니다.

QUEUED: 작업이 대기열에서 대기 중입니다
RUNNING: 작업이 현재 양자 하드웨어에서 실행 중입니다
DONE: 작업이 성공적으로 완료되었습니다
CANCELED: 작업이 취소되었습니다
ERROR: 작업에서 오류가 발생했습니다

# Check job status
print(f"Job status: {job.status()}")

완료 대기

이 셀은 작업이 완료될 때까지 차단됩니다. 최적화 프로세스에는 다음이 포함됩니다:

대기 시간(퀀텀 하드웨어 액세스 대기)
실행 시간(약 10회 반복으로 bf-DCQO 알고리즘 실행)
후처리 시간(기존 로컬 검색)

일반적인 완료 시간은 대기열 조건에 따라 몇 분에서 수십 분까지 다양합니다.

# Wait for job completion
while True:
    status = job.status()
    print(
        f"Waiting for job {job.job_id} to complete... (status: {status})",
        end="\r",
        flush=True,
    )
    if status in ["DONE", "CANCELED", "ERROR"]:
        print(
            f"\nJob {job.job_id} completed with status: {status}" + " " * 20
        )
        break
    time.sleep(30)

# Retrieve the optimization results
result = job.result()
print("\nOptimization complete!")

4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환

이제 양자 실행 결과를 사후 처리합니다. 여기에는 다음과 같은 혜택이 포함됩니다.

솔루션 구조 분석
제약 조건 충족 검증
기존 접근 방식에 대한 벤치마킹

결과 분석

결과 구조 이해하기

Iskay는 다음을 포함하는 포괄적인 결과 사전을 반환합니다:

solution: 변수 인덱스를 최적의 값(0 또는 1)에 매핑하는 사전입니다
solution_info: 다음을 포함한 상세 정보:
- bitstring: 바이너리 문자열로 최적 할당
- cost: 목적 함수 값(완벽한 제약 조건 만족을 위해 0이어야 함)
- mapping: 비트 문자열 위치가 문제 변수에 매핑되는 방법
- seed_transpiler: 재현성을 위해 사용된 씨앗
prob_type: 솔루션이 바이너리 또는 스핀 형식인지 여부

양자 최적화 도구가 반환한 솔루션을 살펴보겠습니다.

# Display the optimization results
print("Optimization Results")
print("=" * 50)
print(f"Problem Type: {result['prob_type']}")
print("\nSolution Info:")
print(f"  Bitstring: {result['solution_info']['bitstring']}")
print(f"  Cost: {result['solution_info']['cost']}")
print("\nSolution (first 10 variables):")
for i, (var, val) in enumerate(list(result["solution"].items())[:10]):
    print(f"  {var}: {val}")
print("  ...")

솔루션 검증

이제 양자 솔루션이 마켓 스플릿 제약 조건을 충족하는지 검증합니다. 유효성 검사 프로세스를 확인합니다:

제약 조건 위반이란 무엇인가요?

각 제품 $i$ 에 대해 지역 A의 실제 매출을 계산합니다: $(Ax)_i$
이를 목표 매출과 비교합니다 $b_i$
위반 여부는 절대적인 차이입니다: $|(Ax)_i - b_i|$
실현 가능한 솔루션은 모든 제품에 대해 위반 사항이 없습니다

기대하는 바

이상적인 경우 : 총 위반 = 0(모든 제약 조건이 완벽하게 충족됨)
- 지역 A는 정확히 제품 1 1002개, 제품 2 879개, 제품 3 1040개를 얻습니다
- 지역 B는 나머지 유닛(각각 1002, 879, 1040)을 가져옵니다
좋은 사례입니다 : 총 위반 건수가 적음(최적에 가까운 솔루션)
불량 사례 : 위반 사항이 크면 솔루션이 비즈니스 요구 사항을 충족하지 못함을 나타냅니다

유효성 검사 함수가 계산됩니다:

각 지역의 제품별 실제 판매량
각 제품에 대한 제약 조건 위반
지역 간 시장 분포

def validate_solution(A, b, solution):
    """Validate market split solution."""
    x = np.array(solution)
    region_a = A @ x
    region_b = A @ (1 - x)
    violations = np.abs(region_a - b)

    return {
        "target": b,
        "region_a": region_a,
        "region_b": region_b,
        "violations": violations,
        "total_violation": np.sum(violations),
        "is_feasible": np.sum(violations) == 0,
        "region_a_markets": int(np.sum(x)),
        "region_b_markets": len(x) - int(np.sum(x)),
    }


# Convert bitstring to list of integers and validate
optimal_assignment = [
    int(bit) for bit in result["solution_info"]["bitstring"]
]
validation = validate_solution(A, b, optimal_assignment)

검증 결과를 해석하십시오

검증 결과는 퀀텀 옵티마이저가 실현 가능한 솔루션을 찾았는지 여부를 보여줍니다. 다음 사항을 살펴보겠습니다:

타당성 확인:

is_feasible = True 는 솔루션이 모든 제약 조건을 완벽하게 만족함을 의미합니다(총 위반 = 0)
is_feasible = False 는 일부 제약 조건을 위반했음을 의미합니다

판매 분석:

각 제품의 목표 판매량과 실제 판매량 비교
완벽한 솔루션을 위해: 실제 = 두 지역의 모든 제품 대상
이 차이는 원하는 시장 분할에 얼마나 근접했는지를 나타냅니다

시장 배포:

각 지역에 할당된 시장 수를 표시합니다
동일한 수의 시장에 대한 요구 사항은 없으며, 판매 목표만 달성하면 됩니다

print("Solution Validation")
print("=" * 50)
print(f"Feasible solution: {validation['is_feasible']}")
print(f"Total constraint violation: {validation['total_violation']}")

print("\nSales Analysis (Target vs Actual):")
for i, (target, actual_a, actual_b) in enumerate(
    zip(validation["target"], validation["region_a"], validation["region_b"])
):
    violation_a = abs(actual_a - target)
    violation_b = abs(actual_b - target)
    print(f"  Product {i+1}:")
    print(f"    Target: {target}")
    print(f"    Region A: {actual_a} (violation: {violation_a})")
    print(f"    Region B: {actual_b} (violation: {violation_b})")

print("\nMarket Distribution:")
print(f"  Region A: {validation['region_a_markets']} markets")
print(f"  Region B: {validation['region_b_markets']} markets")

솔루션 품질 평가

위의 검증 결과를 바탕으로 양자 솔루션의 품질을 평가할 수 있습니다:

** is_feasible = True (총 위반 횟수 = 0)인 경우:**

퀀텀 옵티마이저가 최적의 솔루션을 성공적으로 찾았습니다
모든 비즈니스 제약 조건이 완벽하게 충족됩니다
이는 고전적 풀이 방식이 어려움을 겪는 문제에서 양자 우위를 보여줍니다 [4]

** is_feasible = False (총 위반 횟수 > 0)인 경우:**

거의 최적에 가까운 솔루션이지만 완벽하지는 않습니다
실무상 사소한 위반은 허용될 수 있습니다
최적화 도구 매개변수 조정을 고려하세요:
- 최적화 패스를 더 늘리려면 num_iterations
- 클래식한 세련미를 더하려면 postprocessing_level 으로 늘리세요
- 더 나은 측정 통계를 위해 shots 늘리기

비용 함수 해석:

solution_info 의 cost 값은 다음과 같습니다 $||Ax - b||^2$
비용 = 0은 완벽한 제약 조건 만족을 나타냅니다
비용 값이 높을수록 제약 조건 위반이 더 크다는 의미입니다

결론

우리가 이룬 것

이 튜토리얼에서는 성공적으로 완료했습니다:

실제 최적화 문제 로드 : QOBLIB 벤치마크 라이브러리에서 까다로운 마켓 스플릿 인스턴스 획득 [2]
QUBO 형식으로 변환 : 제약된 문제를 제약되지 않은 이차 공식으로 변환 [3]
고급 양자 알고리즘을 활용했습니다 : 키푸 퀀텀의 bf-DCQO 알고리즘과 역당뇨 용어 사용 [1]
최적의 솔루션을 얻었습니다 : 모든 제약 조건을 만족하는 실현 가능한 솔루션 발견

주요 이점

알고리즘 혁신 : Bf-DCQO 알고리즘은 상당한 발전을 이루었습니다 [1] :

디지털 양자 어닐링보다 10배 적은 게이트 수
변형 방법의 경우 약 100회 대신 약 10회 반복
회로 효율을 통한 오류 복원력 내장

역설적 용어 : 접지 상태 충실도를 유지하면서 빠른 양자 진화를 가능하게 하여 오늘날의 잡음이 많은 하드웨어에서 양자 최적화를 실용적으로 구현합니다 [1].

바이어스 필드 안내 : 반복 바이어스 필드 접근 방식은 각 반복이 이전에 찾은 좋은 솔루션 근처에서 시작하여 일종의 양자 강화 로컬 검색을 제공합니다 [1].

다음 단계

이해의 폭을 넓히고 더 깊이 탐구할 수 있습니다:

다른 인스턴스를 사용해 보세요: 다양한 크기의 다른 QOBLIB 인스턴스로 실험해 보세요
매개변수 조정 : 조정: num_iterations, preprocessing_level, postprocessing_level
클래식과 비교 : 기존 최적화 솔버와의 벤치마크
다른 전략을 시도해 보세요: 문제에 대한 더 나은 인코딩을 찾거나 가능한 경우 HUBO로 공식화합니다
도메인에 적용하세요 : QUBO/HUBO 공식화 기법을 귀사의 최적화 문제에 적용하세요

참조

[1] IBM Quantum. "키푸 양자 최적화." IBM Quantum 문서화.

[2] QOBLIB - 퀀텀 최적화 벤치마킹 라이브러리. 주세 인스티튜트 베를린(ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] 글로버, F., Kochenberger, G., & Du, Y. (2019). "퀀텀 브리지 분석 I: QUBO 모델 공식화 및 사용에 대한 튜토리얼." 4OR: 운영 연구 분기별 저널, 17(4), 335-371.

[4] Lodi, A., 트라몬타니, A., & 웨닝어, K. (2023). "난치성 10종 경기: 어려운 조합 문제 벤치마킹하기." 컴퓨팅에 관한 INFORMS 저널.

이 페이지가 도움이 되었습니까?

GitHub에서 버그, 오타를 보고하거나 컨텐츠를 요청하십시오.