Řešení problému rozdělení trhu s Iskay Quantum Optimizer od Kipu Quantum

Poznámka

Qiskit Functions jsou experimentální funkce dostupné pouze uživatelům plánů IBM Quantum® Premium Plan, Flex Plan a On-Prem (přes IBM Quantum Platform API). Jsou ve stavu náhledu a mohou se měnit.

Odhadovaná spotřeba: 20 sekund na procesoru Heron r2. (POZNÁMKA: Toto je pouze odhad. Skutečný čas běhu se může lišit.)

Pozadí

Tento tutoriál ukazuje, jak řešit problém rozdělení trhu pomocí Iskay quantum optimizer od Kipu Quantum [1]. Problém rozdělení trhu představuje výzvu alokace zdrojů z reálného světa, kde musí být trhy rozděleny do vyvážených prodejních regionů tak, aby byly splněny přesné cíle poptávky.

Výzva rozdělení trhu

Problém rozdělení trhu představuje zdánlivě jednoduchý, avšak výpočetně náročný problém alokace zdrojů. Uvažuj společnost s $m$ produkty prodávanými na $n$ různých trzích, kde každý trh nakupuje specifický soubor produktů (reprezentovaný sloupci matice $A$). Obchodním cílem je rozdělit tyto trhy do dvou vyvážených prodejních regionů tak, aby každý region dostal přesně polovinu celkové poptávky po každém produktu.

Matematická formulace:

Hledáme binární přiřazovací vektor $x$, kde:

• $x_j = 1$ přiřazuje trh $j$ do Regionu A
• $x_j = 0$ přiřazuje trh $j$ do Regionu B
• Musí být splněna podmínka $Ax = b$, kde $b$ představuje cílové prodeje (typicky polovinu celkové poptávky na produkt)

Účelová funkce:

Pro řešení tohoto problému minimalizujeme čtverec porušení podmínek:

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

kde:

• $A_{ij}$ představuje prodeje produktu $i$ na trhu $j$
• $x_j \in \{0,1\}$ je binární přiřazení trhu $j$
• $b_i$ je cílový prodej produktu $i$ v každém regionu
• Cena je nulová právě tehdy, když jsou splněny všechny podmínky

Každý člen součtu představuje čtverec odchylky od cílových prodejů pro konkrétní produkt. Po rozvinutí účelové funkce dostaneme:

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

Protože $b^T b$ je konstanta, minimalizace $C(x)$ je ekvivalentní minimalizaci kvadratické funkce $x^T A^T A x - 2b^T A x$, což je přesně QUBO (Quadratic Unconstrained Binary Optimization) problém.

Výpočetní složitost:

Navzdory jednoduchému obchodnímu výkladu vykazuje tento problém pozoruhodnou výpočetní neřešitelnost:

• Selhání na malých instancích: Konvenční solvery pro smíšené celočíselné programování selhávají na instancích s pouhými sedmi produkty při časovém limitu jedné hodiny [4]
• Exponenciální růst: Prostor řešení roste exponenciálně ($2^n$ možných přiřazení), takže hrubá síla je neproveditelná

Tato závažná výpočetní bariéra, v kombinaci s praktickou relevancí pro plánování území a alokaci zdrojů, dělá z problému rozdělení trhu ideální benchmark pro kvantové optimalizační algoritmy [4].

Co dělá přístup Iskay jedinečným?

Iskay optimizer používá algoritmus bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], který představuje významný pokrok v kvantové optimalizaci:

Efektivita Circuit: Algoritmus bf-DCQO dosahuje pozoruhodného snížení počtu Gate [1]:

• Až 10krát méně proplétacích Gate než Digital Quantum Annealing (DQA)
• Výrazně mělčí Circuit umožňují:
  • Méně akumulace chyb při kvantovém výpočtu
  • Schopnost řešit větší problémy na současném kvantovém hardwaru
  • Není potřeba technik pro zmírňování chyb

Nevariační návrh: Na rozdíl od variačních algoritmů vyžadujících přibližně 100 iterací, bf-DCQO typicky potřebuje pouze přibližně 10 iterací [1]. Toho je dosaženo pomocí:

• Inteligentních výpočtů bias-field z naměřených distribucí stavů
• Zahájení každé iterace z energetického stavu blízkého předchozímu řešení
• Integrovaného klasického post-processingu s lokálním prohledáváním

Kontradiabatické protokoly: Algoritmus zahrnuje kontradiabatické členy, které potlačují nežádoucí kvantové excitace během krátkých evolučních časů, takže systém může zůstat blízko základního stavu i při rychlých přechodech [1].

Požadavky

Před zahájením tohoto tutoriálu se ujisti, že máš nainstalovány následující balíčky:

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

Také budeš potřebovat přístup k funkci Iskay Quantum Optimizer z katalogu Qiskit Functions.

Nastavení

Nejprve importuj všechny balíčky potřebné pro tento tutoriál.

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

Konfigurace přihlašovacích údajů IBM Quantum

Definuj své přihlašovací údaje pro platformu IBM Quantum®. Budeš potřebovat:

• API Token: Tvůj 44znakový API klíč z IBM Quantum Platform
• Instance CRN: Identifikátor tvé instance IBM Cloud®

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

Krok 1: Mapování klasických vstupů na kvantový problém

Začínáme mapováním klasického problému na reprezentaci kompatibilní s kvantovými počítači. Tento krok zahrnuje:

1. Připojení k Iskay Quantum Optimizer
2. Načtení a formulaci problému rozdělení trhu
3. Pochopení algoritmu bf-DCQO, který ho vyřeší

Připojení k Iskay Quantum Optimizer

Začínáme navázáním spojení s katalogem Qiskit Functions a načtením Iskay Quantum Optimizer. Iskay Optimizer je kvantová funkce poskytovaná Kipu Quantum, která implementuje algoritmus bf-DCQO pro řešení optimalizačních problémů na kvantovém hardwaru.

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

Načtení a formulace problému

Pochopení formátu dat problému

Instance problémů z knihovny QOBLIB (Quantum Optimization Benchmarking Library) [2] jsou uloženy v jednoduchém textovém formátu. Podívejme se na skutečný obsah naší cílové instance 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 formátu:

• První řádek: 3 20

  • 3 = počet produktů (podmínky/řádky matice $A$)
  • 20 = počet trhů (proměnné/sloupce matice $A$)

• Další 3 řádky: Matice koeficientů $A$ a cílový vektor $b$

  • Každý řádek má 21 čísel: prvních 20 jsou koeficienty řádku, poslední je cíl
  • Řádek 2: 60 92 161 ... 51 | 1002
    • Prvních 20 čísel: Kolik produktu 1 prodává každý z 20 trhů
    • Poslední číslo (1002): Cílové prodeje produktu 1 v jednom regionu
  • Řádek 3: 176 196 41 ... 46 | 879
    • Prodeje produktu 2 na trh a cíl (879)
  • Řádek 4: 68 68 179 ... 95 | 1040
    • Prodeje produktu 3 na trh a cíl (1040)

Obchodní interpretace:

• Trh 0 prodává: 60 jednotek produktu 1, 176 jednotek produktu 2, 68 jednotek produktu 3
• Trh 1 prodává: 92 jednotek produktu 1, 196 jednotek produktu 2, 68 jednotek produktu 3
• A tak dále pro všech 20 trhů...
• Cíl: Rozdělit těchto 20 trhů do dvou regionů, kde každý region dostane přesně 1002 jednotek produktu 1, 879 jednotek produktu 2 a 1040 jednotek produktu 3

Transformace QUBO

Od podmínek ke QUBO: matematická transformace

Síla kvantové optimalizace spočívá v transformaci problémů s podmínkami na nekondiciovaný kvadratický tvar [4]. Pro problém rozdělení trhu převádíme podmínky rovnosti

$Ax = b$

kde $x ∈ \{0,1\}^n$, na QUBO penalizací porušení podmínek.

Metoda penalizace: Protože potřebujeme, aby $Ax = b$ platilo přesně, minimalizujeme čtverec porušení: $f(x) = ||Ax - b||^2$

Toto se rovná nule přesně tehdy, když jsou splněny všechny podmínky. Algebraickým rozvinutím: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Cíl QUBO: Protože $b^T b$ je konstanta, naše optimalizace se stává: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Klíčové poznatky: Tato transformace je přesná, nikoli přibližná. Podmínky rovnosti se přirozeně umocní do kvadratické formy bez potřeby pomocných proměnných nebo parametrů penalizace — tato formulace je matematicky elegantní a výpočetně efektivní pro kvantové solvery [4]. Použijeme třídu OptimizationProblem k definici našeho problému s podmínkami a pak ho převedeme do formátu QUBO pomocí OptimizationProblemToQubo, obojí z balíčku qiskit_addon_opt_mapper. Tím se automaticky zpracuje transformace založená na penalizaci.

Implementace funkcí pro načítání dat a konverzi QUBO

Nyní definujeme tři pomocné funkce:

1. parse_marketsplit_dat() — Parsuje formát souboru .dat a extrahuje matice $A$ a $b$
2. fetch_marketsplit_data() — Stahuje instance problémů přímo z repozitáře 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

Načtení instance problému

Nyní načteme konkrétní instanci problému ms_03_200_177.dat z QOBLIB [2]. Tato instance má:

• 3 produkty (podmínky)
• 20 trhů (binární rozhodovací proměnné)
• Více než 1 milion možných přiřazení trhů k prozkoumání ($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"
    )

Konverze do formátu QUBO

Nyní transformujeme problém podmíněné optimalizace do formátu 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())}")

Konverze QUBO do formátu Iskay

Nyní potřebujeme převést objekt QUBO do slovníkového formátu požadovaného Iskay Optimizer od Kipu Quantum.

Argumenty problem a problem_type kódují optimalizační problém ve tvaru

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

kde

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

• Zvolením problem_type = "binary" specifikuješ, že účelová funkce je ve formátu binary, což znamená $D = \{0, 1\}^{n}$, tedy účelová funkce je zapsána ve formulaci QUBO/HUBO.
• Na druhou stranu, zvolením problem_type = "spin" je účelová funkce zapsána v Isingově formulaci, kde $D = \{-1, 1\}^{n}$.

Koeficienty problému by měly být zakódovány ve slovníku takto:

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

Klíče slovníku musí být řetězce obsahující platnou n-tici neopakujících se celých čísel. U binárních problémů víme, že:

$$x_i^2 = x_i$$

pro $i=j$ (protože $x_i \in \{0,1\}$ znamená $x_i \cdot x_i = x_i$). Tedy ve formulaci QUBO, máš-li jak lineární příspěvky $b_i x_i$, tak diagonální kvadratické příspěvky $c_{i,i} x_i^2$, musí být tyto členy sloučeny do jediného lineárního koeficientu:

Celkový lineární koeficient pro proměnnou $x_i$: $b_i + c_{i,i}$

To znamená:

• Lineární členy jako "(i, )" obsahují: původní lineární koeficient + diagonální kvadratický koeficient
• Diagonální kvadratické členy jako "(i, i)" by NEMĚLY ve finálním slovníku figurovat
• Pouze mimodiagonální kvadratické členy jako "(i, j)" kde $i \neq j$ by měly být zahrnuty jako samostatné záznamy

Příklad: Pokud tvoje QUBO obsahuje $3x_1 + 2x_1^2 + 4x_1 x_2$, Iskay slovník by měl obsahovat:

• "(0, )": 5.0 (sloučení $3 + 2 = 5$)
• "(0, 1)": 4.0 (mimodiagonální člen)

NIKOLI samostatné záznamy pro "(0, )": 3.0 a "(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!")

Pochopení algoritmu bf-DCQO

Než spustíme optimalizaci, pochopme sofistikovaný kvantový algoritmus, který pohání Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Co je bf-DCQO?

bf-DCQO je založeno na časové evoluci kvantového systému, kde je řešení problému zakódováno v základním stavu (nejnižší energetický stav) finálního kvantového hamiltoniánu [1]. Algoritmus řeší základní výzvu kvantové optimalizace:

Výzva: Tradiční adiabatické kvantové výpočty vyžadují velmi pomalou evoluci pro zachování podmínek základního stavu podle adiabatické věty. To vyžaduje stále hlubší kvantové Circuit se zvyšující se složitostí problému, vedoucí k více Gate operacím a akumulovaným chybám.

Řešení: bf-DCQO využívá kontradiabatické protokoly pro umožnění rychlé evoluce při zachování věrnosti základního stavu, čímž dramaticky snižuje hloubku Circuit.

Matematický rámec

Algoritmus minimalizuje účelovou funkci ve tvaru:

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

kde $D = \{0,1\}^n$ pro binární proměnné a:

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

Pro náš problém rozdělení trhu je účelová funkce:

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

Role kontradiabatických členů

Kontradiabatické členy jsou dodatečné členy zavedené do časově závislého hamiltoniánu, které potlačují nežádoucí excitace během kvantové evoluce. Zde je důvod, proč jsou klíčové:

V adiabatické kvantové optimalizaci vyvíjíme systém podle časově závislého hamiltoniánu:

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

kde $H_{\text{problem}}$ kóduje náš optimalizační problém. Pro zachování základního stavu během rychlé evoluce přidáme kontradiabatické členy:

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

Tyto kontradiabatické členy dělají toto:

1. Potlačují nežádoucí přechody: Zabraňují kvantovému stavu přeskočit do excitovaných stavů během rychlé evoluce
2. Umožňují kratší evoluční časy: Umožňují dosáhnout finálního stavu mnohem rychleji bez porušení adiabatičnosti
3. Snižují hloubku Circuit: Kratší evoluce vede k méně Gate a menším chybám

Praktický dopad je dramatický: bf-DCQO používá až 10krát méně proplétacích Gate než Digital Quantum Annealing [1], takže je praktický pro dnešní hlučný kvantový hardware.

Iterační optimalizace s bias-field

Na rozdíl od variačních algoritmů, které optimalizují parametry Circuit prostřednictvím mnoha iterací, bf-DCQO používá přístup vedený bias-field, který konverguje přibližně za 10 iterací [1]:

Iterační proces:

1. Počáteční kvantová evoluce: Začni s kvantovým Circuit implementujícím protokol kontradiabatické evoluce

2. Měření: Změř kvantový stav pro získání pravděpodobnostní distribuce nad bitstringy

3. Výpočet bias-field: Analyzuj statistiky měření a vypočítej optimální bias-field $h_i$ pro každý Qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Další iterace: Bias-field modifikuje hamiltonián pro příští iteraci: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   To umožňuje začít blízko předchozího dobrého řešení, efektivně provádějící formu „kvantového lokálního prohledávání"

5. Konvergence: Opakuj, dokud se kvalita řešení nestabilizuje nebo není dosaženo maximálního počtu iterací

Klíčová výhoda: Každá iterace přináší smysluplný pokrok k optimálnímu řešení začleněním informací z předchozích měření, na rozdíl od variačních metod, které musí prostor parametrů prozkoumávat naslepo.

Integrovaný klasický post-processing

Po konvergenci kvantové optimalizace provede Iskay klasické lokální prohledávání jako post-processing:

• Explorace bit-flip: Systematické nebo náhodné přepínání bitů v nejlepším naměřeném řešení
• Vyhodnocení energie: Výpočet $C(x)$ pro každé upravené řešení
• Greedy výběr: Přijímání zlepšení, která snižují účelovou funkci
• Více průchodů: Provádění několika průchodů (řízeno parametrem postprocessing_level)

Tento hybridní přístup kompenzuje chyby bit-flip z hardwarových nedokonalostí a chyby čtení, čímž zajišťuje vysoce kvalitní řešení i na hlučných kvantových zařízeních.

Proč bf-DCQO vyniká na současném hardwaru

Algoritmus bf-DCQO je speciálně navržen tak, aby vynikal na dnešních kvantových zařízeních s hlučnou střední škálou (NISQ) [1]:

1. Odolnost vůči chybám: Méně Gate (10násobné snížení) znamená dramaticky méně akumulace chyb
2. Nevyžaduje zmírňování chyb: Inherentní efektivita algoritmu eliminuje potřebu nákladných technik pro zmírňování chyb [1]
3. Škálovatelnost: Dokáže zpracovat problémy s až 156 Qubit (156 binárních proměnných) s přímým mapováním Qubit [1]
4. Prokázaná výkonnost: Dosahuje 100% aproximačních poměrů na benchmarkových instancích MaxCut a HUBO [1]

Nyní se podívejme na tento výkonný algoritmus v akci na našem problému rozdělení trhu!

Krok 2: Optimalizace problému pro spuštění na kvantovém hardwaru

Algoritmus bf-DCQO automaticky zpracovává optimalizaci Circuit, vytváří mělké kvantové Circuit s kontradiabatickými členy speciálně navrženými pro cílový Backend.

Konfigurace optimalizace

Iskay Optimizer vyžaduje několik klíčových parametrů pro efektivní řešení tvého optimalizačního problému. Pojďme se podívat na každý parametr a jeho roli v procesu kvantové optimalizace:

Povinné parametry

Parametr	Typ	Popis	Příklad
problem	Dict[str, float]	Koeficienty QUBO ve formátu řetězcového klíče	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Specifikace formátu: "binary" pro QUBO nebo "spin" pro Ising	"binary"
backend_name	str	Cílové kvantové zařízení	"ibm_fez"

Základní koncepty

• Formát problému: Používáme "binary", protože naše proměnné jsou binární (0/1) a reprezentují přiřazení na trhu.
• Výběr Backend: Vyber si z dostupných QPU (například "ibm_fez") podle svých potřeb a instance výpočetních zdrojů.
• Struktura QUBO: Náš slovník problému obsahuje přesné koeficienty z matematické transformace.

Pokročilé možnosti (volitelné)

Iskay poskytuje možnosti jemného doladění prostřednictvím volitelných parametrů. I když výchozí nastavení funguje dobře pro většinu problémů, můžeš přizpůsobit chování pro konkrétní požadavky:

Parametr	Typ	Výchozí	Popis
shots	int	10000	Kvantová měření na iteraci (vyšší = přesnější)
num_iterations	int	10	Iterace algoritmu (více iterací může zlepšit kvalitu řešení)
use_session	bool	True	Použití IBM Session pro kratší čekací doby ve frontě
seed_transpiler	int	None	Nastav pro reprodukovatelnou kompilaci kvantového Circuit
direct_qubit_mapping	bool	False	Mapování virtuálních Qubit přímo na fyzické Qubit
job_tags	List[str]	None	Vlastní značky pro sledování úloh
preprocessing_level	int	0	Intenzita předběžného zpracování problému (0–3) – viz podrobnosti níže
postprocessing_level	int	2	Úroveň zjemnění řešení (0–2) – viz podrobnosti níže
transpilation_level	int	0	Optimalizační pokusy Transpiler (0–5) – viz podrobnosti níže
transpile_only	bool	False	Analýza optimalizace Circuit bez spuštění plného výpočtu

Úrovně předběžného zpracování (0–3): Zvláště důležité pro větší problémy, které se aktuálně nevejdou do koherenčních dob hardwaru. Vyšší úrovně předběžného zpracování dosahují menších hloubek Circuit pomocí aproximací při transpilaci problému:

• Úroveň 0: Přesné, delší Circuit
• Úroveň 1: Dobrá rovnováha mezi přesností a aproximací, odstraňuje pouze Gate s úhly v nejnižším 10. percentilu
• Úroveň 2: Mírně vyšší aproximace, odstraňuje Gate s úhly v nejnižším 20. percentilu a používá approximation_degree=0.95 při transpilaci
• Úroveň 3: Maximální úroveň aproximace, odstraňuje Gate v nejnižším 30. percentilu a používá approximation_degree=0.90 při transpilaci

Úrovně transpilace (0–5): Řídí pokročilé optimalizační pokusy Transpiler pro kompilaci kvantového Circuit. To může vést ke zvýšení klasické režie a v některých případech nemusí změnit hloubku Circuit. Výchozí hodnota 2 obecně vede k nejmenšímu Circuit a je relativně rychlá.

• Úroveň 0: Optimalizace rozloženého DCQO Circuit (layout, routing, scheduling)
• Úroveň 1: Optimalizace PauliEvolutionGate a poté rozloženého DCQO Circuit (max_trials=10)
• Úroveň 2: Optimalizace PauliEvolutionGate a poté rozloženého DCQO Circuit (max_trials=15)
• Úroveň 3: Optimalizace PauliEvolutionGate a poté rozloženého DCQO Circuit (max_trials=20)
• Úroveň 4: Optimalizace PauliEvolutionGate a poté rozloženého DCQO Circuit (max_trials=25)
• Úroveň 5: Optimalizace PauliEvolutionGate a poté rozloženého DCQO Circuit (max_trials=50)

Úrovně postprocessingu (0–2): Řídí míru klasické optimalizace, která kompenzuje chyby překlápění bitů pomocí různého počtu greedy průchodů lokálního prohledávání:

• Úroveň 0: 1 průchod
• Úroveň 1: 2 průchody
• Úroveň 2: 3 průchody

Režim pouze transpilace: Nyní dostupný pro uživatele, kteří chtějí analyzovat optimalizaci Circuit bez spuštění plného výpočtu kvantového algoritmu.

Příklad vlastní konfigurace

Takhle bys mohl nakonfigurovat Iskay s různými nastaveními:

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
}

Pro tento tutoriál ponecháme většinu výchozích parametrů a změníme pouze počet iterací bias-field:

# 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: Spuštění pomocí Qiskit primitiv

Nyní odesíláme náš problém ke spuštění na IBM Quantum hardwaru. Algoritmus bf-DCQO:

1. Sestaví mělké kvantové Circuit s kontradiabatickými členy
2. Provede přibližně 10 iterací s optimalizací bias-field
3. Provede klasické post-processing s lokálním prohledáváním
4. Vrátí optimální přiřazení trhů

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

Sledování stavu úlohy

Můžeš zkontrolovat aktuální stav své optimalizační úlohy. Možné stavy jsou:

• QUEUED: Úloha čeká ve frontě
• RUNNING: Úloha právě běží na kvantovém hardwaru
• DONE: Úloha úspěšně dokončena
• CANCELED: Úloha byla zrušena
• ERROR: Úloha narazila na chybu

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

Čekání na dokončení

Tato buňka bude blokována, dokud se úloha nedokončí. Proces optimalizace zahrnuje:

• Čas ve frontě (čekání na přístup ke kvantovému hardwaru)
• Čas spuštění (běh algoritmu bf-DCQO s přibližně 10 iteracemi)
• Čas post-processingu (klasické lokální prohledávání)

Typická doba dokončení se pohybuje od několika minut po desítky minut v závislosti na podmínkách fronty.

# 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: Post-processing a vrácení výsledku v požadovaném klasickém formátu

Nyní zpracováváme výsledky kvantového spuštění. To zahrnuje:

• Analýzu struktury řešení
• Ověření splnění omezení
• Porovnání s klasickými přístupy

Analýza výsledků

Pochopení struktury výsledků

Iskay vrací komplexní slovník výsledků obsahující:

• solution: Slovník mapující indexy proměnných na jejich optimální hodnoty (0 nebo 1)
• solution_info: Podrobné informace včetně:
  • bitstring: Optimální přiřazení jako binární řetězec
  • cost: Hodnota účelové funkce (měla by být 0 při dokonalém splnění omezení)
  • mapping: Jak pozice bitstringu mapují na proměnné problému
  • seed_transpiler: Seed použitý pro reprodukovatelnost
• prob_type: Zda je řešení v binárním nebo spinovém formátu

Pojďme prozkoumat řešení vrácené kvantovým optimalizátorem.

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

Ověření řešení

Nyní ověříme, zda kvantové řešení splňuje omezení problému Market Split. Proces ověření kontroluje:

Co je porušení omezení?

• Pro každý produkt $i$ vypočítáme skutečný prodej v regionu A: $(Ax)_i$
• Porovnáme ho s cílovým prodejem $b_i$
• Porušení je absolutní rozdíl: $|(Ax)_i - b_i|$
• Přípustné řešení má nulová porušení pro všechny produkty

Co očekáváme:

• Ideální případ: Celkové porušení = 0 (všechna omezení jsou dokonale splněna)
  • Region A dostane přesně 1002 jednotek produktu 1, 879 jednotek produktu 2 a 1040 jednotek produktu 3
  • Region B dostane zbývající jednotky (také 1002, 879 a 1040)
• Dobrý případ: Celkové porušení je malé (téměř optimální řešení)
• Špatný případ: Velká porušení naznačují, že řešení nesplňuje obchodní požadavky

Funkce pro ověření vypočítá:

1. Skutečný prodej na produkt v každém regionu
2. Porušení omezení pro každý produkt
3. Distribuci trhů mezi regiony

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)

Interpretace výsledků ověření

Výsledky ověření ukazují, zda Quantum Optimizer nalezl přípustné řešení. Pojďme prozkoumat:

Kontrola přípustnosti:

• is_feasible = True znamená, že řešení dokonale splňuje všechna omezení (celkové porušení = 0)
• is_feasible = False znamená, že některá omezení jsou porušena

Analýza prodeje:

• Porovnej cílový a skutečný prodej pro každý produkt
• Pro dokonalé řešení: Skutečný = Cílový pro všechny produkty v obou regionech
• Rozdíl udává, jak blízko jsme k požadovanému rozdělení trhu

Distribuce trhů:

• Ukazuje, kolik trhů je přiřazeno každému regionu
• Neexistuje požadavek na stejný počet trhů, pouze na splnění prodejních cílů

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

Hodnocení kvality řešení

Na základě výsledků ověření výše můžeme posoudit kvalitu kvantového řešení:

Pokud is_feasible = True (celkové porušení = 0):

• Quantum Optimizer úspěšně nalezl optimální řešení
• Všechna obchodní omezení jsou dokonale splněna
• To demonstruje kvantovou výhodu u problému, kde mají klasické řešiče potíže [4]

Pokud is_feasible = False (celkové porušení > 0):

• Řešení je téměř optimální, ale ne dokonalé
• Malá porušení mohou být v praxi přijatelná
• Zvaž úpravu parametrů optimalizátoru:
  • Zvyš num_iterations pro více průchodů optimalizace
  • Zvyš postprocessing_level pro více klasického zpřesnění
  • Zvyš shots pro lepší statistiku měření

Interpretace účelové funkce:

• Hodnota cost z solution_info se rovná $||Ax - b||^2$
• Cost = 0 indikuje dokonalé splnění omezení
• Vyšší hodnoty cost indikují větší porušení omezení

Závěr

Čeho jsme dosáhli

V tomto tutoriálu jsme úspěšně:

1. Načetli reálný optimalizační problém: Získali náročnou instanci Market Split z benchmarkové knihovny QOBLIB [2]
2. Transformovali do formátu QUBO: Převedli problém s omezeními na neomezený kvadratický formulace [3]
3. Využili pokročilé kvantové algoritmy: Použili algoritmus bf-DCQO od Kipu Quantum s kontradiabatickými členy [1]
4. Získali optimální řešení: Nalezli přípustná řešení splňující všechna omezení

Klíčové poznatky

Inovace algoritmu: Algoritmus bf-DCQO představuje významný pokrok [1]:

• 10krát méně Gate než digitální kvantové žíhání
• Přibližně 10 iterací místo přibližně 100 pro variační metody
• Vestavěná odolnost vůči chybám díky efektivitě Circuit

Kontradiabatické členy: Umožňují rychlou kvantovou evoluci při zachování věrnosti základního stavu, čímž činí kvantovou optimalizaci praktickou na dnešním hlučném hardwaru [1].

Guidance bias-field: Iterativní přístup bias-field umožňuje každé iteraci začít blízko dříve nalezených dobrých řešení a poskytuje formu kvantově posíleného lokálního prohledávání [1].

Další kroky

Pro prohloubení porozumění a další průzkum:

1. Vyzkoušej různé instance: Experimentuj s dalšími instancemi QOBLIB různých velikostí
2. Lad parametry: Uprav num_iterations, preprocessing_level, postprocessing_level
3. Porovnej s klasickými: Porovnej s klasickými optimalizačními řešiči
4. Vyzkoušej různé strategie: Pokus se najít lepší kódování problému nebo ho formuluj jako HUBO (pokud je to možné)
5. Aplikuj ve své oblasti: Přizpůsob techniky formulace QUBO/HUBO svým vlastním optimalizačním problémům

Reference

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