Lutasin ang Market Split problem gamit ang Iskay Quantum Optimizer ng Kipu Quantum

Paalala

Ang Qiskit Functions ay isang eksperimentong feature na available lamang para sa IBM Quantum® Premium Plan, Flex Plan, at On-Prem (via IBM Quantum Platform API) Plan users. Sila ay nasa preview release status at maaaring magbago.

Tinantyang paggamit: 20 segundo sa isang Heron r2 processor. (PAALALA: Ito ay tantya lamang. Maaaring mag-iba ang inyong runtime.)

Background

Ipinakikita ng tutorial na ito kung paano lutasin ang Market Split problem gamit ang Iskay quantum optimizer ng Kipu Quantum [1]. Ang Market Split problem ay kumakatawan sa isang real-world resource allocation challenge kung saan kailangang hatiin ang mga market sa balanseng sales regions upang matugunan ang eksaktong demand targets.

Ang Market Split challenge

Ang Market Split problem ay nagpapakita ng isang mukhang simpleng ngunit computationally formidable na hamon sa resource allocation. Isaalang-alang ang isang kumpanya na may $m$ na mga produkto na ibinebenta sa $n$ na iba't ibang markets, kung saan bawat market ay bumibili ng isang partikular na bundle ng mga produkto (kinakatawan ng mga column ng matrix $A$). Ang layuning pang-negosyo ay hatiin ang mga market na ito sa dalawang balanseng sales regions na ang bawat region ay makakatanggap ng eksaktong kalahati ng kabuuang demand para sa bawat produkto.

Pormulasyong matematikal:

Hinahanap natin ang isang binary assignment vector $x$, kung saan:

• Ang $x_j = 1$ ay nagtatalaga ng market $j$ sa Region A
• Ang $x_j = 0$ ay nagtatalaga ng market $j$ sa Region B
• Ang constraint na $Ax = b$ ay dapat matugunan, kung saan ang $b$ ay kumakatawan sa target sales (karaniwang kalahati ng kabuuang demand bawat produkto)

Cost function:

Upang lutasin ang problemang ito, pinaliit natin ang squared constraint violation:

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

kung saan:

• Ang $A_{ij}$ ay kumakatawan sa mga benta ng produkto $i$ sa market $j$
• Ang $x_j \in \{0,1\}$ ay ang binary assignment ng market $j$
• Ang $b_i$ ay ang target sales para sa produkto $i$ sa bawat region
• Ang cost ay katumbas ng zero sa tuwing natutugunan ang lahat ng constraints

Bawat term sa sum ay kumakatawan sa squared deviation mula sa target sales para sa isang partikular na produkto. Kapag pinalawak natin ang cost function na ito, nakukuha natin ang:

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

Dahil ang $b^T b$ ay constant, ang pagpapaliit ng $C(x)$ ay katumbas ng pagpapaliit ng quadratic function na $x^T A^T A x - 2b^T A x$, na eksaktong isang QUBO (Quadratic Unconstrained Binary Optimization) problem.

Computational complexity:

Sa kabila ng straightforward na interpretasyong pang-negosyo nito, ang problemang ito ay nagpapakita ng kapansin-pansing computational intractability:

• Small-scale failure: Ang conventional Mixed Integer Programming solvers ay nabibigo sa mga instance na may kasing kaunti ng pitong produkto sa ilalim ng timeout na isang oras [4]
• Exponential growth: Ang solution space ay lumalaki nang exponential ($2^n$ na posibleng assignments), na ginagawang hindi posible ang brute force approaches

Ang matinding computational barrier na ito, kasama ng praktikal na kaugnayan nito sa territory planning at resource allocation, ay ginagawang ideal benchmark para sa quantum optimization algorithms ang Market Split problem [4].

Ano ang gumagawang natatangi sa approach ng Iskay?

Ginagamit ng Iskay optimizer ang bf-DCQO (bias-field digitized counterdiabatic quantum optimization) algorithm [1], na kumakatawan sa isang makabuluhang advancement sa quantum optimization:

Kahusayan ng circuit: Ang bf-DCQO algorithm ay nakakamit ng kahanga-hangang gate reduction [1]:

• Hanggang 10 beses na mas kaunting entangling gates kaysa Digital Quantum Annealing (DQA)
• Ang makabuluhang mas mababaw na circuits ay nagbibigay-daan sa:
  • Mas kaunting error accumulation sa panahon ng quantum execution
  • Kakayahang harapin ang mas malalaking problema sa kasalukuyang quantum hardware
  • Walang pangangailangan para sa error mitigation techniques

Non-variational design: Hindi tulad ng variational algorithms na nangangailangan ng mga humigit-kumulang 100 iterations, ang bf-DCQO ay karaniwang nangangailangan lamang ng mga humigit-kumulang 10 iterations [1]. Nakakamit ito sa pamamagitan ng:

• Matalinong bias-field calculations mula sa sinusukat na state distributions
• Pagsisimula ng bawat iteration mula sa energy state na malapit sa nakaraang solusyon
• Integrated classical post-processing na may local search

Counterdiabatic protocols: Isinasama ng algorithm ang mga counterdiabatic terms na nagsusupil ng mga hindi gustong quantum excitations sa panahon ng maikling evolution times, na nagbibigay-daan sa system na manatiling malapit sa ground state kahit na may mabilis na transitions [1].

Requirements

Bago simulan ang tutorial na ito, tiyaking mayroon kayong naka-install na sumusunod:

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

Kakailanganin din ninyong makakuha ng access sa Iskay Quantum Optimizer function mula sa Qiskit Functions Catalog.

Setup

Una, i-import ang lahat ng kinakailangang packages para sa tutorial na ito.

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

I-configure ang IBM Quantum credentials

Tukuyin ang inyong IBM Quantum® Platform credentials. Kakailanganin ninyo ang:

• API Token: Ang inyong 44-character na API key mula sa IBM Quantum Platform
• Instance CRN: Ang inyong IBM Cloud® instance identifier

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

Step 1: I-map ang classical inputs sa isang quantum problem

Nagsisimula tayo sa pamamagitan ng pag-map ng ating classical problem sa isang quantum-compatible representation. Kasama sa hakbang na ito ang:

1. Pagkonekta sa Iskay Quantum Optimizer
2. Pag-load at pagpormulahin ng Market Split problem
3. Pag-unawa sa bf-DCQO algorithm na maglulutos nito

Kumonekta sa Iskay Quantum Optimizer

Nagsisimula tayo sa pamamagitan ng pagtatatag ng koneksyon sa Qiskit Functions Catalog at pag-load ng Iskay Quantum Optimizer. Ang Iskay Optimizer ay isang quantum function na ibinibigay ng Kipu Quantum na nag-iimplement ng bf-DCQO algorithm para sa paglutas ng mga optimization problems sa quantum hardware.

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

I-load at formulahin ang problema

Unawain ang format ng problem data

Ang mga problem instances mula sa QOBLIB (Quantum Optimization Benchmarking Library) [2] ay nakaimbak sa isang simpleng text format. Suriin natin ang aktwal na nilalaman ng ating target instance na 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

Istruktura ng format:

• Unang linya: 3 20

  • 3 = bilang ng mga produkto (constraints/rows sa matrix $A$)
  • 20 = bilang ng mga markets (variables/columns sa matrix $A$)

• Susunod na 3 linya: Coefficient matrix $A$ at target vector $b$

  • Bawat linya ay may 21 numero: unang 20 ay row coefficients, huli ay ang target
  • Line 2: 60 92 161 ... 51 | 1002
    • Unang 20 numero: Kung gaano karami ng Product 1 ang binebenta ng bawat isa sa 20 markets
    • Huling numero (1002): Target sales para sa Product 1 sa isang region
  • Line 3: 176 196 41 ... 46 | 879
    • Product 2 sales bawat market at target (879)
  • Line 4: 68 68 179 ... 95 | 1040
    • Product 3 sales bawat market at target (1040)

Interpretasyong pang-negosyo:

• Ang Market 0 ay nagbebenta ng: 60 units ng Product 1, 176 units ng Product 2, 68 units ng Product 3
• Ang Market 1 ay nagbebenta ng: 92 units ng Product 1, 196 units ng Product 2, 68 units ng Product 3
• At iba pa para sa lahat ng 20 markets...
• Layunin: Hatiin ang 20 markets na ito sa dalawang regions kung saan ang bawat region ay makakakuha ng eksaktong 1002 units ng Product 1, 879 units ng Product 2, at 1040 units ng Product 3

QUBO transformation

Mula sa constraints tungo sa QUBO: ang mathematical transformation

Ang kapangyarihan ng quantum optimization ay nakasalalay sa pagtransporma ng constrained problems sa unconstrained quadratic forms [4]. Para sa Market Split problem, kinukumberte natin ang equality constraints

$Ax = b$

kung saan ang $x ∈ \{0,1\}^n$, sa isang QUBO sa pamamagitan ng pagpaparusa sa constraint violations.

Ang penalty method: Dahil kailangan nating ang $Ax = b$ ay manatiling eksaktong totoo, pinaliit natin ang squared violation: $f(x) = ||Ax - b||^2$

Ito ay katumbas ng zero sa tuwing natutugunan ang lahat ng constraints. Sa pag-expand nang algebraically: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

QUBO objective: Dahil ang $b^T b$ ay constant, ang ating optimization ay nagiging: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Pangunahing insight: Ang transformation na ito ay eksaktong, hindi tinantiya. Ang equality constraints ay natural na nag-square sa quadratic form nang hindi nangangailangan ng auxiliary variables o penalty parameters - ginagawang mathematically elegant at computationally efficient para sa quantum solvers ang pormulasiyon na ito [4]. Gagamitin natin ang OptimizationProblem class upang tukuyin ang ating constrained problem, pagkatapos ay i-convert ito sa QUBO format gamit ang OptimizationProblemToQubo, pareho mula sa qiskit_addon_opt_mapper package. Ito ay awtomatikong humahawak ng penalty-based transformation.

I-implement ang data loading at QUBO conversion functions

Tutukuyin natin ngayon ang tatlong utility functions:

1. parse_marketsplit_dat() - Nag-parse ng .dat file format at nag-extract ng matrices $A$ at $b$
2. fetch_marketsplit_data() - Nag-download ng problem instances direkta mula sa QOBLIB repository

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

I-load ang problem instance

I-load natin ngayon ang partikular na problem instance na ms_03_200_177.dat mula sa QOBLIB [2]. Ang instance na ito ay may:

• 3 produkto (constraints)
• 20 markets (binary decision variables)
• Mahigit 1 milyon na posibleng market assignments na susuriin ($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"
    )

I-convert sa QUBO format

Itransporma natin ngayon ang constrained optimization problem sa QUBO format:

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

I-convert ang QUBO sa Iskay format

Kailangan nating i-convert ngayon ang QUBO object sa dictionary format na kailangan ng Iskay Optimizer ng Kipu Quantum.

Ang problem at problem_type arguments ay nag-encode ng optimization problem sa anyo ng

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

kung saan

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

• Sa pagpili ng problem_type = "binary", tinutukoy ninyo na ang cost function ay nasa binary format, na nangangahulugang $D = \{0, 1\}^{n}$, gaya ng, ang cost function ay nakasulat sa QUBO/HUBO formulation.
• Sa kabilang banda, sa pagpili ng problem_type = "spin", ang cost function ay nakasulat sa Ising formulation, kung saan ang $D = \{-1, 1\}^{n}$.

Ang mga coefficients ng problema ay dapat na i-encode sa isang dictionary gaya ng sumusunod:

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

Tandaan na ang mga keys ng dictionary ay dapat na strings na naglalaman ng valid tuple ng mga non-repeating integers. Para sa binary problems, alam natin na:

$$x_i^2 = x_i$$

para sa $i=j$ (dahil ang $x_i \in \{0,1\}$ ay nangangahulugang $x_i \cdot x_i = x_i$). Kaya, sa inyong QUBO formulation, kung mayroon kayong parehong linear contributions na $b_i x_i$ at diagonal quadratic contributions na $c_{i,i} x_i^2$, ang mga terms na ito ay dapat pagsamahin sa isang linear coefficient:

Kabuuang linear coefficient para sa variable na $x_i$: $b_i + c_{i,i}$

Nangangahulugan ito na:

• Ang linear terms tulad ng "(i, )" ay naglalaman ng: orihinal na linear coefficient + diagonal quadratic coefficient
• Ang diagonal quadratic terms tulad ng "(i, i)" ay HINDI dapat lumitaw sa huling dictionary
• Ang off-diagonal quadratic terms lamang tulad ng "(i, j)" kung saan ang $i \neq j$ ay dapat isama bilang hiwalay na entries

Halimbawa: Kung ang inyong QUBO ay may $3x_1 + 2x_1^2 + 4x_1 x_2$, ang Iskay dictionary ay dapat maglaman ng:

• "(0, )": 5.0 (pinagsasama ang $3 + 2 = 5$)
• "(0, 1)": 4.0 (off-diagonal term)

HINDI hiwalay na entries para sa "(0, )": 3.0 at "(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!")

Unawain ang bf-DCQO algorithm

Bago natin patakbuhin ang optimization, unawain muna natin ang sopistikadong quantum algorithm na nagpapalakas sa Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Ano ang bf-DCQO?

Ang bf-DCQO ay batay sa time evolution ng isang quantum system kung saan ang solusyon sa problema ay naka-encode sa ground state (pinakamababang energy state) ng panghuling quantum Hamiltonian [1]. Tinutugunan ng algorithm ang isang pangunahing hamon sa quantum optimization:

Ang hamon: Ang traditional adiabatic quantum computing ay nangangailangan ng napakabagal na evolution upang mapanatili ang ground state conditions ayon sa adiabatic theorem. Ito ay nangangailangan ng tumataas na malalim na quantum circuits habang tumataas ang pagiging kumplikado ng problema, na nagreresulta sa mas maraming gate operations at accumulated errors.

Ang solusyon: Ginagamit ng bf-DCQO ang counterdiabatic protocols upang paganahin ang mabilis na evolution habang pinapanatili ang ground state fidelity, na lubhang nagpapababa ng circuit depth.

Mathematical framework

Pinaliit ng algorithm ang cost function sa anyo ng:

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

kung saan ang $D = \{0,1\}^n$ para sa binary variables at:

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

Para sa ating Market Split problem, ang cost function ay:

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

Ang papel ng counterdiabatic terms

Ang counterdiabatic terms ay karagdagang terms na ipinakilala sa time-dependent Hamiltonian na nagsusupil ng mga hindi gustong excitations sa panahon ng quantum evolution. Narito kung bakit sila mahalaga:

Sa adiabatic quantum optimization, pinapalaki natin ang system ayon sa time-dependent Hamiltonian:

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

kung saan ang $H_{\text{problem}}$ ay nag-encode ng ating optimization problem. Upang mapanatili ang ground state sa panahon ng mabilis na evolution, idinadagdag natin ang counterdiabatic terms:

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

Ang counterdiabatic terms na ito ay gumagawa ng sumusunod:

1. Sinusupil ang mga hindi gustong transitions: Pinipigilan ang quantum state na tumalon sa excited states sa panahon ng mabilis na evolution
2. Pinagagana ang mas maikling evolution times: Binibigyang-daan tayo na maabot ang panghuling state nang mas mabilis nang hindi lumalabag sa adiabaticity
3. Binabawasan ang circuit depth: Ang mas maikling evolution ay humahantong sa mas kaunting gates at mas kaunting error

Ang praktikal na epekto ay kahanga-hanga: ang bf-DCQO ay gumagamit ng hanggang 10 beses na mas kaunting entangling gates kaysa Digital Quantum Annealing [1], na ginagawang praktikal para sa quantum hardware ngayon na maingay.

Bias-field iterative optimization

Hindi tulad ng variational algorithms na nag-optimize ng circuit parameters sa maraming iterations, ang bf-DCQO ay gumagamit ng bias-field guided approach na nag-converge sa humigit-kumulang 10 iterations [1]:

Proseso ng iteration:

1. Paunang quantum evolution: Magsimula sa quantum circuit na nag-iimplement ng counterdiabatic evolution protocol

2. Pagsukat: Sukatin ang quantum state upang makakuha ng probability distribution sa mga bitstrings

3. Pagkalkula ng bias-field: Suriin ang measurement statistics at kalkulahin ang optimal bias-field na $h_i$ para sa bawat qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Susunod na iteration: Binabago ng bias-field ang Hamiltonian para sa susunod na iteration: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Ito ay nagbibigay-daan sa pagsisimula malapit sa dati nang natagpuang magandang solusyon, na epektibong gumaganap ng isang uri ng "quantum local search"

5. Convergence: Ulitin hanggang ang kalidad ng solusyon ay maging stable o maabot ang maximum na bilang ng iterations

Pangunahing pakinabang: Bawat iteration ay nagbibigay ng makabuluhang pag-unlad tungo sa optimal solution sa pamamagitan ng pagsasama ng impormasyon mula sa nakaraang measurements, hindi tulad ng variational methods na kailangang suriin ang parameter space nang bulag.

Integrated classical post-processing

Pagkatapos ng pag-converge ng quantum optimization, nagsasagawa ang Iskay ng classical local search post-processing:

• Bit-flip exploration: Sistematiko o random na i-flip ang mga bits sa pinakamahusay na nasukat na solusyon
• Pagsusuri ng energy: Kalkulahin ang $C(x)$ para sa bawat binagong solusyon
• Greedy selection: Tanggapin ang mga pagpapabuti na nagpapababa ng cost function
• Maraming passes: Magsagawa ng ilang passes (kinokontrol ng postprocessing_level)

Ang hybrid approach na ito ay bumabawi para sa bit-flip errors mula sa hardware imperfections at readout errors, na tinitiyak ang mataas na kalidad ng mga solusyon kahit sa maingay na quantum devices.

Bakit nangunguna ang bf-DCQO sa kasalukuyang hardware

Ang bf-DCQO algorithm ay partikular na dinisenyo upang manguna sa noisy intermediate-scale quantum (NISQ) devices ngayon [1]:

1. Tibay sa error: Mas kaunting gates (10 beses na pagbawas) ay nangangahulugang lubhang mas kaunting error accumulation
2. Walang kailangang error mitigation: Ang likas na kahusayan ng algorithm ay nag-aalis ng pangangailangan para sa mahal na error mitigation techniques [1]
3. Scalability: Kayang hawakan ang mga problema na may hanggang 156 qubits (156 binary variables) na may direct qubit-mapping [1]
4. Napatunayang performance: Nakakamit ng 100% approximation ratios sa benchmark MaxCut at HUBO instances [1]

Tingnan natin ngayon ang powerful algorithm na ito sa aksyon sa ating Market Split problem!

Step 2: I-optimize ang problema para sa quantum hardware execution

Ang bf-DCQO algorithm ay awtomatikong humahawak ng circuit optimization, na lumilikha ng mababaw na quantum circuits na may counterdiabatic terms na partikular na dinisenyo para sa target backend.

I-configure ang optimization

Ang Iskay Optimizer ay nangangailangan ng ilang pangunahing parameters upang epektibong malutas ang inyong optimization problem. Suriin natin ang bawat parameter at ang papel nito sa quantum optimization process:

Kinakailangang parameters

Parameter	Type	Paglalarawan	Halimbawa
problem	Dict[str, float]	Mga QUBO coefficients sa string-key format	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Tukoy ng format: "binary" para sa QUBO o "spin" para sa Ising	"binary"
backend_name	str	Target na quantum device	"ibm_fez"

Mahahalagang konsepto

• Format ng problema: Ginagamit natin ang "binary" dahil ang ating mga variables ay binary (0/1), na kumakatawan sa market assignments.
• Pagpili ng backend: Pumili sa pagitan ng mga available na QPUs (halimbawa, "ibm_fez") batay sa inyong pangangailangan at compute resource instance.
• Istruktura ng QUBO: Ang ating problem dictionary ay naglalaman ng eksaktong coefficients mula sa mathematical transformation.

Advanced options (opsyonal)

Ang Iskay ay nagbibigay ng fine-tuning capabilities sa pamamagitan ng optional parameters. Habang ang defaults ay gumagana nang maayos para sa karamihan ng mga problema, maaari ninyong i-customize ang pag-uugali para sa partikular na pangangailangan:

Parameter	Type	Default	Paglalarawan
shots	int	10000	Mga quantum measurements bawat iteration (mas mataas = mas tumpak)
num_iterations	int	10	Mga iterations ng algorithm (mas maraming iterations ay maaaring magpabuti ng kalidad ng solusyon)
use_session	bool	True	Gumamit ng IBM sessions para sa nabawasang queue times
seed_transpiler	int	None	Itakda para sa reproducible quantum circuit compilation
direct_qubit_mapping	bool	False	I-map ang virtual qubits direkta sa physical qubits
job_tags	List[str]	None	Custom tags para sa job tracking
preprocessing_level	int	0	Intensidad ng problem preprocessing (0-3) - tingnan ang mga detalye sa ibaba
postprocessing_level	int	2	Antas ng solution refinement (0-2) - tingnan ang mga detalye sa ibaba
transpilation_level	int	0	Mga transpiler optimization trials (0-5) - tingnan ang mga detalye sa ibaba
transpile_only	bool	False	Suriin ang circuit optimization nang hindi nagpapatakbo ng buong execution

Mga Antas ng Preprocessing (0-3): Partikular na mahalaga para sa mas malalaking problema na hindi kasalukuyang kasya sa coherence times ng hardware. Ang mas mataas na preprocessing levels ay nakakamit ng mas mababaw na circuit depths sa pamamagitan ng approximations sa problem transpilation:

• Level 0: Eksaktong, mas mahabang circuits
• Level 1: Magandang balanse sa pagitan ng accuracy at approximation, pinutol lamang ang gates na may angles sa pinakamababang 10 percentile
• Level 2: Bahagyang mas mataas na approximation, pinutol ang gates na may angles sa pinakamababang 20 percentile at gumagamit ng approximation_degree=0.95 sa transpilation
• Level 3: Maximum approximation level, pinutol ang gates sa pinakamababang 30 percentile at gumagamit ng approximation_degree=0.90 sa transpilation

Mga Antas ng Transpilation (0-5): Kinokontrol ang advanced transpiler optimization trials para sa quantum circuit compilation. Maaaring humantong ito sa pagtaas ng classical overhead, at para sa ilang mga kaso maaaring hindi ito magbago ng circuit depth. Ang default value na 2 sa pangkalahatan ay humahantong sa pinakamaliit na circuit at medyo mabilis.

• Level 0: Optimization ng decomposed DCQO circuit (layout, routing, scheduling)
• Level 1: Optimization ng PauliEvolutionGate at pagkatapos ng decomposed DCQO circuit (max_trials=10)
• Level 2: Optimization ng PauliEvolutionGate at pagkatapos ng decomposed DCQO circuit (max_trials=15)
• Level 3: Optimization ng PauliEvolutionGate at pagkatapos ng decomposed DCQO circuit (max_trials=20)
• Level 4: Optimization ng PauliEvolutionGate at pagkatapos ng decomposed DCQO circuit (max_trials=25)
• Level 5: Optimization ng PauliEvolutionGate at pagkatapos ng decomposed DCQO circuit (max_trials=50)

Mga Antas ng Postprocessing (0-2): Kinokontrol kung gaano karaming classical optimization, bumabawi para sa bit-flip errors na may iba't ibang bilang ng greedy passes ng local search:

• Level 0: 1 pass
• Level 1: 2 passes
• Level 2: 3 passes

Transpile-only mode: Available na ngayon para sa mga users na gustong suriin ang circuit optimization nang hindi nagpapatakbo ng buong quantum algorithm execution.

Halimbawa ng custom configuration

Narito kung paano ninyo maaaring i-configure ang Iskay na may iba't ibang settings:

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
}

Para sa tutorial na ito, papanatilihin natin ang karamihan sa mga default parameters at babaguhin lamang ang bilang ng bias-field iterations:

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

Step 3: Isagawa gamit ang Qiskit primitives

Isusumite natin ngayon ang ating problema upang tumakbo sa IBM Quantum hardware. Ang bf-DCQO algorithm ay:

1. Gagawa ng mababaw na quantum circuits na may counterdiabatic terms
2. Magsasagawa ng humigit-kumulang 10 iterations na may bias-field optimization
3. Magsasagawa ng classical post-processing na may local search
4. Magbabalik ng optimal market assignment

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

Subaybayan ang job status

Maaari ninyong suriin ang kasalukuyang status ng inyong optimization job. Ang posibleng mga status ay:

• QUEUED: Naghihintay ang job sa queue
• RUNNING: Kasalukuyang tumatakbo ang job sa quantum hardware
• DONE: Matagumpay na nakumpleto ang job
• CANCELED: Kinansela ang job
• ERROR: Nakakita ang job ng error

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

Maghintay para sa pagkumpleto

Ang cell na ito ay magba-block hanggang sa makumpleto ang job. Kasama sa optimization process ang:

• Queue time (paghihintay para sa quantum hardware access)
• Execution time (pagpapatakbo ng bf-DCQO algorithm na may humigit-kumulang 10 iterations)
• Post-processing time (classical local search)

Ang karaniwang completion times ay mula ilang minuto hanggang sampung minuto depende sa queue conditions.

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

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

Step 4: I-post-process at ibalik ang resulta sa nais na classical format

I-post-process natin ngayon ang mga resulta ng quantum execution. Kasama rito ang:

• Pagsusuri sa istruktura ng solusyon
• Pagpapatunay ng constraint satisfaction
• Pag-benchmark laban sa classical approaches

Suriin ang mga resulta

Unawain ang istruktura ng resulta

Ang Iskay ay nagbabalik ng komprehensibong result dictionary na naglalaman ng:

• solution: Isang dictionary na nag-map ng variable indices sa kanilang optimal values (0 o 1)
• solution_info: Detalyadong impormasyon kasama ang:
  • bitstring: Ang optimal assignment bilang binary string
  • cost: Ang objective function value (dapat ay 0 para sa perpektong constraint satisfaction)
  • mapping: Kung paano nag-map ang bitstring positions sa problem variables
  • seed_transpiler: Seed na ginamit para sa reproducibility
• prob_type: Kung ang solusyon ay nasa binary o spin format

Suriin natin ang solusyon na ibinalik ng quantum optimizer.

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

Pagpapatunay ng solusyon

I-validate natin ngayon kung natutugunan ng quantum solution ang Market Split constraints. Sinusuri ng validation process ang:

Ano ang constraint violation?

• Para sa bawat produkto $i$, kinakalkula natin ang aktwal na benta sa Region A: $(Ax)_i$
• Inihahambing natin ito sa target sales na $b_i$
• Ang violation ay ang absolute difference: $|(Ax)_i - b_i|$
• Ang feasible solution ay may zero violations para sa lahat ng produkto

Ano ang inaasahan natin:

• Ideal case: Kabuuang violation = 0 (lahat ng constraints ay perpektong natutugunan)
  • Ang Region A ay nakakakuha ng eksaktong 1002 units ng Product 1, 879 units ng Product 2, at 1040 units ng Product 3
  • Ang Region B ay nakakakuha ng natitirang units (gayundin 1002, 879, at 1040 ayon sa pagkakabanggit)
• Good case: Ang kabuuang violation ay maliit (near-optimal solution)
• Poor case: Ang malalaking violations ay nagpapahiwatig na ang solusyon ay hindi natutugunan ang mga pangangailangan ng negosyo

Ang validation function ay magsasagawa ng:

1. Aktwal na benta bawat produkto sa bawat region
2. Mga constraint violations para sa bawat produkto
3. Pamamahagi ng market sa pagitan ng mga regions

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)

Bigyang-kahulugan ang mga validation results

Ipinapakita ng validation results kung nakakita ang Quantum Optimizer ng feasible solution. Suriin natin ang sumusunod:

Pagsusuri sa feasibility:

• Ang is_feasible = True ay nangangahulugang perpektong natutugunan ng solusyon ang lahat ng constraints (kabuuang violation = 0)
• Ang is_feasible = False ay nangangahulugang may ilang constraints na nilabag

Pagsusuri ng benta:

• Ihambing ang Target versus Actual sales para sa bawat produkto
• Para sa perpektong solusyon: Actual = Target para sa lahat ng produkto sa parehong regions
• Ipinapakita ng pagkakaiba kung gaano tayo kalapit sa nais na market split

Pamamahagi ng market:

• Ipinapakita kung gaano karaming markets ang nakatakda sa bawat region
• Walang kinakailangan para sa pantay na bilang ng markets, basta natutugunan lamang ang sales targets

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

Pagsusuri sa kalidad ng solusyon

Batay sa validation results sa itaas, masusuri natin ang kalidad ng quantum solution:

Kung is_feasible = True (Kabuuang violation = 0):

• Matagumpay na nakakita ang Quantum Optimizer ng optimal solution
• Lahat ng business constraints ay perpektong natutugunan
• Ipinakikita nito ang quantum advantage sa isang problema kung saan nahihirapan ang classical solvers [4]

Kung is_feasible = False (Kabuuang violation > 0):

• Ang solusyon ay near-optimal ngunit hindi perpekto
• Maaaring tanggapin ang maliliit na violations sa praktis
• Isaalang-alang ang pag-adjust ng optimizer parameters:
  • Itaas ang num_iterations para sa mas maraming optimization passes
  • Itaas ang postprocessing_level para sa mas maraming classical refinement
  • Itaas ang shots para sa mas magandang measurement statistics

Interpretasyon ng cost function:

• Ang cost value mula sa solution_info ay katumbas ng $||Ax - b||^2$
• Ang Cost = 0 ay nagpapahiwatig ng perpektong constraint satisfaction
• Ang mas mataas na cost values ay nagpapahiwatig ng mas malalaking constraint violations

Konklusyon

Ano ang ating naisakatuparan

Sa tutorial na ito, matagumpay tayong:

1. Nag-load ng real optimization problem: Nakakuha ng mahirap na Market Split instance mula sa QOBLIB benchmark library [2]
2. Nagtransporma sa QUBO format: Kinumberte ang constrained problem sa unconstrained quadratic formulation [3]
3. Gumamit ng advanced quantum algorithms: Ginamit ang bf-DCQO algorithm ng Kipu Quantum na may counterdiabatic terms [1]
4. Nakakuha ng optimal solutions: Nakakita ng feasible solutions na natututugunan ang lahat ng constraints

Mga pangunahing aral

Pagbabago sa algorithm: Ang bf-DCQO algorithm ay kumakatawan sa makabuluhang advancement [1]:

• 10 beses na mas kaunting gates kaysa digital quantum annealing
• Humigit-kumulang 10 iterations sa halip na humigit-kumulang 100 para sa variational methods
• Built-in error resilience sa pamamagitan ng kahusayan ng circuit

Counterdiabatic terms: Nagbibigay-daan sa mabilis na quantum evolution habang pinapanatili ang ground state fidelity, na ginagawang praktikal ang quantum optimization sa maingay na hardware ngayon [1].

Bias-field guidance: Ang iterative bias-field approach ay nagbibigay-daan sa bawat iteration na magsimula malapit sa dati nang natagpuang magagandang solusyon, na nagbibigay ng isang uri ng quantum-enhanced local search [1].

Susunod na hakbang

Upang palalimin ang inyong pag-unawa at mag-explore pa:

1. Subukan ang iba't ibang instances: Mag-eksperimento sa iba pang QOBLIB instances ng iba't ibang laki
2. I-tune ang parameters: I-adjust ang num_iterations, preprocessing_level, postprocessing_level
3. Ihambing sa classical: Mag-benchmark laban sa classical optimization solvers
4. Subukan ang iba't ibang strategies: Subukang maghanap ng mas magandang encoding para sa problema o pormulasyunin ito bilang HUBO (kung posible)
5. Ilapat sa inyong domain: I-adapt ang QUBO/HUBO formulation techniques sa inyong sariling optimization problems

Mga Sanggunian

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