Rozwiązywanie problemu podziału rynku za pomocą Iskay Quantum Optimizer firmy Kipu Quantum

Uwaga

Qiskit Functions to funkcja eksperymentalna dostępna wyłącznie dla użytkowników planów IBM Quantum® Premium Plan, Flex Plan oraz On-Prem (za pośrednictwem IBM Quantum Platform API). Funkcja ta jest w fazie podglądu i może ulec zmianie.

Szacowane zużycie zasobów: 20 sekund na procesorze Heron r2. (UWAGA: To jedynie szacunek. Twój czas działania może się różnić.)

Tło

Ten samouczek demonstruje, jak rozwiązać problem podziału rynku przy użyciu Iskay quantum optimizer firmy Kipu Quantum [1]. Problem podziału rynku reprezentuje rzeczywiste wyzwanie alokacji zasobów, w którym rynki muszą zostać podzielone na zrównoważone regiony sprzedaży spełniające dokładne cele popytowe.

Wyzwanie podziału rynku

Problem podziału rynku pozornie wydaje się prosty, lecz stanowi poważne obliczeniowe wyzwanie w dziedzinie alokacji zasobów. Wyobraź sobie firmę sprzedającą $m$ produktów na $n$ różnych rynkach, gdzie każdy rynek kupuje określony zestaw produktów (reprezentowany przez kolumny macierzy $A$). Celem biznesowym jest podział tych rynków na dwa zrównoważone regiony sprzedaży, tak aby każdy region otrzymał dokładnie połowę łącznego popytu na każdy produkt.

Sformułowanie matematyczne:

Szukamy binarnego wektora przypisania $x$, gdzie:

• $x_j = 1$ przypisuje rynek $j$ do Regionu A
• $x_j = 0$ przypisuje rynek $j$ do Regionu B
• Warunek $Ax = b$ musi być spełniony, gdzie $b$ reprezentuje docelową sprzedaż (zazwyczaj połowę łącznego popytu na produkt)

Funkcja kosztu:

Aby rozwiązać ten problem, minimalizujemy kwadrat naruszenia warunków ograniczających:

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

gdzie:

• $A_{ij}$ reprezentuje sprzedaż produktu $i$ na rynku $j$
• $x_j \in \{0,1\}$ to binarne przypisanie rynku $j$
• $b_i$ to docelowa sprzedaż produktu $i$ w każdym regionie
• Koszt równa się zero dokładnie wtedy, gdy wszystkie warunki są spełnione

Każdy wyraz sumy reprezentuje kwadratowe odchylenie od docelowej sprzedaży dla danego produktu. Po rozwinięciu tej funkcji kosztu otrzymujemy:

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

Ponieważ $b^T b$ jest stałą, minimalizacja $C(x)$ jest równoważna minimalizacji funkcji kwadratowej $x^T A^T A x - 2b^T A x$, co jest dokładnie problemem QUBO (Quadratic Unconstrained Binary Optimization).

Złożoność obliczeniowa:

Pomimo prostej interpretacji biznesowej problem ten wykazuje wyjątkową trudność obliczeniową:

• Niepowodzenie dla małych instancji: Konwencjonalne solwery mieszanoprogramowania całkowitoliczbowego (Mixed Integer Programming) zawodzą już dla instancji z zaledwie siedmioma produktami przy limicie czasu jednej godziny [4]
• Wzrost wykładniczy: Przestrzeń rozwiązań rośnie wykładniczo ($2^n$ możliwych przypisań), co sprawia, że podejścia siłowe są niewykonalne

Ta poważna bariera obliczeniowa, w połączeniu z praktyczną przydatnością w planowaniu terytoriów i alokacji zasobów, sprawia, że problem podziału rynku jest idealnym benchmarkiem dla kwantowych algorytmów optymalizacyjnych [4].

Co wyróżnia podejście Iskay?

Optimizer Iskay wykorzystuje algorytm bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], który stanowi znaczący postęp w optymalizacji kwantowej:

Wydajność Circuit: Algorytm bf-DCQO osiąga znaczną redukcję bramek [1]:

• Do 10 razy mniej bramek splątujących niż Digital Quantum Annealing (DQA)
• Znacznie płytsze Circuit umożliwiają:
  • Mniejszą akumulację błędów podczas wykonywania kwantowego
  • Możliwość rozwiązywania większych problemów na obecnym sprzęcie kwantowym
  • Brak konieczności stosowania technik korekcji błędów

Projekt nie-wariacyjny: W przeciwieństwie do algorytmów wariacyjnych wymagających około 100 iteracji, bf-DCQO zazwyczaj potrzebuje jedynie około 10 iteracji [1]. Osiąga się to dzięki:

• Inteligentnym obliczeniom pola bias na podstawie rozkładów zmierzonych stanów
• Rozpoczynaniu każdej iteracji od stanu energetycznego bliskiego poprzedniemu rozwiązaniu
• Zintegrowanemu klasycznemu przetwarzaniu końcowemu z lokalnym przeszukiwaniem

Protokoły kontradiabaytyczne: Algorytm wykorzystuje człony kontradiabatyczne, które tłumią niechciane wzbudzenia kwantowe podczas krótkich czasów ewolucji, umożliwiając systemowi pozostanie blisko stanu podstawowego nawet przy szybkich przejściach [1].

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że masz zainstalowane następujące pakiety:

• 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)

Będziesz również potrzebować dostępu do funkcji Iskay Quantum Optimizer z katalogu Qiskit Functions Catalog.

Konfiguracja

Na początku zaimportuj wszystkie wymagane pakiety do tego samouczka.

# 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")

Konfiguracja poświadczeń IBM Quantum

Zdefiniuj swoje poświadczenia IBM Quantum® Platform. Będziesz potrzebować:

• Token API: Twój 44-znakowy klucz API z IBM Quantum Platform
• Instance CRN: Twój identyfikator instancji IBM Cloud®

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

Krok 1: Odwzorowanie klasycznych danych wejściowych na problem kwantowy

Zaczynamy od odwzorowania naszego klasycznego problemu na reprezentację zgodną z kwantową. Ten krok obejmuje:

1. Połączenie z Iskay Quantum Optimizer
2. Załadowanie i sformułowanie problemu podziału rynku
3. Zrozumienie algorytmu bf-DCQO, który go rozwiąże

Połączenie z Iskay Quantum Optimizer

Zaczynamy od nawiązania połączenia z katalogiem Qiskit Functions Catalog i załadowania Iskay Quantum Optimizer. Iskay Optimizer to funkcja kwantowa dostarczana przez Kipu Quantum, która implementuje algorytm bf-DCQO do rozwiązywania problemów optymalizacyjnych na sprzęcie kwantowym.

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")

Załadowanie i sformułowanie problemu

Zrozumienie formatu danych problemu

Instancje problemu z QOBLIB (Quantum Optimization Benchmarking Library) [2] są przechowywane w prostym formacie tekstowym. Przyjrzyjmy się rzeczywistej zawartości naszej docelowej instancji 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

Struktura formatu:

• Pierwszy wiersz: 3 20

  • 3 = liczba produktów (warunki/wiersze macierzy $A$)
  • 20 = liczba rynków (zmienne/kolumny macierzy $A$)

• Kolejne 3 wiersze: Macierz współczynników $A$ i wektor docelowy $b$

  • Każdy wiersz ma 21 liczb: pierwsze 20 to współczynniki wiersza, ostatnia to wartość docelowa
  • Wiersz 2: 60 92 161 ... 51 | 1002
    • Pierwsze 20 liczb: Ile Produktu 1 sprzedaje każdy z 20 rynków
    • Ostatnia liczba (1002): Docelowa sprzedaż Produktu 1 w jednym regionie
  • Wiersz 3: 176 196 41 ... 46 | 879
    • Sprzedaż Produktu 2 na rynek i wartość docelowa (879)
  • Wiersz 4: 68 68 179 ... 95 | 1040
    • Sprzedaż Produktu 3 na rynek i wartość docelowa (1040)

Interpretacja biznesowa:

• Rynek 0 sprzedaje: 60 jednostek Produktu 1, 176 jednostek Produktu 2, 68 jednostek Produktu 3
• Rynek 1 sprzedaje: 92 jednostki Produktu 1, 196 jednostek Produktu 2, 68 jednostek Produktu 3
• I tak dalej dla wszystkich 20 rynków...
• Cel: Podziel te 20 rynków na dwa regiony, w których każdy region otrzymuje dokładnie 1002 jednostki Produktu 1, 879 jednostek Produktu 2 i 1040 jednostek Produktu 3

Transformacja QUBO

Od warunków ograniczających do QUBO: transformacja matematyczna

Siła optymalizacji kwantowej tkwi w przekształcaniu problemów z warunkami ograniczającymi na nieograniczone formy kwadratowe [4]. W przypadku problemu podziału rynku zamieniamy warunki równości

$Ax = b$

gdzie $x ∈ \{0,1\}^n$, na QUBO poprzez penalizację naruszeń warunków.

Metoda karania: Ponieważ potrzebujemy, aby $Ax = b$ było spełnione dokładnie, minimalizujemy kwadrat naruszenia: $f(x) = ||Ax - b||^2$

Wyrażenie to równa się zero dokładnie wtedy, gdy wszystkie warunki są spełnione. Rozwijając algebraicznie: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Cel QUBO: Ponieważ $b^T b$ jest stałą, nasza optymalizacja staje się: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Kluczowa obserwacja: Ta transformacja jest dokładna, a nie przybliżona. Warunki równości w naturalny sposób przyjmują postać kwadratową bez potrzeby wprowadzania zmiennych pomocniczych ani parametrów kary — co czyni to sformułowanie matematycznie eleganckim i obliczeniowo wydajnym dla solwerów kwantowych [4]. Użyjemy klasy OptimizationProblem do zdefiniowania naszego problemu z warunkami ograniczającymi, a następnie przekonwertujemy go do formatu QUBO za pomocą OptimizationProblemToQubo — obu z pakietu qiskit_addon_opt_mapper. To automatycznie obsługuje transformację opartą na karach.

Implementacja funkcji ładowania danych i konwersji QUBO

Teraz definiujemy trzy funkcje pomocnicze:

1. parse_marketsplit_dat() — parsuje format pliku .dat i wyodrębnia macierze $A$ i $b$
2. fetch_marketsplit_data() — pobiera instancje problemu bezpośrednio z repozytorium 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

Załadowanie instancji problemu

Teraz ładujemy konkretną instancję problemu ms_03_200_177.dat z QOBLIB [2]. Ta instancja zawiera:

• 3 produkty (warunki ograniczające)
• 20 rynków (binarne zmienne decyzyjne)
• Ponad milion możliwych przypisań rynków do zbadania ($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: 2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Konwersja do formatu QUBO

Teraz przekształcamy ograniczony problem optymalizacyjny do formatu 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())}")

Konwersja QUBO do formatu Iskay

Teraz musimy przekonwertować obiekt QUBO do formatu słownikowego wymaganego przez Iskay Optimizer firmy Kipu Quantum.

Argumenty problem i problem_type kodują problem optymalizacyjny w postaci

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

gdzie

$$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}$$

• Wybierając problem_type = "binary", określasz, że funkcja kosztu jest w formacie binary, co oznacza, że $D = \{0, 1\}^{n}$, czyli funkcja kosztu jest zapisana w sformułowaniu QUBO/HUBO.
• Z kolei wybierając problem_type = "spin", funkcja kosztu jest zapisana w sformułowaniu Isinga, gdzie $D = \{-1, 1\}^{n}$.

Współczynniki problemu powinny być zakodowane w słowniku w następujący sposób:

$$\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}$$

Zwróć uwagę, że klucze słownika muszą być ciągami znaków zawierającymi prawidłową krotkę niepowtarzających się liczb całkowitych. Dla problemów binarnych wiemy, że:

$$x_i^2 = x_i$$

dla $i=j$ (ponieważ $x_i \in \{0,1\}$ oznacza $x_i \cdot x_i = x_i$). Tak więc w swoim sformułowaniu QUBO, jeśli masz zarówno liniowe składniki $b_i x_i$, jak i diagonalne składniki kwadratowe $c_{i,i} x_i^2$, te wyrazy muszą być połączone w jeden współczynnik liniowy:

Łączny współczynnik liniowy dla zmiennej $x_i$: $b_i + c_{i,i}$

Oznacza to:

• Wyrazy liniowe jak "(i, )" zawierają: oryginalny współczynnik liniowy + diagonalny współczynnik kwadratowy
• Diagonalne wyrazy kwadratowe jak "(i, i)" NIE powinny pojawiać się w końcowym słowniku
• Tylko pozadiagonalne wyrazy kwadratowe jak "(i, j)" gdzie $i \neq j$ powinny być uwzględnione jako osobne wpisy

Przykład: Jeśli twoje QUBO ma $3x_1 + 2x_1^2 + 4x_1 x_2$, słownik Iskay powinien zawierać:

• "(0, )": 5.0 (łącząc $3 + 2 = 5$)
• "(0, 1)": 4.0 (wyraz pozadiagonalny)

NIE osobne wpisy dla "(0, )": 3.0 i "(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!")

Zrozumienie algorytmu bf-DCQO

Zanim uruchomimy optymalizację, poznajmy zaawansowany algorytm kwantowy napędzający Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Czym jest bf-DCQO?

bf-DCQO opiera się na ewolucji czasowej układu kwantowego, gdzie rozwiązanie problemu jest zakodowane w stanie podstawowym (stanie o najniższej energii) końcowego Hamiltonianu kwantowego [1]. Algorytm rozwiązuje fundamentalne wyzwanie optymalizacji kwantowej:

Wyzwanie: Tradycyjne adiabatyczne komputery kwantowe wymagają bardzo powolnej ewolucji, aby zachować warunki stanu podstawowego zgodnie z twierdzeniem adiabatycznym. Wymaga to coraz głębszych Circuit kwantowych wraz ze wzrostem złożoności problemu, co prowadzi do większej liczby operacji bramkowych i akumulacji błędów.

Rozwiązanie: bf-DCQO używa protokołów kontradiabatycznych, które umożliwiają szybką ewolucję przy zachowaniu wierności stanu podstawowego, znacznie redukując głębokość Circuit.

Ramy matematyczne

Algorytm minimalizuje funkcję kosztu postaci:

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

gdzie $D = \{0,1\}^n$ dla zmiennych binarnych i:

$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}$

Dla naszego problemu podziału rynku funkcja kosztu wynosi:

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

Rola członów kontradiabatycznych

Człony kontradiabatyczne to dodatkowe wyrazy wprowadzane do zależnego od czasu Hamiltonianu, które tłumią niechciane wzbudzenia podczas ewolucji kwantowej. Oto dlaczego są kluczowe:

W adiabatycznej optymalizacji kwantowej ewoluujemy układ zgodnie z zależnym od czasu Hamiltonianem:

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

gdzie $H_{\text{problem}}$ koduje nasz problem optymalizacyjny. Aby zachować stan podstawowy podczas szybkiej ewolucji, dodajemy człony kontradiabatyczne:

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

Te człony kontradiabatyczne spełniają następujące funkcje:

1. Tłumienie niechcianych przejść: Zapobiegają przeskakiwaniu stanu kwantowego do stanów wzbudzonych podczas szybkiej ewolucji
2. Umożliwiają krótsze czasy ewolucji: Pozwalają nam osiągnąć stan końcowy znacznie szybciej bez naruszania adiabatyczności
3. Redukują głębokość Circuit: Krótsza ewolucja prowadzi do mniejszej liczby bramek i mniejszej liczby błędów

Praktyczny wpływ jest dramatyczny: bf-DCQO używa do 10 razy mniej bramek splątujących niż Digital Quantum Annealing [1], co czyni go praktycznym dla dzisiejszego zaszumionego sprzętu kwantowego.

Iteracyjna optymalizacja z polem bias

W przeciwieństwie do algorytmów wariacyjnych, które optymalizują parametry Circuit przez wiele iteracji, bf-DCQO stosuje podejście prowadzone przez pole bias, które zbiega w około 10 iteracjach [1]:

Proces iteracyjny:

1. Początkowa ewolucja kwantowa: Rozpoczęcie od Circuit kwantowego implementującego protokół ewolucji kontradiabatycznej

2. Pomiar: Zmierzenie stanu kwantowego w celu uzyskania rozkładu prawdopodobieństwa nad ciągami bitów

3. Obliczenie pola bias: Analiza statystyk pomiarów i obliczenie optymalnego pola bias $h_i$ dla każdego Qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Następna iteracja: Pole bias modyfikuje Hamiltonian dla następnej iteracji: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Pozwala to na rozpoczynanie blisko poprzednio znalezionego dobrego rozwiązania, skutecznie wykonując formę "kwantowego lokalnego przeszukiwania"

5. Zbieżność: Powtarzaj aż do stabilizacji jakości rozwiązania lub osiągnięcia maksymalnej liczby iteracji

Kluczowa zaleta: Każda iteracja zapewnia znaczący postęp w kierunku optymalnego rozwiązania poprzez włączenie informacji z poprzednich pomiarów, w przeciwieństwie do metod wariacyjnych, które muszą eksplorować przestrzeń parametrów w ciemno.

Zintegrowane klasyczne przetwarzanie końcowe

Po zbieżności optymalizacji kwantowej Iskay wykonuje klasyczne przetwarzanie końcowe metodą lokalnego przeszukiwania:

• Eksploracja bitflip: Systematyczne lub losowe odwracanie bitów w najlepszym zmierzonym rozwiązaniu
• Ocena energii: Obliczenie $C(x)$ dla każdego zmodyfikowanego rozwiązania
• Selekcja zachłanna: Akceptowanie ulepszeń obniżających funkcję kosztu
• Wielokrotne przejścia: Wykonanie kilku przejść (kontrolowanych przez postprocessing_level)

To hybrydowe podejście kompensuje błędy bitflip wynikające z niedoskonałości sprzętu i błędów odczytu, zapewniając wysokiej jakości rozwiązania nawet na zaszumionych urządzeniach kwantowych.

Dlaczego bf-DCQO sprawdza się na obecnym sprzęcie

Algorytm bf-DCQO jest specjalnie zaprojektowany do działania na dzisiejszych urządzeniach kwantowych w skali pośredniej z szumem (NISQ) [1]:

1. Odporność na błędy: Mniej bramek (redukcja 10-krotna) oznacza dramatycznie mniejszą akumulację błędów
2. Brak potrzeby korekcji błędów: Wbudowana wydajność algorytmu eliminuje konieczność stosowania kosztownych technik korekcji błędów [1]
3. Skalowalność: Może obsługiwać problemy z do 156 Qubitami (156 zmiennych binarnych) przy bezpośrednim mapowaniu Qubitów [1]
4. Udowodniona wydajność: Osiąga 100% współczynnik aproksymacji na benchmarkach MaxCut i HUBO [1]

Zobaczmy teraz ten potężny algorytm w akcji na naszym problemie podziału rynku!

Krok 2: Optymalizacja problemu pod kątem wykonania na sprzęcie kwantowym

Algorytm bf-DCQO automatycznie obsługuje optymalizację obwodów, tworząc płytkie obwody kwantowe z wyrazami kontradiabatycznymi zaprojektowanymi specjalnie pod kątem docelowego Backend.

Konfiguracja optymalizacji

Iskay Optimizer wymaga kilku kluczowych parametrów, aby efektywnie rozwiązać twój problem optymalizacyjny. Przyjrzyjmy się każdemu parametrowi i jego roli w procesie optymalizacji kwantowej:

Parametry wymagane

Parametr	Typ	Opis	Przykład
problem	Dict[str, float]	Współczynniki QUBO w formacie kluczy tekstowych	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Specyfikacja formatu: "binary" dla QUBO lub "spin" dla Isinga	"binary"
backend_name	str	Docelowe urządzenie kwantowe	"ibm_fez"

Kluczowe pojęcia

• Format problemu: Używamy "binary", ponieważ nasze zmienne są binarne (0/1), reprezentując przypisania rynkowe.
• Wybór Backend: Wybierz spośród dostępnych QPU (na przykład "ibm_fez") na podstawie swoich potrzeb i instancji zasobów obliczeniowych.
• Struktura QUBO: Nasz słownik problemu zawiera dokładne współczynniki z transformacji matematycznej.

Zaawansowane opcje (opcjonalne)

Iskay oferuje możliwości dostrajania za pomocą parametrów opcjonalnych. Chociaż wartości domyślne sprawdzają się w przypadku większości problemów, możesz dostosować zachowanie do konkretnych wymagań:

Parametr	Typ	Domyślnie	Opis
shots	int	10000	Pomiary kwantowe na iterację (wyższa wartość = większa dokładność)
num_iterations	int	10	Iteracje algorytmu (więcej iteracji może poprawić jakość rozwiązania)
use_session	bool	True	Użyj sesji IBM dla krótszych czasów oczekiwania w kolejce
seed_transpiler	int	None	Ustaw dla odtwarzalnej kompilacji obwodu kwantowego
direct_qubit_mapping	bool	False	Mapuj wirtualne Qubit bezpośrednio na fizyczne Qubit
job_tags	List[str]	None	Niestandardowe tagi do śledzenia zadań
preprocessing_level	int	0	Intensywność wstępnego przetwarzania problemu (0-3) — szczegóły poniżej
postprocessing_level	int	2	Poziom udoskonalenia rozwiązania (0-2) — szczegóły poniżej
transpilation_level	int	0	Próby optymalizacji Transpiler (0-5) — szczegóły poniżej
transpile_only	bool	False	Analiza optymalizacji obwodu bez uruchamiania pełnego wykonania

Poziomy wstępnego przetwarzania (0-3): Szczególnie ważne dla większych problemów, które aktualnie nie mieszczą się w czasach dekoherencji sprzętu. Wyższe poziomy wstępnego przetwarzania osiągają mniejsze głębokości obwodów poprzez aproksymacje w transpilacji problemu:

• Poziom 0: Dokładny, dłuższe obwody
• Poziom 1: Dobry balans między dokładnością a aproksymacją — eliminuje tylko bramki z kątami w najniższym 10. percentylu
• Poziom 2: Nieco wyższa aproksymacja — eliminuje bramki z kątami w najniższym 20. percentylu i używa approximation_degree=0.95 w transpilacji
• Poziom 3: Maksymalny poziom aproksymacji — eliminuje bramki w najniższym 30. percentylu i używa approximation_degree=0.90 w transpilacji

Poziomy transpilacji (0-5): Kontrolują zaawansowane próby optymalizacji Transpiler dla kompilacji obwodu kwantowego. Może to prowadzić do wzrostu narzutu klasycznego i w niektórych przypadkach może nie zmienić głębokości obwodu. Wartość domyślna 2 generalnie prowadzi do najmniejszego obwodu i jest stosunkowo szybka.

• Poziom 0: Optymalizacja rozłożonego obwodu DCQO (layout, routing, scheduling)
• Poziom 1: Optymalizacja PauliEvolutionGate, a następnie rozłożonego obwodu DCQO (max_trials=10)
• Poziom 2: Optymalizacja PauliEvolutionGate, a następnie rozłożonego obwodu DCQO (max_trials=15)
• Poziom 3: Optymalizacja PauliEvolutionGate, a następnie rozłożonego obwodu DCQO (max_trials=20)
• Poziom 4: Optymalizacja PauliEvolutionGate, a następnie rozłożonego obwodu DCQO (max_trials=25)
• Poziom 5: Optymalizacja PauliEvolutionGate, a następnie rozłożonego obwodu DCQO (max_trials=50)

Poziomy postprocessingu (0-2): Kontrolują ilość klasycznej optymalizacji kompensującej błędy bit-flip przy użyciu różnej liczby zachłannych przebiegów lokalnego przeszukiwania:

• Poziom 0: 1 przebieg
• Poziom 1: 2 przebiegi
• Poziom 2: 3 przebiegi

Tryb tylko transpilacji: Dostępny teraz dla użytkowników, którzy chcą analizować optymalizację obwodu bez uruchamiania pełnego wykonania algorytmu kwantowego.

Przykład niestandardowej konfiguracji

Oto jak możesz skonfigurować Iskay z różnymi ustawieniami:

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
}

Na potrzeby tego samouczka zachowamy większość domyślnych parametrów i zmienimy tylko liczbę iteracji pola biasowego:

# 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")

Krok 3: Wykonanie przy użyciu prymitywów Qiskit

Teraz przesyłamy nasz problem do uruchomienia na sprzęcie IBM Quantum. Algorytm bf-DCQO:

1. Skonstruuje płytkie obwody kwantowe z wyrazami kontradiabatycznymi
2. Wykona około 10 iteracji z optymalizacją pola biasowego
3. Przeprowadzi klasyczne przetwarzanie końcowe z lokalnym przeszukiwaniem
4. Zwróci optymalne przypisanie rynkowe

# 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"
)

Monitorowanie statusu zadania

Możesz sprawdzić aktualny status swojego zadania optymalizacyjnego. Możliwe statusy to:

• QUEUED: Zadanie oczekuje w kolejce
• RUNNING: Zadanie jest aktualnie wykonywane na sprzęcie kwantowym
• DONE: Zadanie zakończyło się pomyślnie
• CANCELED: Zadanie zostało anulowane
• ERROR: Zadanie napotkało błąd

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

Oczekiwanie na zakończenie

Ta komórka będzie blokować wykonanie do momentu zakończenia zadania. Proces optymalizacji obejmuje:

• Czas oczekiwania w kolejce (oczekiwanie na dostęp do sprzętu kwantowego)
• Czas wykonania (uruchomienie algorytmu bf-DCQO z około 10 iteracjami)
• Czas przetwarzania końcowego (klasyczne lokalne przeszukiwanie)

Typowe czasy realizacji wynoszą od kilku minut do kilkudziesięciu minut, w zależności od warunków kolejki.

# 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!")

Krok 4: Przetwarzanie końcowe i zwrócenie wyniku w żądanym formacie klasycznym

Teraz przetwarzamy wyniki wykonania kwantowego. Obejmuje to:

• Analizę struktury rozwiązania
• Walidację spełnienia ograniczeń
• Porównanie z podejściami klasycznymi

Analiza wyników

Zrozumienie struktury wyniku

Iskay zwraca kompleksowy słownik wyników zawierający:

• solution: Słownik mapujący indeksy zmiennych na ich optymalne wartości (0 lub 1)
• solution_info: Szczegółowe informacje zawierające:
  • bitstring: Optymalne przypisanie jako ciąg binarny
  • cost: Wartość funkcji celu (powinna wynosić 0 dla idealnego spełnienia ograniczeń)
  • mapping: Sposób mapowania pozycji bitstring na zmienne problemu
  • seed_transpiler: Ziarno użyte dla odtwarzalności
• prob_type: Czy rozwiązanie jest w formacie binarnym czy spinowym

Przyjrzyjmy się rozwiązaniu zwróconemu przez optymalizator kwantowy.

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

Walidacja rozwiązania

Teraz sprawdzamy, czy rozwiązanie kwantowe spełnia ograniczenia podziału rynku. Proces walidacji sprawdza:

Czym jest naruszenie ograniczenia?

• Dla każdego produktu $i$ obliczamy rzeczywistą sprzedaż w Regionie A: $(Ax)_i$
• Porównujemy to z docelową sprzedażą $b_i$
• Naruszenie to bezwzględna różnica: $|(Ax)_i - b_i|$
• Rozwiązanie dopuszczalne ma zerowe naruszenia dla wszystkich produktów

Czego oczekujemy:

• Przypadek idealny: Łączne naruszenie = 0 (wszystkie ograniczenia idealnie spełnione)
  • Region A otrzymuje dokładnie 1002 jednostki Produktu 1, 879 jednostek Produktu 2 i 1040 jednostek Produktu 3
  • Region B otrzymuje pozostałe jednostki (odpowiednio 1002, 879 i 1040)
• Dobry przypadek: Łączne naruszenie jest małe (rozwiązanie bliskie optymalnemu)
• Słaby przypadek: Duże naruszenia wskazują, że rozwiązanie nie spełnia wymagań biznesowych

Funkcja walidacji obliczy:

1. Rzeczywistą sprzedaż na produkt w każdym regionie
2. Naruszenia ograniczeń dla każdego produktu
3. Rozkład rynku między regionami

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)

Interpretacja wyników walidacji

Wyniki walidacji pokazują, czy Optymalizator Kwantowy znalazł rozwiązanie dopuszczalne. Przyjrzyjmy się następującym aspektom:

Sprawdzenie dopuszczalności:

• is_feasible = True oznacza, że rozwiązanie idealnie spełnia wszystkie ograniczenia (łączne naruszenie = 0)
• is_feasible = False oznacza, że niektóre ograniczenia są naruszone

Analiza sprzedaży:

• Porównaj sprzedaż docelową z rzeczywistą dla każdego produktu
• Dla idealnego rozwiązania: Rzeczywista = Docelowa dla wszystkich produktów w obu regionach
• Różnica wskazuje, jak blisko jesteśmy pożądanego podziału rynku

Rozkład rynku:

• Pokazuje, ile rynków jest przypisanych do każdego regionu
• Nie ma wymogu równej liczby rynków — ważne jest jedynie spełnienie celów sprzedażowych

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")

Ocena jakości rozwiązania

Na podstawie powyższych wyników walidacji możemy ocenić jakość rozwiązania kwantowego:

Jeśli is_feasible = True (łączne naruszenie = 0):

• Optymalizator Kwantowy z powodzeniem znalazł optymalne rozwiązanie
• Wszystkie ograniczenia biznesowe są idealnie spełnione
• Demonstruje to przewagę kwantową nad problemem, z którym klasyczne solwery mają trudności [4]

Jeśli is_feasible = False (łączne naruszenie > 0):

• Rozwiązanie jest bliskie optymalnemu, ale niedoskonałe
• Małe naruszenia mogą być w praktyce akceptowalne
• Rozważ dostosowanie parametrów optymalizatora:
  • Zwiększ num_iterations dla większej liczby przebiegów optymalizacji
  • Zwiększ postprocessing_level dla większego udoskonalania klasycznego
  • Zwiększ shots dla lepszej statystyki pomiarów

Interpretacja funkcji kosztu:

• Wartość cost z solution_info równa się $||Ax - b||^2$
• Koszt = 0 oznacza idealne spełnienie ograniczeń
• Wyższe wartości kosztu wskazują na większe naruszenia ograniczeń

Podsumowanie

Co osiągnęliśmy

W tym samouczku z powodzeniem:

1. Załadowaliśmy rzeczywisty problem optymalizacyjny: Pobraliśmy wymagający przypadek podziału rynku z biblioteki wzorcowej QOBLIB [2]
2. Przekształciliśmy do formatu QUBO: Zamieniliśmy problem z ograniczeniami na bezograniczeniową formulację kwadratową [3]
3. Wykorzystaliśmy zaawansowane algorytmy kwantowe: Użyliśmy algorytmu bf-DCQO firmy Kipu Quantum z wyrazami kontradiabatycznymi [1]
4. Uzyskaliśmy optymalne rozwiązania: Znaleźliśmy rozwiązania dopuszczalne spełniające wszystkie ograniczenia

Kluczowe wnioski

Innowacja algorytmiczna: Algorytm bf-DCQO stanowi znaczący postęp [1]:

• 10 razy mniej bramek niż cyfrowe wyżarzanie kwantowe
• Około 10 iteracji zamiast około 100 dla metod wariantowych
• Wbudowana odporność na błędy dzięki wydajności obwodów

Wyrazy kontradiabatyczne: Umożliwiają szybką ewolucję kwantową przy zachowaniu wierności stanu podstawowego, dzięki czemu optymalizacja kwantowa staje się praktyczna na dzisiejszym zakłóconym sprzęcie [1].

Prowadzenie polem biasowym: Iteracyjne podejście z polem biasowym pozwala każdej iteracji startować blisko wcześniej znalezionych dobrych rozwiązań, zapewniając formę kwantowo-ulepszonego lokalnego przeszukiwania [1].

Kolejne kroki

Aby pogłębić swoje rozumienie i zbadać dalsze możliwości:

1. Wypróbuj różne instancje: Eksperymentuj z innymi instancjami QOBLIB różnych rozmiarów
2. Dostrajaj parametry: Dostosowuj num_iterations, preprocessing_level, postprocessing_level
3. Porównaj z klasycznym podejściem: Porównaj z klasycznymi solwerami optymalizacyjnymi
4. Wypróbuj różne strategie: Spróbuj znaleźć lepsze kodowanie dla problemu lub sformułuj go jako HUBO (jeśli możliwe)
5. Zastosuj w swojej dziedzinie: Dostosuj techniki formulacji QUBO/HUBO do własnych problemów optymalizacyjnych

Odniesienia

[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.