Rezolvă problema Market Split cu Iskay Quantum Optimizer de la Kipu Quantum

Notă

Funcțiile Qiskit sunt o funcționalitate experimentală disponibilă doar pentru utilizatorii IBM Quantum® Premium Plan, Flex Plan și On-Prem (prin IBM Quantum Platform API) Plan. Acestea se află în stadiu de previzualizare și pot fi modificate.

Estimare de utilizare: 20 de secunde pe un procesor Heron r2. (NOTĂ: Aceasta este doar o estimare. Timpul tău de rulare poate varia.)

Fundal

Acest tutorial demonstrează cum să rezolvi problema Market Split folosind Iskay quantum optimizer de la Kipu Quantum [1]. Problema Market Split reprezintă o provocare reală de alocare a resurselor, în care piețele trebuie împărțite în regiuni de vânzare echilibrate pentru a îndeplini exact obiectivele de cerere.

Provocarea Market Split

Problema Market Split prezintă o provocare deceptiv de simplă, dar computațional formidabilă în alocarea resurselor. Imaginează-ți o companie cu $m$ produse vândute pe $n$ piețe diferite, unde fiecare piață achiziționează un pachet specific de produse (reprezentat de coloanele matricei $A$). Obiectivul de afaceri este de a împărți aceste piețe în două regiuni de vânzare echilibrate, astfel încât fiecare regiune să primească exact jumătate din cererea totală pentru fiecare produs.

Formulare matematică:

Căutăm un vector binar de atribuire $x$, unde:

• $x_j = 1$ atribuie piața $j$ Regiunii A
• $x_j = 0$ atribuie piața $j$ Regiunii B
• Constrângerea $Ax = b$ trebuie satisfăcută, unde $b$ reprezintă vânzările țintă (de obicei jumătate din cererea totală per produs)

Funcția de cost:

Pentru a rezolva această problemă, minimizăm violarea constrângerii la pătrat:

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

unde:

• $A_{ij}$ reprezintă vânzările produsului $i$ pe piața $j$
• $x_j \in \{0,1\}$ este atribuirea binară a pieței $j$
• $b_i$ este vânzările țintă pentru produsul $i$ în fiecare regiune
• Costul este zero exact atunci când toate constrângerile sunt satisfăcute

Fiecare termen din sumă reprezintă deviația la pătrat față de vânzările țintă pentru un anumit produs. Când extindem această funcție de cost, obținem:

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

Deoarece $b^T b$ este o constantă, minimizarea $C(x)$ este echivalentă cu minimizarea funcției pătratice $x^T A^T A x - 2b^T A x$, care este exact o problemă QUBO (Quadratic Unconstrained Binary Optimization).

Complexitate computațională:

În ciuda interpretării sale de afaceri simple, această problemă prezintă o intractabilitate computațională remarcabilă:

• Eșec la scară mică: Soluționarii convenționali de Mixed Integer Programming eșuează pe instanțe cu doar șapte produse, cu un timeout de o oră [4]
• Creștere exponențială: Spațiul soluțiilor crește exponențial ($2^n$ atribuiri posibile), făcând abordările brute force infezabile

Această barieră computațională severă, combinată cu relevanța sa practică pentru planificarea teritoriilor și alocarea resurselor, face din problema Market Split un benchmark ideal pentru algoritmii de optimizare cuantică [4].

Ce face abordarea Iskay unică?

Optimizatorul Iskay folosește algoritmul bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], care reprezintă un progres semnificativ în optimizarea cuantică:

Eficiența Circuit-ului: Algoritmul bf-DCQO realizează o reducere remarcabilă a porților [1]:

• Până la de 10 ori mai puține porți de entanglement față de Digital Quantum Annealing (DQA)
• Circuit-urile semnificativ mai puțin adânci permit:
  • Mai puțină acumulare de erori în timpul execuției cuantice
  • Posibilitatea de a aborda probleme mai mari pe hardware-ul cuantic actual
  • Fără necesitatea tehnicilor de atenuare a erorilor

Design non-variațional: Spre deosebire de algoritmii variaționali care necesită aproximativ 100 de iterații, bf-DCQO necesită de obicei doar aproximativ 10 iterații [1]. Acest lucru se realizează prin:

• Calcule inteligente ale câmpului de bias din distribuțiile de stare măsurate
• Pornirea fiecărei iterații dintr-o stare de energie apropiată de soluția anterioară
• Post-procesare clasică integrată cu căutare locală

Protocoale contradiabatice: Algoritmul încorporează termeni contradiabatici care suprimă excitațiile cuantice nedorite în timpul evoluțiilor scurte, permițând sistemului să rămână aproape de starea fundamentală chiar și cu tranziții rapide [1].

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalate următoarele:

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

Va trebui, de asemenea, să obții acces la funcția Iskay Quantum Optimizer din Catalogul Qiskit Functions.

Configurare

Mai întâi, importă toate pachetele necesare pentru acest tutorial.

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

Configurează acreditivele IBM Quantum

Definește-ți acreditivele pentru IBM Quantum® Platform. Vei avea nevoie de:

• Token API: Cheia ta API de 44 de caractere din IBM Quantum Platform
• Instance CRN: Identificatorul instanței tale IBM Cloud®

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

Pasul 1: Maparea intrărilor clasice la o problemă cuantică

Începem prin maparea problemei noastre clasice la o reprezentare compatibilă cuantic. Acest pas implică:

1. Conectarea la Iskay Quantum Optimizer
2. Încărcarea și formularea problemei Market Split
3. Înțelegerea algoritmului bf-DCQO care o va rezolva

Conectează-te la Iskay Quantum Optimizer

Începem prin stabilirea unei conexiuni la Qiskit Functions Catalog și încărcarea Iskay Quantum Optimizer. Iskay Optimizer este o funcție cuantică furnizată de Kipu Quantum care implementează algoritmul bf-DCQO pentru rezolvarea problemelor de optimizare pe hardware cuantic.

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

Încarcă și formulează problema

Înțelege formatul datelor problemei

Instanțele de probleme din QOBLIB (Quantum Optimization Benchmarking Library) [2] sunt stocate într-un format text simplu. Să examinăm conținutul real al instanței noastre țintă 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

Structura formatului:

• Prima linie: 3 20

  • 3 = numărul de produse (constrângeri/rânduri în matricea $A$)
  • 20 = numărul de piețe (variabile/coloane în matricea $A$)

• Următoarele 3 linii: Matricea de coeficienți $A$ și vectorul țintă $b$

  • Fiecare linie are 21 de numere: primele 20 sunt coeficienții rândului, ultimul este ținta
  • Linia 2: 60 92 161 ... 51 | 1002
    • Primele 20 de numere: Cât din Produsul 1 vinde fiecare dintre cele 20 de piețe
    • Ultimul număr (1002): Vânzările țintă pentru Produsul 1 dintr-o regiune
  • Linia 3: 176 196 41 ... 46 | 879
    • Vânzările Produsului 2 per piață și ținta (879)
  • Linia 4: 68 68 179 ... 95 | 1040
    • Vânzările Produsului 3 per piață și ținta (1040)

Interpretare de afaceri:

• Piața 0 vinde: 60 de unități din Produsul 1, 176 de unități din Produsul 2, 68 de unități din Produsul 3
• Piața 1 vinde: 92 de unități din Produsul 1, 196 de unități din Produsul 2, 68 de unități din Produsul 3
• Și așa mai departe pentru toate cele 20 de piețe...
• Obiectiv: Împărți aceste 20 de piețe în două regiuni unde fiecare regiune primește exact 1002 unități din Produsul 1, 879 unități din Produsul 2 și 1040 unități din Produsul 3

Transformare QUBO

De la constrângeri la QUBO: transformarea matematică

Puterea optimizării cuantice constă în transformarea problemelor cu constrângeri în forme pătratice fără constrângeri [4]. Pentru problema Market Split, convertim constrângerile de egalitate

$Ax = b$

unde $x ∈ \{0,1\}^n$, într-un QUBO prin penalizarea violărilor constrângerilor.

Metoda de penalizare: Deoarece avem nevoie ca $Ax = b$ să fie satisfăcut exact, minimizăm violarea la pătrat: $f(x) = ||Ax - b||^2$

Aceasta este zero exact atunci când toate constrângerile sunt satisfăcute. Extinzând algebric: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Obiectivul QUBO: Deoarece $b^T b$ este constant, optimizarea noastră devine: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Observație cheie: Această transformare este exactă, nu aproximativă. Constrângerile de egalitate se transformă natural la pătrat în formă pătratică fără a necesita variabile auxiliare sau parametri de penalizare — făcând această formulare elegant matematică și eficientă computațional pentru soluționarii cuantici [4]. Vom folosi clasa OptimizationProblem pentru a defini problema noastră cu constrângeri, apoi o vom converti în format QUBO folosind OptimizationProblemToQubo, ambele din pachetul qiskit_addon_opt_mapper. Aceasta gestionează automat transformarea bazată pe penalizare.

Implementează funcțiile de încărcare a datelor și conversie QUBO

Definim acum trei funcții utilitare:

1. parse_marketsplit_dat() - Parsează formatul fișierului .dat și extrage matricele $A$ și $b$
2. fetch_marketsplit_data() - Descarcă instanțele de probleme direct din repository-ul 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

Încarcă instanța problemei

Acum încărcăm instanța specifică de problemă ms_03_200_177.dat din QOBLIB [2]. Această instanță are:

• 3 produse (constrângeri)
• 20 de piețe (variabile binare de decizie)
• Peste 1 milion de atribuiri posibile de piețe de explorat ($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"
    )

Convertește în format QUBO

Acum transformăm problema de optimizare cu constrângeri în format 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())}")

Convertește QUBO în formatul Iskay

Acum trebuie să convertim obiectul QUBO în formatul de dicționar cerut de Iskay Optimizer de la Kipu Quantum.

Argumentele problem și problem_type codifică o problemă de optimizare de forma

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

unde

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

• Alegând problem_type = "binary", specifici că funcția de cost este în format binary, adică $D = \{0, 1\}^{n}$, adică funcția de cost este scrisă în formularea QUBO/HUBO.
• Pe de altă parte, alegând problem_type = "spin", funcția de cost este scrisă în formularea Ising, unde $D = \{-1, 1\}^{n}$.

Coeficienții problemei trebuie codificați într-un dicționar după cum urmează:

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

Reține că cheile dicționarului trebuie să fie șiruri care conțin un tuplu valid de numere întregi nerepetate. Pentru problemele binare, știm că:

$$x_i^2 = x_i$$

pentru $i=j$ (deoarece $x_i \in \{0,1\}$ înseamnă $x_i \cdot x_i = x_i$). Deci, în formularea ta QUBO, dacă ai atât contribuții liniare $b_i x_i$, cât și contribuții pătratice diagonale $c_{i,i} x_i^2$, acești termeni trebuie combinați într-un singur coeficient liniar:

Coeficientul liniar total pentru variabila $x_i$: $b_i + c_{i,i}$

Aceasta înseamnă:

• Termenii liniari ca "(i, )" conțin: coeficientul liniar original + coeficientul pătratic diagonal
• Termenii pătratici diagonali ca "(i, i)" NU trebuie să apară în dicționarul final
• Doar termenii pătratici în afara diagonalei ca "(i, j)" unde $i \neq j$ trebuie incluși ca intrări separate

Exemplu: Dacă QUBO-ul tău are $3x_1 + 2x_1^2 + 4x_1 x_2$, dicționarul Iskay ar trebui să conțină:

• "(0, )": 5.0 (combinând $3 + 2 = 5$)
• "(0, 1)": 4.0 (termen în afara diagonalei)

NU intrări separate pentru "(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!")

Înțelege algoritmul bf-DCQO

Înainte de a rula optimizarea, să înțelegem algoritmul cuantic sofisticat care alimentează Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Ce este bf-DCQO?

bf-DCQO se bazează pe evoluția în timp a unui sistem cuantic în care soluția problemei este codificată în starea fundamentală (starea cu cea mai mică energie) a Hamiltonianului cuantic final [1]. Algoritmul abordează o provocare fundamentală în optimizarea cuantică:

Provocarea: Calculul cuantic adiabatic tradițional necesită o evoluție foarte lentă pentru a menține condițiile stării fundamentale conform teoremei adiabatice. Aceasta cere circuit-uri cuantice din ce în ce mai adânci pe măsură ce complexitatea problemei crește, ducând la mai multe operații de porți și erori acumulate.

Soluția: bf-DCQO folosește protocoale contradiabatice pentru a permite o evoluție rapidă menținând în același timp fidelitatea stării fundamentale, reducând dramatic adâncimea circuit-ului.

Cadrul matematic

Algoritmul minimizează o funcție de cost de forma:

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

unde $D = \{0,1\}^n$ pentru variabile binare ș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}$

Pentru problema noastră Market Split, funcția de cost este:

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

Rolul termenilor contradiabatici

Termenii contradiabatici sunt termeni suplimentari introduși în Hamiltonianul dependent de timp care suprimă excitațiile nedorite în timpul evoluției cuantice. Iată de ce sunt esențiali:

În optimizarea cuantică adiabatică, evoluăm sistemul conform unui Hamiltonian dependent de timp:

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

unde $H_{\text{problem}}$ codifică problema noastră de optimizare. Pentru a menține starea fundamentală în timpul evoluției rapide, adăugăm termeni contradiabatici:

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

Acești termeni contradiabatici fac următoarele:

1. Suprimă tranzițiile nedorite: Previn saltul stării cuantice la stări excitate în timpul evoluției rapide
2. Permit timpi de evoluție mai scurți: Ne permit să atingem starea finală mult mai repede fără a viola adiabaticitea
3. Reduc adâncimea circuit-ului: Evoluția mai scurtă duce la mai puține porți și mai puțin erori

Impactul practic este dramatic: bf-DCQO folosește de până la 10 ori mai puține porți de entanglement față de Digital Quantum Annealing [1], făcându-l practic pentru hardware-ul cuantic zgomotos de astăzi.

Optimizarea iterativă cu câmp de bias

Spre deosebire de algoritmii variaționali care optimizează parametrii circuit-ului prin multe iterații, bf-DCQO folosește o abordare ghidată de câmpul de bias care converge în aproximativ 10 iterații [1]:

Procesul de iterație:

1. Evoluția cuantică inițială: Pornește cu un circuit cuantic care implementează protocolul de evoluție contradiabatică

2. Măsurare: Măsoară starea cuantică pentru a obține o distribuție de probabilitate peste bitstringuri

3. Calculul câmpului de bias: Analizează statisticile de măsurare și calculează un câmp de bias optim $h_i$ pentru fiecare qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Iterația următoare: Câmpul de bias modifică Hamiltonianul pentru iterația următoare: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Aceasta permite pornirea aproape de soluția bună găsită anterior, realizând efectiv o formă de „căutare locală cuantică"

5. Convergență: Repetă până când calitatea soluției se stabilizează sau se atinge un număr maxim de iterații

Avantaj cheie: Fiecare iterație aduce progres semnificativ spre soluția optimă prin incorporarea informațiilor din măsurătorile anterioare, spre deosebire de metodele variationale care trebuie să exploreze spațiul de parametri orbește.

Post-procesare clasică integrată

După convergența optimizării cuantice, Iskay efectuează căutare locală clasică post-procesare:

• Explorare bit-flip: Răstoarnă sistematic sau aleatoriu biți în cea mai bună soluție măsurată
• Evaluarea energiei: Calculează $C(x)$ pentru fiecare soluție modificată
• Selecție lacomă: Acceptă îmbunătățiri care reduc funcția de cost
• Treceri multiple: Efectuează mai multe treceri (controlat de postprocessing_level)

Această abordare hibridă compensează erorile bit-flip cauzate de imperfecțiunile hardware-ului și erorile de citire, asigurând soluții de înaltă calitate chiar și pe dispozitive cuantice zgomotoase.

De ce bf-DCQO excelează pe hardware-ul actual

Algoritmul bf-DCQO este proiectat special pentru a excela pe dispozitivele cuantice de scară intermediară zgomotoasă (NISQ) de astăzi [1]:

1. Rezistență la erori: Mai puține porți (reducere de 10 ori) înseamnă dramatic mai puțină acumulare de erori
2. Nu necesită atenuarea erorilor: Eficiența inerentă a algoritmului elimină nevoia de tehnici costisitoare de atenuare a erorilor [1]
3. Scalabilitate: Poate gestiona probleme cu până la 156 de qubiți (156 de variabile binare) cu mapare directă qubit [1]
4. Performanță dovedită: Atinge rate de aproximare de 100% pe instanțele de benchmark MaxCut și HUBO [1]

Acum să vedem acest algoritm puternic în acțiune pe problema noastră Market Split!

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

Algoritmul bf-DCQO gestionează automat optimizarea circuitelor, creând circuite cuantice superficiale cu termeni contradiabatici, concepuți special pentru backend-ul țintă.

Configurează optimizarea

Optimizatorul Iskay necesită câțiva parametri cheie pentru a rezolva eficient problema ta de optimizare. Să examinăm fiecare parametru și rolul său în procesul de optimizare cuantică:

Parametri obligatorii

Parametru	Tip	Descriere	Exemplu
problem	Dict[str, float]	Coeficienții QUBO în format cu chei string	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Specificația formatului: "binary" pentru QUBO sau "spin" pentru Ising	"binary"
backend_name	str	Dispozitivul cuantic țintă	"ibm_fez"

Concepte esențiale

• Formatul problemei: Folosim "binary" deoarece variabilele noastre sunt binare (0/1), reprezentând atribuirile de piețe.
• Selectarea Backend-ului: Alege între QPU-urile disponibile (de exemplu, "ibm_fez") în funcție de nevoile tale și de instanța resurselor de calcul.
• Structura QUBO: Dicționarul nostru de probleme conține coeficienții exacți din transformarea matematică.

Opțiuni avansate (opționale)

Iskay oferă capabilități de ajustare fină prin parametri opționali. Deși valorile implicite funcționează bine pentru majoritatea problemelor, poți personaliza comportamentul pentru cerințe specifice:

Parametru	Tip	Implicit	Descriere
shots	int	10000	Măsurători cuantice per iterație (mai multe = mai precis)
num_iterations	int	10	Iterații ale algoritmului (mai multe iterații pot îmbunătăți calitatea soluției)
use_session	bool	True	Folosește sesiuni IBM pentru timpi de așteptare reduși
seed_transpiler	int	None	Setează pentru compilare reproductibilă a circuitelor cuantice
direct_qubit_mapping	bool	False	Mapează Qubit-urile virtuale direct la Qubit-urile fizice
job_tags	List[str]	None	Etichete personalizate pentru urmărirea joburilor
preprocessing_level	int	0	Intensitatea preprocesării problemei (0-3) - vezi detalii mai jos
postprocessing_level	int	2	Nivelul de rafinare a soluției (0-2) - vezi detalii mai jos
transpilation_level	int	0	Încercările de optimizare ale Transpiler-ului (0-5) - vezi detalii mai jos
transpile_only	bool	False	Analizează optimizarea circuitului fără a rula execuția completă

Niveluri de preprocesare (0-3): Deosebit de importante pentru problemele mai mari care nu pot fi încadrate în timpii de coerență ai hardware-ului. Nivelurile mai înalte de preprocesare obțin adâncimi de circuit mai mici prin aproximări în transpilarea problemei:

• Nivelul 0: Exact, circuite mai lungi
• Nivelul 1: Echilibru bun între acuratețe și aproximare, eliminând doar porțile cu unghiuri în cel mai mic percentil de 10%
• Nivelul 2: Aproximare ușor mai mare, eliminând porțile cu unghiuri în cel mai mic percentil de 20% și folosind approximation_degree=0.95 în transpilare
• Nivelul 3: Nivelul maxim de aproximare, eliminând porțile în cel mai mic percentil de 30% și folosind approximation_degree=0.90 în transpilare

Niveluri de transpilare (0-5): Controlează încercările avansate de optimizare ale Transpiler-ului pentru compilarea circuitelor cuantice. Aceasta poate duce la o creștere a suprasolicitării clasice și, în unele cazuri, s-ar putea să nu schimbe adâncimea circuitului. Valoarea implicită 2 duce în general la cel mai mic circuit și este relativ rapidă.

• Nivelul 0: Optimizarea circuitului DCQO descompus (layout, rutare, planificare)
• Nivelul 1: Optimizarea PauliEvolutionGate și apoi a circuitului DCQO descompus (max_trials=10)
• Nivelul 2: Optimizarea PauliEvolutionGate și apoi a circuitului DCQO descompus (max_trials=15)
• Nivelul 3: Optimizarea PauliEvolutionGate și apoi a circuitului DCQO descompus (max_trials=20)
• Nivelul 4: Optimizarea PauliEvolutionGate și apoi a circuitului DCQO descompus (max_trials=25)
• Nivelul 5: Optimizarea PauliEvolutionGate și apoi a circuitului DCQO descompus (max_trials=50)

Niveluri de postprocesare (0-2): Controlează volumul de optimizare clasică, compensând erorile de inversare de biți cu un număr diferit de treceri greedy ale unei căutări locale:

• Nivelul 0: 1 trecere
• Nivelul 1: 2 treceri
• Nivelul 2: 3 treceri

Modul transpile-only: Acum disponibil pentru utilizatorii care doresc să analizeze optimizarea circuitului fără a rula execuția completă a algoritmului cuantic.

Exemplu de configurare personalizată

Iată cum ai putea configura Iskay cu setări diferite:

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
}

Pentru acest tutorial, vom păstra majoritatea parametrilor impliciți și vom schimba doar numărul de iterații ale câmpului de polarizare:

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

Pasul 3: Execuție folosind primitivele Qiskit

Acum trimitem problema noastră pentru a rula pe hardware-ul cuantic IBM. Algoritmul bf-DCQO va:

1. Construi circuite cuantice superficiale cu termeni contradiabatici
2. Executa aproximativ 10 iterații cu optimizare a câmpului de polarizare
3. Efectua post-procesare clasică cu căutare locală
4. Returna atribuirea optimă a piețelor

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

Monitorizează starea jobului

Poți verifica starea curentă a jobului tău de optimizare. Stările posibile sunt:

• QUEUED: Jobul așteaptă în coadă
• RUNNING: Jobul se execută în prezent pe hardware-ul cuantic
• DONE: Jobul s-a finalizat cu succes
• CANCELED: Jobul a fost anulat
• ERROR: Jobul a întâmpinat o eroare

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

Așteaptă finalizarea

Această celulă va bloca execuția până la finalizarea jobului. Procesul de optimizare include:

• Timp de așteptare în coadă (așteptarea accesului la hardware-ul cuantic)
• Timp de execuție (rularea algoritmului bf-DCQO cu aproximativ 10 iterații)
• Timp de post-procesare (căutare locală clasică)

Timpii tipici de finalizare variază de la câteva minute la zeci de minute, în funcție de condițiile din coadă.

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

Pasul 4: Post-procesarea și returnarea rezultatului în formatul clasic dorit

Acum post-procesăm rezultatele execuției cuantice. Aceasta include:

• Analizarea structurii soluției
• Validarea satisfacerii constrângerilor
• Compararea cu abordările clasice

Analizarea rezultatelor

Înțelegerea structurii rezultatului

Iskay returnează un dicționar de rezultate cuprinzător care conține:

• solution: Un dicționar care mapează indicii variabilelor la valorile lor optime (0 sau 1)
• solution_info: Informații detaliate, inclusiv:
  • bitstring: Atribuirea optimă ca șir binar
  • cost: Valoarea funcției obiectiv (ar trebui să fie 0 pentru satisfacerea perfectă a constrângerilor)
  • mapping: Cum sunt mapate pozițiile din bitstring la variabilele problemei
  • seed_transpiler: Seed-ul folosit pentru reproductibilitate
• prob_type: Dacă soluția este în format binar sau spin

Să examinăm soluția returnată de optimizatorul cuantic.

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

Validarea soluției

Acum validăm dacă soluția cuantică satisface constrângerile problemei Market Split. Procesul de validare verifică:

Ce este o încălcare a constrângerii?

• Pentru fiecare produs $i$, calculăm vânzările reale din Regiunea A: $(Ax)_i$
• Comparăm acest lucru cu vânzările țintă $b_i$
• Încălcarea este diferența absolută: $|(Ax)_i - b_i|$
• O soluție fezabilă are zero încălcări pentru toate produsele

Ce ne așteptăm:

• Cazul ideal: Încălcare totală = 0 (toate constrângerile perfect satisfăcute)
  • Regiunea A primește exact 1002 unități din Produsul 1, 879 unități din Produsul 2 și 1040 unități din Produsul 3
  • Regiunea B primește unitățile rămase (de asemenea 1002, 879 și respectiv 1040)
• Cazul bun: Încălcarea totală este mică (soluție aproape optimă)
• Cazul slab: Încălcările mari indică faptul că soluția nu satisface cerințele de afaceri

Funcția de validare va calcula:

1. Vânzările reale per produs în fiecare regiune
2. Încălcările constrângerilor pentru fiecare produs
3. Distribuția pieței între regiuni

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)

Interpretarea rezultatelor de validare

Rezultatele validării arată dacă Optimizatorul Cuantic a găsit o soluție fezabilă. Să examinăm următoarele:

Verificarea fezabilității:

• is_feasible = True înseamnă că soluția satisface perfect toate constrângerile (încălcare totală = 0)
• is_feasible = False înseamnă că unele constrângeri sunt încălcate

Analiza vânzărilor:

• Compară vânzările Țintă față de cele Reale pentru fiecare produs
• Pentru o soluție perfectă: Reale = Țintă pentru toate produsele în ambele regiuni
• Diferența indică cât de aproape suntem de împărțirea dorită a pieței

Distribuția pieței:

• Arată câte piețe sunt atribuite fiecărei regiuni
• Nu există nicio cerință pentru un număr egal de piețe, ci doar ca țintele de vânzări să fie atinse

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

Evaluarea calității soluției

Pe baza rezultatelor de validare de mai sus, putem evalua calitatea soluției cuantice:

Dacă is_feasible = True (Încălcare totală = 0):

• Optimizatorul Cuantic a găsit cu succes o soluție optimă
• Toate constrângerile de afaceri sunt perfect satisfăcute
• Aceasta demonstrează avantajul cuantic pe o problemă în care solverele clasice întâmpină dificultăți [4]

Dacă is_feasible = False (Încălcare totală > 0):

• Soluția este aproape optimă, dar nu perfectă
• Încălcările mici pot fi acceptabile în practică
• Ia în considerare ajustarea parametrilor optimizatorului:
  • Mărește num_iterations pentru mai multe treceri de optimizare
  • Mărește postprocessing_level pentru mai mult rafinament clasic
  • Mărește shots pentru statistici de măsurare mai bune

Interpretarea funcției de cost:

• Valoarea cost din solution_info este egală cu $||Ax - b||^2$
• Cost = 0 indică satisfacerea perfectă a constrângerilor
• Valorile mai mari ale costului indică încălcări mai mari ale constrângerilor

Concluzie

Ce am realizat

În acest tutorial, am reușit să:

1. Încărcăm o problemă de optimizare reală: Am obținut o instanță dificilă de Market Split din biblioteca de benchmark QOBLIB [2]
2. Transformăm în format QUBO: Am convertit problema cu constrângeri într-o formulare pătratică fără constrângeri [3]
3. Folosim algoritmi cuantici avansați: Am utilizat algoritmul bf-DCQO al Kipu Quantum cu termeni contradiabatici [1]
4. Obținem soluții optime: Am găsit soluții fezabile care satisfac toate constrângerile

Concluzii cheie

Inovație algoritmică: Algoritmul bf-DCQO reprezintă un progres semnificativ [1]:

• De 10 ori mai puține porți decât recoacerea cuantică digitală
• Aproximativ 10 iterații în loc de aproximativ 100 pentru metodele variaționale
• Rezistență intrinsecă la erori prin eficiența circuitului

Termeni contradiabatici: Permit o evoluție cuantică rapidă menținând în același timp fidelitatea stării de bază, făcând optimizarea cuantică practică pe hardware-ul zgomotos de azi [1].

Ghidare prin câmp de polarizare: Abordarea iterativă prin câmp de polarizare permite fiecărei iterații să pornească din apropierea soluțiilor bune găsite anterior, oferind o formă de căutare locală îmbunătățită cuantic [1].

Pași următori

Pentru a-ți aprofunda înțelegerea și a explora mai departe:

1. Încearcă instanțe diferite: Experimentează cu alte instanțe QOBLIB de dimensiuni variate
2. Ajustează parametrii: Modifică num_iterations, preprocessing_level, postprocessing_level
3. Compară cu clasicul: Compară performanța cu solverele de optimizare clasice
4. Încearcă strategii diferite: Caută o codificare mai bună pentru problemă sau formulează-o ca HUBO (dacă este posibil)
5. Aplică în domeniul tău: Adaptează tehnicile de formulare QUBO/HUBO la propriile tale probleme de optimizare

Referințe

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