주 콘텐츠로 건너뛰기

Kipu Quantum의 Iskay Quantum Optimizer로 Market Split 문제 풀기

참고

Qiskit Functions는 IBM Quantum® Premium Plan, Flex Plan, On-Prem(IBM Quantum Platform API 경유) Plan 사용자만 이용 가능한 실험적 기능입니다. 현재 미리 보기 릴리스 상태이며 변경될 수 있습니다.

사용 시간 예측: Heron r2 프로세서 기준 20초. (참고: 이는 예측값이며 실제 실행 시간은 다를 수 있습니다.)

배경​

이 튜토리얼에서는 Kipu Quantum의 Iskay quantum optimizer [1]를 사용하여 Market Split 문제를 풀어봅니다. Market Split 문제는 정확한 수요 목표를 충족하도록 시장을 균형 잡힌 영업 구역으로 분할해야 하는 실세계 자원 배분 과제를 나타냅니다.

Market Split 과제​

Market Split 문제는 자원 배분에서 겉으로는 단순해 보이지만 계산적으로 매우 어려운 과제를 제시합니다. nn개의 서로 다른 시장에서 판매되는 mm가지 제품을 가진 기업을 생각해 보세요. 각 시장은 특정한 제품 묶음을 구매합니다(행렬 AA의 열로 표현). 비즈니스 목표는 이 시장들을 두 개의 균형 잡힌 영업 구역으로 분할하여 각 구역이 모든 제품에 대해 총 수요의 정확히 절반을 받도록 하는 것입니다.

수학적 공식화:

이진 할당 벡터 xx를 구하며, 여기서:

  • xj=1x_j = 1은 시장 jj를 구역 A에 할당
  • xj=0x_j = 0은 시장 jj를 구역 B에 할당
  • 제약 조건 Ax=bAx = b를 만족해야 하며, bb는 목표 판매량(일반적으로 제품별 총 수요의 절반)을 나타냄

비용 함수:

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

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

여기서:

  • AijA_{ij}는 시장 jj에서 제품 ii의 판매량을 나타냄
  • xj∈{0,1}x_j \in \{0,1\}은 시장 jj의 이진 할당
  • bib_i는 각 구역에서 제품 ii의 목표 판매량
  • 모든 제약 조건이 충족될 때 비용은 정확히 0

합의 각 항은 특정 제품에 대한 목표 판매량으로부터의 제곱 편차를 나타냅니다. 이 비용 함수를 전개하면 다음과 같습니다:

C(x)=xTATAx−2bTAx+bTbC(x) = x^T A^T A x - 2b^T A x + b^T b

bTbb^T b는 상수이므로, C(x)C(x)를 최소화하는 것은 이차 함수 xTATAx−2bTAxx^T A^T A x - 2b^T A x를 최소화하는 것과 동일하며, 이것이 바로 QUBO(Quadratic Unconstrained Binary Optimization) 문제입니다.

계산 복잡도:

단순명쾌한 비즈니스 해석에도 불구하고, 이 문제는 놀라운 계산 난해성을 보입니다:

  • 소규모 실패: 기존의 혼합 정수 프로그래밍 솔버는 1시간 제한 시간 내에 제품이 7개에 불과한 인스턴스에서도 실패합니다 [4]
  • 지수적 증가: 해 공간이 지수적으로 증가하여(2n2^n개의 가능한 할당) 무차별 대입 방식은 현실적으로 불가능

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

Iskay의 접근 방식이 독특한 이유​

Iskay optimizer는 bf-DCQO(bias-field digitized counterdiabatic quantum optimization) 알고리즘 [1]을 사용하며, 이는 양자 최적화에서 중요한 발전을 나타냅니다:

Circuit 효율성: bf-DCQO 알고리즘은 놀라운 Gate 감소를 달성합니다 [1]:

  • Digital Quantum Annealing(DQA)보다 최대 10배 적은 엔탱글링 Gate
  • 훨씬 얕은 Circuit으로 가능한 것들:
    • 양자 실행 중 오류 누적 감소
    • 현재 양자 하드웨어에서 더 큰 문제 처리 가능
    • 오류 완화 기법이 필요 없음

비변분적 설계: 약 100번의 반복이 필요한 변분 알고리즘과 달리, bf-DCQO는 일반적으로 약 10번의 반복만 필요합니다 [1]. 이는 다음을 통해 달성됩니다:

  • 측정된 상태 분포로부터의 지능적인 편향장 계산
  • 이전 해에 가까운 에너지 상태에서 각 반복 시작
  • 로컬 탐색을 포함한 통합 고전적 후처리

반단열적 프로토콜: 알고리즘은 짧은 진화 시간 동안 원치 않는 양자 여기를 억제하는 반단열적 항을 포함하여, 빠른 전이에서도 시스템이 기저 상태 근처에 머물 수 있도록 합니다 [1].

요구 사항​

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

  • Qiskit IBM Runtime (pip install qiskit-ibm-runtime)
  • Qiskit Functions (pip install qiskit-ibm-catalog)
  • NumPy (pip install numpy)
  • Requests (pip install requests)
  • Opt Mapper Qiskit addon (pip install qiskit-addon-opt-mapper)

또한 Qiskit Functions Catalog에서 Iskay Quantum Optimizer 함수에 대한 액세스 권한을 얻어야 합니다.

설정​

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

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit-addon-opt-mapper qiskit-ibm-catalog requests
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 토큰: IBM Quantum Platform의 44자리 API 키
  • Instance CRN: IBM Cloud® 인스턴스 식별자
token = "<YOUR_API_KEY>"
instance = "<YOUR_INSTANCE_CRN>"

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

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

  1. Iskay Quantum Optimizer에 연결
  2. Market Split 문제 로드 및 공식화
  3. 이를 해결할 bf-DCQO 알고리즘 이해

Iskay Quantum Optimizer에 연결하기​

Qiskit Functions Catalog에 연결하고 Iskay Quantum Optimizer를 로드하는 것부터 시작합니다. Iskay Optimizer는 Kipu Quantum이 제공하는 양자 함수로, 양자 하드웨어에서 최적화 문제를 풀기 위해 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(Quantum Optimization Benchmarking Library) [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 = 제품 수(행렬 AA의 제약/행 수)
    • 20 = 시장 수(행렬 AA의 변수/열 수)

  • 다음 3줄: 계수 행렬 AA와 목표 벡터 bb

    • 각 줄에는 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]. Market Split 문제에서는 등식 제약 조건

Ax=bAx = b

여기서 x∈{0,1}nx ∈ \{0,1\}^n을, 제약 조건 위반에 패널티를 부과하여 QUBO로 변환합니다.

패널티 방법: Ax=bAx = b가 정확히 성립해야 하므로, 제곱 위반을 최소화합니다: f(x)=∣∣Ax−b∣∣2f(x) = ||Ax - b||^2

모든 제약 조건이 충족될 때 이 값은 정확히 0이 됩니다. 대수적으로 전개하면: f(x)=(Ax−b)T(Ax−b)=xTATAx−2bTAx+bTbf(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b

QUBO 목적 함수: bTbb^T b는 상수이므로, 최적화 문제는 다음이 됩니다: minimizeQ(x)=xT(ATA)x−2(ATb)Tx\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x

핵심 통찰: 이 변환은 근사적이 아닌 정확합니다. 등식 제약 조건은 보조 변수나 패널티 매개변수 없이 자연스럽게 이차 형식으로 제곱되며, 이는 양자 솔버에 수학적으로 우아하고 계산적으로 효율적인 공식화를 만들어줍니다 [4]. qiskit_addon_opt_mapper 패키지의 OptimizationProblem 클래스를 사용하여 제약이 있는 문제를 정의한 다음, OptimizationProblemToQubo를 사용하여 QUBO 형식으로 변환합니다. 이는 패널티 기반 변환을 자동으로 처리합니다.

데이터 로딩 및 QUBO 변환 함수 구현​

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

  1. parse_marketsplit_dat() - .dat 파일 형식을 파싱하고 행렬 AA와 bb를 추출
  2. 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개 (이진 결정 변수)
  • 탐색 가능한 시장 배정 조합 100만 개 이상 (220=1,048,5762^{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: 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 객체를 Kipu Quantum의 Iskay Optimizer가 요구하는 딕셔너리 형식으로 변환해야 합니다.

problem 및 problem_type 인수는 다음 형태의 최적화 문제를 인코딩합니다.

min⁡(x1,x2,…,xn)∈DC(x1,x2,…,xn)\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}

여기서

C(x1,...,xn)=a+∑ibixi+∑i,jci,jxixj+...+∑k1,...,kmgk1,...,kmxk1...xkmC(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}nD = \{0, 1\}^{n}, 즉 비용 함수가 QUBO/HUBO 형식으로 작성됨을 의미합니다.
  • 반면 problem_type = "spin"을 선택하면 비용 함수는 D={−1,1}nD = \{-1, 1\}^{n}인 Ising 형식으로 작성됩니다.

문제의 계수는 다음과 같이 딕셔너리로 인코딩해야 합니다:

{"()":a,"(i,)":bi,"(i, j)":ci,j,(i≠j)⋮"(k1,...,km)":gk1,...,km,(k1≠k2≠…≠km)}\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}

딕셔너리의 키는 반복되지 않는 정수로 구성된 유효한 튜플 문자열이어야 합니다. 이진 문제에서는 다음이 성립합니다:

xi2=xix_i^2 = x_i

i=ji=j인 경우(xi∈{0,1}x_i \in \{0,1\}이므로 xi⋅xi=xix_i \cdot x_i = x_i). 따라서 QUBO 형식에서 선형 기여 bixib_i x_i와 대각 이차 기여 ci,ixi2c_{i,i} x_i^2가 모두 있다면, 이 항들을 하나의 선형 계수로 결합해야 합니다:

변수 xix_i의 총 선형 계수: bi+ci,ib_i + c_{i,i}

이는 다음을 의미합니다:

  • "(i, )"와 같은 선형 항에는 원래 선형 계수 + 대각 이차 계수가 포함됩니다
  • "(i, i)"와 같은 대각 이차 항은 최종 딕셔너리에 포함되어서는 안 됩니다
  • i≠ji \neq j인 "(i, j)"와 같은 비대각 이차 항만 별도 항목으로 포함됩니다

예시: QUBO에 3x1+2x12+4x1x23x_1 + 2x_1^2 + 4x_1 x_2가 있다면, Iskay 딕셔너리에는 다음이 포함되어야 합니다:

  • "(0, )": 5.0 (3+2=53 + 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: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: {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(편향 필드 디지털화 반단열 양자 최적화, bias-field digitized counterdiabatic quantum optimization) [1]를 이해해 봅시다.

bf-DCQO란 무엇인가요?​

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

문제점: 기존의 단열 양자 컴퓨팅은 단열 정리에 따라 바닥 상태 조건을 유지하기 위해 매우 느린 진화가 필요합니다. 이는 문제 복잡도가 증가할수록 더 깊은 양자 Circuit이 필요하고, 더 많은 Gate 연산과 누적 오류로 이어집니다.

해결책: bf-DCQO는 반단열 프로토콜을 사용하여 바닥 상태 충실도를 유지하면서 빠른 진화를 가능하게 하고, Circuit 깊이를 획기적으로 줄입니다.

수학적 프레임워크​

알고리즘은 다음 형태의 비용 함수를 최소화합니다:

min⁡(x1,x2,...,xn)∈DC(x1,x2,...,xn)\min_{(x_1,x_2,...,x_n) \in D} C(x_1,x_2,...,x_n)

여기서 이진 변수의 경우 D={0,1}nD = \{0,1\}^n이고:

C(x)=a+∑ibixi+∑i,jcijxixj+...+∑gk1,...,kmxk1...xkmC(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=xTATAx−2bTAx+bTbC(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b

반단열 항의 역할​

반단열 항은 양자 진화 중 원치 않는 여기(excitation)를 억제하기 위해 시간 의존 해밀토니안에 도입되는 추가 항입니다. 이것이 중요한 이유는 다음과 같습니다:

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

H(t)=(1−tT)Hinitial+tTHproblemH(t) = \left(1 - \frac{t}{T}\right) H_{\text{initial}} + \frac{t}{T} H_{\text{problem}}

여기서 HproblemH_{\text{problem}}은 최적화 문제를 인코딩합니다. 빠른 진화 중에도 바닥 상태를 유지하기 위해 반단열 항을 추가합니다:

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

이 반단열 항은 다음을 수행합니다:

  1. 원치 않는 전이 억제: 빠른 진화 중 양자 상태가 여기 상태로 도약하는 것을 방지합니다
  2. 짧은 진화 시간 가능: 단열성을 위반하지 않고 훨씬 빠르게 최종 상태에 도달할 수 있습니다
  3. Circuit 깊이 감소: 짧은 진화는 더 적은 Gate와 더 적은 오류로 이어집니다

실질적인 영향은 매우 큽니다: bf-DCQO는 디지털 양자 어닐링에 비해 엔탱글링 Gate를 최대 10배 적게 사용하여 [1], 오늘날의 잡음이 있는 양자 하드웨어에서도 실용적으로 사용할 수 있습니다.

편향 필드 반복 최적화​

많은 반복을 통해 Circuit 매개변수를 최적화하는 변분 알고리즘과 달리, bf-DCQO는 약 10회 반복으로 수렴하는 편향 필드 안내 방식을 사용합니다 [1]:

반복 과정:

  1. 초기 양자 진화: 반단열 진화 프로토콜을 구현하는 양자 Circuit으로 시작합니다

  2. 측정: 양자 상태를 측정하여 비트스트링에 대한 확률 분포를 얻습니다

  3. 편향 필드 계산: 측정 통계를 분석하고 각 Qubit에 대한 최적 편향 필드 hih_i를 계산합니다: hi=f(measurement statistics,previous solutions)h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})

  4. 다음 반복: 편향 필드가 다음 반복을 위한 해밀토니안을 수정합니다: Hnext=Hproblem+∑ihiσizH_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z

    이를 통해 이전에 발견된 좋은 해 근처에서 시작할 수 있어, 효과적으로 "양자 지역 탐색" 형태를 수행합니다

  5. 수렴: 해의 품질이 안정화되거나 최대 반복 횟수에 도달할 때까지 반복합니다

핵심 장점: 각 반복은 매개변수 공간을 맹목적으로 탐색해야 하는 변분 방법과 달리, 이전 측정의 정보를 통합하여 최적 해를 향해 의미 있는 진전을 이룹니다.

통합 고전적 후처리​

양자 최적화가 수렴된 후, Iskay는 고전적 지역 탐색 후처리를 수행합니다:

  • 비트 플립 탐색: 측정된 최선의 해에서 비트를 체계적으로 또는 무작위로 뒤집습니다
  • 에너지 평가: 수정된 각 해에 대해 C(x)C(x)를 계산합니다
  • 탐욕적 선택: 비용 함수를 낮추는 개선을 수락합니다
  • 다중 패스: 여러 번의 패스를 수행합니다(postprocessing_level로 제어)

이 하이브리드 접근 방식은 하드웨어 불완전성과 읽기 오류로 인한 비트 플립 오류를 보상하여, 잡음이 많은 양자 장치에서도 고품질의 해를 보장합니다.

현재 하드웨어에서 bf-DCQO가 뛰어난 이유​

bf-DCQO 알고리즘은 오늘날의 중간 규모 잡음 양자(NISQ) 장치에서 뛰어난 성능을 발휘하도록 특별히 설계되었습니다 [1]:

  1. 오류 복원력: Gate가 적을수록(10배 감소) 오류 누적이 극적으로 줄어듭니다
  2. 오류 완화 불필요: 알고리즘의 고유한 효율성으로 인해 비용이 많이 드는 오류 완화 기술이 필요 없습니다 [1]
  3. 확장성: 직접 Qubit 매핑으로 최대 156개의 Qubit(156개의 이진 변수) 문제를 처리할 수 있습니다 [1]
  4. 검증된 성능: 벤치마크 MaxCut 및 HUBO 인스턴스에서 100% 근사 비율을 달성합니다 [1]

이제 시장 분할 문제에서 이 강력한 알고리즘을 실제로 확인해 봅시다!

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

bf-DCQO 알고리즘은 대상 Backend에 맞게 특별히 설계된 반단열 항을 포함한 얕은 양자 Circuit을 생성하여 Circuit 최적화를 자동으로 처리합니다.

최적화 구성하기​

Iskay Optimizer는 최적화 문제를 효과적으로 풀기 위해 여러 핵심 매개변수가 필요합니다. 각 매개변수와 양자 최적화 과정에서의 역할을 살펴보겠습니다:

필수 매개변수​

매개변수유형설명예시
problemDict[str, float]문자열 키 형식의 QUBO 계수{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_typestr형식 지정: QUBO의 경우 "binary", Ising의 경우 "spin""binary"
backend_namestr대상 양자 장치"ibm_fez"

핵심 개념​

  • 문제 형식: 변수가 시장 배정을 나타내는 이진값(0/1)이므로 "binary"를 사용합니다.
  • Backend 선택: 필요와 컴퓨팅 리소스 인스턴스에 따라 사용 가능한 QPU(예: "ibm_fez") 중에서 선택합니다.
  • QUBO 구조: 문제 딕셔너리에는 수학적 변환에서 도출된 정확한 계수가 포함됩니다.

고급 옵션 (선택 사항)​

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

매개변수유형기본값설명
shotsint10000반복당 양자 측정 횟수 (높을수록 더 정확)
num_iterationsint10알고리즘 반복 횟수 (반복이 많을수록 해 품질이 향상될 수 있음)
use_sessionboolTrue대기 시간 단축을 위해 IBM Session 사용
seed_transpilerintNone재현 가능한 양자 Circuit 컴파일을 위해 설정
direct_qubit_mappingboolFalse가상 Qubit을 물리적 Qubit에 직접 매핑
job_tagsList[str]None작업 추적을 위한 사용자 정의 태그
preprocessing_levelint0문제 전처리 강도 (0-3) - 아래 세부 정보 참조
postprocessing_levelint2해 정제 수준 (0-2) - 아래 세부 정보 참조
transpilation_levelint0Transpiler 최적화 시도 횟수 (0-5) - 아래 세부 정보 참조
transpile_onlyboolFalse전체 실행 없이 Circuit 최적화만 분석

전처리 수준 (0-3): 현재 하드웨어의 결어긋남 시간에 맞지 않는 더 큰 문제에 특히 중요합니다. 전처리 수준이 높을수록 문제 트랜스파일레이션의 근사화를 통해 더 얕은 Circuit 깊이를 달성합니다:

  • 레벨 0: 정확하지만 더 긴 Circuit
  • 레벨 1: 정확도와 근사화 간의 좋은 균형으로, 최저 10 백분위수의 각도를 가진 Gate만 제거
  • 레벨 2: 약간 더 높은 근사화로, 최저 20 백분위수의 Gate를 제거하고 트랜스파일레이션에서 approximation_degree=0.95 사용
  • 레벨 3: 최대 근사화 수준으로, 최저 30 백분위수의 Gate를 제거하고 approximation_degree=0.90 사용

트랜스파일레이션 수준 (0-5): 양자 Circuit 컴파일을 위한 고급 Transpiler 최적화 시도를 제어합니다. 이로 인해 고전적 오버헤드가 증가할 수 있으며, 경우에 따라 Circuit 깊이가 변경되지 않을 수도 있습니다. 기본값 2는 일반적으로 가장 작은 Circuit을 생성하면서도 비교적 빠릅니다.

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

후처리 수준 (0-2): 서로 다른 수의 지역 탐색 탐욕 패스를 통해 비트 플립 오류를 보정하는 고전적 최적화 양을 제어합니다:

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

트랜스파일 전용 모드: 전체 양자 알고리즘 실행 없이 Circuit 최적화를 분석하려는 사용자에게 이제 제공됩니다.

사용자 지정 구성 예시​

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

custom_options = {
    "shots": 15_000,                                        # Higher shot count for better statistics
    "num_iterations": 12,                                   # More iterations for solution refinement
    "preprocessing_level": 1,                               # Light preprocessing for problem simplification
    "postprocessing_level": 2,                              # Maximum postprocessing for solution quality
    "transpilation_level": 3,                               # Using higher transpilation level for circuit optimization
    "seed_transpiler": 42,                                  # Fixed seed for reproducible results
    "job_tags": ["market_split"]                            # Custom tracking tags
}

이 튜토리얼에서는 대부분의 기본 매개변수를 유지하고 편향 필드 반복 횟수만 변경합니다:

# 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 프리미티브를 사용하여 실행하기​

이제 IBM Quantum 하드웨어에서 실행하기 위해 문제를 제출합니다. bf-DCQO 알고리즘은 다음을 수행합니다:

  1. 반단열 항을 포함한 얕은 양자 Circuit 구성
  2. 편향 필드 최적화로 약 10회 반복 실행
  3. 지역 탐색을 통한 고전적 후처리 수행
  4. 최적 시장 배정 반환
# 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 {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!")

Step 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("  ...")

솔루션 검증​

이제 양자 솔루션이 시장 분할 제약 조건을 만족하는지 검증합니다. 검증 과정에서는 다음을 확인합니다:

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

  • 각 제품 ii에 대해, 지역 A의 실제 판매량을 계산합니다: (Ax)i(Ax)_i
  • 이를 목표 판매량 bib_i와 비교합니다
  • 위반은 절대 차이입니다: ∣(Ax)i−bi∣|(Ax)_i - b_i|
  • 실현 가능한 솔루션은 모든 제품에 대해 위반이 없는 경우입니다

예상 결과:

  • 이상적인 경우: 총 위반 = 0 (모든 제약 조건이 완벽히 만족됨)
    • 지역 A는 제품 1의 1002단위, 제품 2의 879단위, 제품 3의 1040단위를 정확히 받습니다
    • 지역 B는 나머지 단위를 받습니다 (각각 1002, 879, 1040)
  • 좋은 경우: 총 위반이 작음 (준최적 솔루션)
  • 좋지 않은 경우: 큰 위반은 솔루션이 비즈니스 요건을 충족하지 못함을 나타냄

검증 함수는 다음을 계산합니다:

  1. 각 지역의 제품별 실제 판매량
  2. 각 제품의 제약 조건 위반
  3. 지역 간 시장 분배
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||Ax - b||^2와 같습니다
  • Cost = 0은 완벽한 제약 조건 만족을 나타냄
  • 높은 비용 값은 더 큰 제약 조건 위반을 나타냄

결론​

달성한 것​

이 튜토리얼에서 우리는 성공적으로 다음을 수행했습니다:

  1. 실제 최적화 문제 로드: QOBLIB 벤치마크 라이브러리에서 어려운 시장 분할 인스턴스 획득 [2]
  2. QUBO 형식으로 변환: 제약이 있는 문제를 비제약 이차 공식으로 변환 [3]
  3. 고급 양자 알고리즘 활용: 반단열 항을 포함한 Kipu Quantum의 bf-DCQO 알고리즘 사용 [1]
  4. 최적 솔루션 획득: 모든 제약 조건을 만족하는 실현 가능한 솔루션 발견

핵심 요점​

알고리즘 혁신: bf-DCQO 알고리즘은 중요한 발전을 나타냅니다 [1]:

  • 디지털 양자 어닐링보다 10배 적은 Gate
  • 변분 방법의 약 100회 대신 약 10회 반복
  • Circuit 효율성을 통한 내장된 오류 복원력

반단열 항: 기저 상태 충실도를 유지하면서 빠른 양자 진화를 가능하게 하여, 오늘날의 노이즈가 있는 하드웨어에서 양자 최적화를 실용적으로 만듭니다 [1].

바이어스 필드 안내: 반복적인 바이어스 필드 접근 방식은 각 반복이 이전에 찾은 좋은 솔루션 근처에서 시작할 수 있게 하여, 양자 강화 지역 탐색의 형태를 제공합니다 [1].

다음 단계​

더 깊은 이해와 추가 탐구를 위해:

  1. 다른 인스턴스 시도: 다양한 크기의 다른 QOBLIB 인스턴스 실험
  2. 매개변수 조정: num_iterations, preprocessing_level, postprocessing_level 조정
  3. 고전적 방법과 비교: 고전적 최적화 솔버와 성능 비교
  4. 다른 전략 시도: 문제에 더 나은 인코딩을 찾거나 HUBO로 공식화 시도 (가능한 경우)
  5. 자신의 도메인에 적용: QUBO/HUBO 공식화 기법을 자신의 최적화 문제에 적용

참고문헌​

[1] IBM Quantum. "Kipu Quantum Optimization." IBM Quantum Documentation.

[2] QOBLIB - Quantum Optimization Benchmarking Library. Zuse Institute Berlin (ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] Glover, F., Kochenberger, G., & Du, Y. (2019). "Quantum bridge analytics I: a tutorial on formulating and using QUBO models." 4OR: A Quarterly Journal of Operations Research, 17(4), 335-371.

[4] Lodi, A., Tramontani, A., & Weninger, K. (2023). "The Intractable Decathlon: Benchmarking Hard Combinatorial Problems." INFORMS Journal on Computing.

출처: IBM Quantum docs — 2026년 5월 15일 업데이트
doQumentation의 영어 버전 — 2026년 5월 15일 업데이트
이 번역은 2026년 4월 9일의 영어 버전을 기반으로 합니다
사이트 또는 번역 문제?콘텐츠 문제? IBM Quantum docs에서 편집