Selesaikan masalah Market Split dengan Iskay Quantum Optimizer dari Kipu Quantum

Nota

Qiskit Functions ialah ciri eksperimental yang hanya tersedia untuk pengguna IBM Quantum® Premium Plan, Flex Plan, dan On-Prem (melalui IBM Quantum Platform API) Plan. Ia berada dalam status pratonton dan tertakluk kepada perubahan.

Anggaran penggunaan: 20 saat pada pemproses Heron r2. (NOTA: Ini adalah anggaran sahaja. Masa jalan anda mungkin berbeza.)

Latar Belakang

Tutorial ini menunjukkan cara menyelesaikan masalah Market Split menggunakan Iskay quantum optimizer dari Kipu Quantum [1]. Masalah Market Split mewakili cabaran pengagihan sumber dunia nyata di mana pasaran perlu dibahagikan kepada kawasan jualan yang seimbang untuk memenuhi sasaran permintaan yang tepat.

Cabaran Market Split

Masalah Market Split menghadirkan cabaran yang kelihatan mudah tetapi amat sukar dari segi pengiraan dalam pengagihan sumber. Bayangkan sebuah syarikat dengan $m$ produk yang dijual merentasi $n$ pasaran berbeza, di mana setiap pasaran membeli satu set produk tertentu (diwakili oleh lajur matriks $A$). Objektif perniagaan adalah untuk membahagikan pasaran-pasaran ini kepada dua kawasan jualan yang seimbang supaya setiap kawasan menerima tepat separuh daripada jumlah permintaan bagi setiap produk.

Formulasi matematik:

Kita mencari vektor tugasan binari $x$, di mana:

• $x_j = 1$ menugaskan pasaran $j$ ke Kawasan A
• $x_j = 0$ menugaskan pasaran $j$ ke Kawasan B
• Kekangan $Ax = b$ mesti dipenuhi, di mana $b$ mewakili sasaran jualan (biasanya separuh daripada jumlah permintaan setiap produk)

Fungsi kos:

Untuk menyelesaikan masalah ini, kita meminimumkan pelanggaran kekangan kuasa dua:

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

di mana:

• $A_{ij}$ mewakili jualan produk $i$ di pasaran $j$
• $x_j \in \{0,1\}$ ialah tugasan binari pasaran $j$
• $b_i$ ialah sasaran jualan untuk produk $i$ di setiap kawasan
• Kos adalah sifar tepat apabila semua kekangan dipenuhi

Setiap sebutan dalam jumlah mewakili sisihan kuasa dua daripada sasaran jualan untuk produk tertentu. Apabila kita mengembangkan fungsi kos ini, kita mendapat:

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

Oleh kerana $b^T b$ adalah pemalar, meminimumkan $C(x)$ adalah setara dengan meminimumkan fungsi kuadratik $x^T A^T A x - 2b^T A x$, yang merupakan tepat masalah QUBO (Quadratic Unconstrained Binary Optimization).

Kerumitan pengiraan:

Walaupun interpretasi perniagaannya mudah, masalah ini mempunyai kerumitan pengiraan yang luar biasa:

• Kegagalan berskala kecil: Penyelesai Mixed Integer Programming konvensional gagal pada contoh dengan serendah tujuh produk dalam masa tamat satu jam [4]
• Pertumbuhan eksponen: Ruang penyelesaian berkembang secara eksponen ($2^n$ tugasan yang mungkin), menjadikan pendekatan kasar tidak boleh dilaksanakan

Halangan pengiraan yang teruk ini, digabungkan dengan relevansi praktikalnya untuk perancangan wilayah dan pengagihan sumber, menjadikan masalah Market Split penanda aras yang ideal untuk algoritma pengoptimuman kuantum [4].

Apakah yang menjadikan pendekatan Iskay unik?

Pengoptimum Iskay menggunakan algoritma bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], yang mewakili kemajuan signifikan dalam pengoptimuman kuantum:

Kecekapan Circuit: Algoritma bf-DCQO mencapai pengurangan gate yang luar biasa [1]:

• Sehingga 10 kali lebih sedikit gate pembelit berbanding Digital Quantum Annealing (DQA)
• Circuit yang jauh lebih cetek membolehkan:
  • Pengumpulan ralat yang lebih sedikit semasa pelaksanaan kuantum
  • Keupayaan untuk menangani masalah yang lebih besar pada perkakasan kuantum semasa
  • Tidak perlu teknik mitigasi ralat

Reka bentuk bukan variatif: Tidak seperti algoritma variatif yang memerlukan kira-kira 100 lelaran, bf-DCQO biasanya hanya memerlukan kira-kira 10 lelaran [1]. Ini dicapai melalui:

• Pengiraan bias-field yang bijak daripada taburan keadaan yang diukur
• Memulakan setiap lelaran daripada keadaan tenaga berhampiran penyelesaian sebelumnya
• Pasca-pemprosesan klasik bersepadu dengan carian setempat

Protokol counterdiabatic: Algoritma ini menggabungkan sebutan counterdiabatic yang menekan pengujaan kuantum yang tidak diingini semasa masa evolusi yang singkat, membolehkan sistem kekal berhampiran keadaan asas walaupun dengan peralihan cepat [1].

Keperluan

Sebelum memulakan tutorial ini, pastikan anda telah memasang perkara berikut:

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

Anda juga perlu mendapat akses kepada fungsi Iskay Quantum Optimizer daripada Qiskit Functions Catalog.

Persediaan

Mula-mula, import semua pakej yang diperlukan untuk tutorial ini.

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

Konfigurasikan kelayakan IBM Quantum

Takrifkan kelayakan IBM Quantum® Platform anda. Anda memerlukan:

• Token API: Kunci API 44 aksara anda daripada IBM Quantum Platform
• Instance CRN: Pengecam instance IBM Cloud® anda

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

Langkah 1: Petakan input klasik kepada masalah kuantum

Kita mulakan dengan memetakan masalah klasik kita kepada representasi yang serasi dengan kuantum. Langkah ini melibatkan:

1. Menyambung kepada Iskay Quantum Optimizer
2. Memuatkan dan merumuskan masalah Market Split
3. Memahami algoritma bf-DCQO yang akan menyelesaikannya

Sambung kepada Iskay Quantum Optimizer

Kita mulakan dengan membuat sambungan kepada Qiskit Functions Catalog dan memuatkan Iskay Quantum Optimizer. Iskay Optimizer ialah fungsi kuantum yang disediakan oleh Kipu Quantum yang melaksanakan algoritma bf-DCQO untuk menyelesaikan masalah pengoptimuman pada perkakasan kuantum.

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

Muatkan dan rumuskan masalah

Fahami format data masalah

Instance masalah daripada QOBLIB (Quantum Optimization Benchmarking Library) [2] disimpan dalam format teks yang mudah. Mari kita periksa kandungan sebenar instance sasaran kita 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

Struktur format:

• Baris pertama: 3 20

  • 3 = bilangan produk (kekangan/baris dalam matriks $A$)
  • 20 = bilangan pasaran (pemboleh ubah/lajur dalam matriks $A$)

• 3 baris seterusnya: Matriks pekali $A$ dan vektor sasaran $b$

  • Setiap baris mempunyai 21 nombor: 20 pertama ialah pekali baris, yang terakhir ialah sasaran
  • Baris 2: 60 92 161 ... 51 | 1002
    • 20 nombor pertama: Jumlah Produk 1 yang dijual oleh setiap daripada 20 pasaran
    • Nombor terakhir (1002): Sasaran jualan untuk Produk 1 dalam satu kawasan
  • Baris 3: 176 196 41 ... 46 | 879
    • Jualan Produk 2 setiap pasaran dan sasaran (879)
  • Baris 4: 68 68 179 ... 95 | 1040
    • Jualan Produk 3 setiap pasaran dan sasaran (1040)

Interpretasi perniagaan:

• Pasaran 0 menjual: 60 unit Produk 1, 176 unit Produk 2, 68 unit Produk 3
• Pasaran 1 menjual: 92 unit Produk 1, 196 unit Produk 2, 68 unit Produk 3
• Dan seterusnya untuk kesemua 20 pasaran...
• Matlamat: Bahagikan 20 pasaran ini kepada dua kawasan di mana setiap kawasan mendapat tepat 1002 unit Produk 1, 879 unit Produk 2, dan 1040 unit Produk 3

Transformasi QUBO

Dari kekangan kepada QUBO: transformasi matematik

Kekuatan pengoptimuman kuantum terletak pada transformasi masalah berkekangan kepada bentuk kuadratik tanpa kekangan [4]. Untuk masalah Market Split, kita menukar kekangan kesamaan

$Ax = b$

di mana $x ∈ \{0,1\}^n$, kepada QUBO dengan menghukum pelanggaran kekangan.

Kaedah penalti: Oleh kerana kita perlu $Ax = b$ dipegang secara tepat, kita meminimumkan pelanggaran kuasa dua: $f(x) = ||Ax - b||^2$

Ini sama dengan sifar tepat apabila semua kekangan dipenuhi. Mengembangkan secara algebra: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Objektif QUBO: Oleh kerana $b^T b$ adalah pemalar, pengoptimuman kita menjadi: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Pandangan utama: Transformasi ini adalah tepat, bukan hampiran. Kekangan kesamaan secara semula jadi dikuasakan dua kepada bentuk kuadratik tanpa memerlukan pemboleh ubah tambahan atau parameter penalti — menjadikan formulasi ini elegan secara matematik dan cekap dari segi pengiraan untuk penyelesai kuantum [4]. Kita akan menggunakan kelas OptimizationProblem untuk mentakrifkan masalah berkekangan kita, kemudian menukarnya kepada format QUBO menggunakan OptimizationProblemToQubo, kedua-duanya daripada pakej qiskit_addon_opt_mapper. Ini secara automatik mengendalikan transformasi berasaskan penalti.

Laksanakan fungsi pemuatan data dan penukaran QUBO

Kita kini mentakrifkan tiga fungsi utiliti:

1. parse_marketsplit_dat() - Menghurai format fail .dat dan mengekstrak matriks $A$ dan $b$
2. fetch_marketsplit_data() - Memuat turun instance masalah terus daripada repositori 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

Muatkan instance masalah

Kini kita muatkan instance masalah khusus ms_03_200_177.dat daripada QOBLIB [2]. Instance ini mempunyai:

• 3 produk (kekangan)
• 20 pasaran (pemboleh ubah keputusan binari)
• Lebih 1 juta tugasan pasaran yang mungkin untuk diterokai ($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"
    )

Tukar kepada format QUBO

Kita kini mengubah masalah pengoptimuman berkekangan kepada 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())}")

Tukar QUBO kepada format Iskay

Kini kita perlu menukar objek QUBO kepada format kamus yang diperlukan oleh Iskay Optimizer dari Kipu Quantum.

Argumen problem dan problem_type mengekod masalah pengoptimuman dalam bentuk

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

di mana

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

• Dengan memilih problem_type = "binary", anda menentukan bahawa fungsi kos adalah dalam format binary, yang bermaksud $D = \{0, 1\}^{n}$, iaitu fungsi kos ditulis dalam formulasi QUBO/HUBO.
• Sebaliknya, dengan memilih problem_type = "spin", fungsi kos ditulis dalam formulasi Ising, di mana $D = \{-1, 1\}^{n}$.

Pekali masalah perlu dikodkan dalam kamus seperti berikut:

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

Perhatikan bahawa kunci kamus mestilah rentetan yang mengandungi tuple integer yang tidak berulang yang sah. Untuk masalah binari, kita tahu bahawa:

$$x_i^2 = x_i$$

untuk $i=j$ (kerana $x_i \in \{0,1\}$ bermaksud $x_i \cdot x_i = x_i$). Jadi, dalam formulasi QUBO anda, jika anda mempunyai sumbangan linear $b_i x_i$ dan sumbangan kuadratik pepenjuru $c_{i,i} x_i^2$, sebutan-sebutan ini mesti digabungkan menjadi satu pekali linear:

Jumlah pekali linear untuk pemboleh ubah $x_i$: $b_i + c_{i,i}$

Ini bermaksud:

• Sebutan linear seperti "(i, )" mengandungi: pekali linear asal + pekali kuadratik pepenjuru
• Sebutan kuadratik pepenjuru seperti "(i, i)" TIDAK sepatutnya muncul dalam kamus akhir
• Hanya sebutan kuadratik bukan pepenjuru seperti "(i, j)" di mana $i \neq j$ perlu dimasukkan sebagai entri berasingan

Contoh: Jika QUBO anda mempunyai $3x_1 + 2x_1^2 + 4x_1 x_2$, kamus Iskay sepatutnya mengandungi:

• "(0, )": 5.0 (menggabungkan $3 + 2 = 5$)
• "(0, 1)": 4.0 (sebutan bukan pepenjuru)

BUKAN entri berasingan untuk "(0, )": 3.0 dan "(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!")

Fahami algoritma bf-DCQO

Sebelum kita menjalankan pengoptimuman, mari kita fahami algoritma kuantum canggih yang menguasai Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Apakah bf-DCQO?

bf-DCQO adalah berdasarkan evolusi masa sistem kuantum di mana penyelesaian masalah dikodkan dalam keadaan asas (keadaan tenaga terendah) Hamiltonian kuantum akhir [1]. Algoritma ini menangani cabaran asas dalam pengoptimuman kuantum:

Cabarannya: Pengkomputeran kuantum adiabatik tradisional memerlukan evolusi yang sangat perlahan untuk mengekalkan keadaan asas mengikut teorem adiabatik. Ini menuntut circuit kuantum yang semakin dalam apabila kerumitan masalah meningkat, membawa kepada lebih banyak operasi gate dan ralat yang terkumpul.

Penyelesaiannya: bf-DCQO menggunakan protokol counterdiabatic untuk membolehkan evolusi cepat sambil mengekalkan ketepatan keadaan asas, mengurangkan kedalaman circuit secara dramatik.

Rangka kerja matematik

Algoritma ini meminimumkan fungsi kos dalam bentuk:

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

di mana $D = \{0,1\}^n$ untuk pemboleh ubah binari dan:

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

Untuk masalah Market Split kita, fungsi kos ialah:

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

Peranan sebutan counterdiabatic

Sebutan counterdiabatic ialah sebutan tambahan yang diperkenalkan ke dalam Hamiltonian bergantung masa yang menekan pengujaan yang tidak diingini semasa evolusi kuantum. Inilah sebabnya ia penting:

Dalam pengoptimuman kuantum adiabatik, kita mengembangkan sistem mengikut Hamiltonian bergantung masa:

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

di mana $H_{\text{problem}}$ mengekodkan masalah pengoptimuman kita. Untuk mengekalkan keadaan asas semasa evolusi cepat, kita menambahkan sebutan counterdiabatic:

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

Sebutan counterdiabatic ini melakukan perkara berikut:

1. Menekan peralihan yang tidak diingini: Menghalang keadaan kuantum daripada melompat ke keadaan teruja semasa evolusi cepat
2. Membolehkan masa evolusi yang lebih singkat: Membenarkan kita mencapai keadaan akhir dengan lebih cepat tanpa melanggar adiabaticity
3. Mengurangkan kedalaman circuit: Evolusi yang lebih singkat membawa kepada lebih sedikit gate dan lebih sedikit ralat

Impak praktikalnya adalah dramatik: bf-DCQO menggunakan sehingga 10 kali lebih sedikit gate pembelit berbanding Digital Quantum Annealing [1], menjadikannya praktikal untuk perkakasan kuantum yang bising hari ini.

Pengoptimuman lelaran bias-field

Tidak seperti algoritma variatif yang mengoptimumkan parameter circuit melalui banyak lelaran, bf-DCQO menggunakan pendekatan berpandukan bias-field yang menumpu dalam kira-kira 10 lelaran [1]:

Proses lelaran:

1. Evolusi kuantum awal: Mulakan dengan circuit kuantum yang melaksanakan protokol evolusi counterdiabatic

2. Pengukuran: Ukur keadaan kuantum untuk mendapatkan taburan kebarangkalian merentasi rentetan bit

3. Pengiraan bias-field: Analisis statistik pengukuran dan hitung bias-field optimum $h_i$ untuk setiap qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Lelaran seterusnya: Bias-field mengubah suai Hamiltonian untuk lelaran seterusnya: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Ini membolehkan permulaan berhampiran penyelesaian baik yang ditemui sebelumnya, secara berkesan melakukan sejenis "carian setempat kuantum"

5. Penumpuan: Ulang sehingga kualiti penyelesaian stabil atau bilangan maksimum lelaran dicapai

Kelebihan utama: Setiap lelaran memberikan kemajuan bermakna ke arah penyelesaian optimum dengan menggabungkan maklumat daripada pengukuran sebelumnya, tidak seperti kaedah variatif yang mesti meneroka ruang parameter secara membuta.

Pasca-pemprosesan klasik bersepadu

Selepas pengoptimuman kuantum menumpu, Iskay melakukan pasca-pemprosesan carian setempat klasik:

• Penerokaan bit-flip: Membalikkan bit secara sistematik atau rawak dalam penyelesaian terbaik yang diukur
• Penilaian tenaga: Mengira $C(x)$ untuk setiap penyelesaian yang diubah suai
• Pemilihan tamak: Menerima penambahbaikan yang menurunkan fungsi kos
• Pelbagai laluan: Lakukan beberapa laluan (dikawal oleh postprocessing_level)

Pendekatan hibrid ini mengimbangi ralat bit-flip daripada ketidaksempurnaan perkakasan dan ralat pembacaan, memastikan penyelesaian berkualiti tinggi walaupun pada peranti kuantum yang bising.

Mengapa bf-DCQO cemerlang pada perkakasan semasa

Algoritma bf-DCQO direka khas untuk cemerlang pada peranti kuantum berskala pertengahan bising (NISQ) hari ini [1]:

1. Ketahanan terhadap ralat: Lebih sedikit gate (pengurangan 10 kali) bermaksud pengumpulan ralat yang jauh lebih sedikit
2. Tiada mitigasi ralat diperlukan: Kecekapan semula jadi algoritma menghapuskan keperluan untuk teknik mitigasi ralat yang mahal [1]
3. Kebolehskalaan: Boleh menangani masalah dengan sehingga 156 qubit (156 pemboleh ubah binari) dengan pemetaan qubit terus [1]
4. Prestasi terbukti: Mencapai nisbah hampiran 100% pada instance MaxCut dan HUBO penanda aras [1]

Sekarang mari kita lihat algoritma yang berkuasa ini beraksi pada masalah Market Split kita!

Langkah 2: Optimumkan masalah untuk pelaksanaan perkakasan kuantum

Algoritma bf-DCQO secara automatik mengendalikan pengoptimuman circuit, mewujudkan circuit kuantum yang cetek dengan sebutan counterdiabatic yang direka khas untuk Backend sasaran.

Konfigurasikan pengoptimuman

Iskay Optimizer memerlukan beberapa parameter utama untuk menyelesaikan masalah pengoptimuman anda dengan berkesan. Mari kita periksa setiap parameter dan peranannya dalam proses pengoptimuman kuantum:

Parameter yang diperlukan

Parameter	Jenis	Penerangan	Contoh
problem	Dict[str, float]	Pekali QUBO dalam format kunci rentetan	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Spesifikasi format: "binary" untuk QUBO atau "spin" untuk Ising	"binary"
backend_name	str	Peranti kuantum sasaran	"ibm_fez"

Konsep penting

• Format masalah: Kita gunakan "binary" kerana pemboleh ubah kita adalah binari (0/1), mewakili tugasan pasaran.
• Pemilihan Backend: Pilih antara QPU yang tersedia (contohnya, "ibm_fez") berdasarkan keperluan dan instance sumber pengiraan anda.
• Struktur QUBO: Kamus masalah kita mengandungi pekali tepat daripada transformasi matematik.

Pilihan lanjutan (pilihan)

Iskay menyediakan keupayaan penalaan halus melalui parameter pilihan. Walaupun nilai lalai berfungsi dengan baik untuk kebanyakan masalah, anda boleh menyesuaikan tingkah laku untuk keperluan khusus:

Parameter	Jenis	Lalai	Penerangan
shots	int	10000	Pengukuran kuantum setiap lelaran (lebih tinggi = lebih tepat)
num_iterations	int	10	Lelaran algoritma (lebih banyak lelaran boleh meningkatkan kualiti penyelesaian)
use_session	bool	True	Gunakan sesi IBM untuk masa giliran yang lebih singkat
seed_transpiler	int	None	Tetapkan untuk kompilasi circuit kuantum yang boleh dihasilkan semula
direct_qubit_mapping	bool	False	Petakan qubit maya terus kepada qubit fizikal
job_tags	List[str]	None	Tag tersuai untuk penjejakan kerja
preprocessing_level	int	0	Keamatan pra-pemprosesan masalah (0-3) - lihat butiran di bawah
postprocessing_level	int	2	Tahap penapisan penyelesaian (0-2) - lihat butiran di bawah
transpilation_level	int	0	Percubaan pengoptimuman Transpiler (0-5) - lihat butiran di bawah
transpile_only	bool	False	Analisis pengoptimuman circuit tanpa menjalankan pelaksanaan penuh

Tahap Pra-pemprosesan (0-3): Amat penting untuk masalah yang lebih besar yang pada masa ini tidak dapat muat dalam masa koherensi perkakasan. Tahap pra-pemprosesan yang lebih tinggi mencapai kedalaman circuit yang lebih cetek melalui hampiran dalam transpilasi masalah:

• Tahap 0: Tepat, circuit yang lebih panjang
• Tahap 1: Keseimbangan yang baik antara ketepatan dan hampiran, memotong hanya gate dengan sudut dalam persentil terendah 10
• Tahap 2: Hampiran yang sedikit lebih tinggi, memotong gate dengan sudut dalam persentil terendah 20 dan menggunakan approximation_degree=0.95 dalam transpilasi
• Tahap 3: Tahap hampiran maksimum, memotong gate dalam persentil terendah 30 dan menggunakan approximation_degree=0.90 dalam transpilasi

Tahap Transpilasi (0-5): Mengawal percubaan pengoptimuman Transpiler lanjutan untuk kompilasi circuit kuantum. Ini boleh menyebabkan peningkatan overhead klasik, dan untuk beberapa kes ia mungkin tidak mengubah kedalaman circuit. Nilai lalai 2 secara umum menghasilkan circuit terkecil dan agak pantas.

• Tahap 0: Pengoptimuman circuit DCQO yang didekomposisi (susun atur, penghalaan, penjadualan)
• Tahap 1: Pengoptimuman PauliEvolutionGate dan kemudian circuit DCQO yang didekomposisi (max_trials=10)
• Tahap 2: Pengoptimuman PauliEvolutionGate dan kemudian circuit DCQO yang didekomposisi (max_trials=15)
• Tahap 3: Pengoptimuman PauliEvolutionGate dan kemudian circuit DCQO yang didekomposisi (max_trials=20)
• Tahap 4: Pengoptimuman PauliEvolutionGate dan kemudian circuit DCQO yang didekomposisi (max_trials=25)
• Tahap 5: Pengoptimuman PauliEvolutionGate dan kemudian circuit DCQO yang didekomposisi (max_trials=50)

Tahap Pasca-pemprosesan (0-2): Mengawal jumlah pengoptimuman klasik, mengimbangi ralat bit-flip dengan bilangan laluan tamak yang berbeza dalam carian setempat:

• Tahap 0: 1 laluan
• Tahap 1: 2 laluan
• Tahap 2: 3 laluan

Mod transpile-only: Kini tersedia untuk pengguna yang ingin menganalisis pengoptimuman circuit tanpa menjalankan pelaksanaan algoritma kuantum penuh.

Contoh konfigurasi tersuai

Berikut adalah cara anda boleh mengkonfigurasi Iskay dengan tetapan berbeza:

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
}

Untuk tutorial ini, kita akan mengekalkan kebanyakan parameter lalai dan hanya mengubah bilangan lelaran 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")

Langkah 3: Laksanakan menggunakan primitif Qiskit

Kini kita hantar masalah kita untuk dijalankan pada perkakasan IBM Quantum. Algoritma bf-DCQO akan:

1. Membina circuit kuantum cetek dengan sebutan counterdiabatic
2. Melaksanakan kira-kira 10 lelaran dengan pengoptimuman bias-field
3. Melakukan pasca-pemprosesan klasik dengan carian setempat
4. Mengembalikan tugasan pasaran yang optimum

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

Pantau status kerja

Anda boleh menyemak status semasa kerja pengoptimuman anda. Status yang mungkin ialah:

• QUEUED: Kerja sedang menunggu dalam giliran
• RUNNING: Kerja sedang dilaksanakan pada perkakasan kuantum
• DONE: Kerja selesai dengan jayanya
• CANCELED: Kerja telah dibatalkan
• ERROR: Kerja menghadapi ralat

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

Tunggu sehingga selesai

Sel ini akan menghalang sehingga kerja selesai. Proses pengoptimuman merangkumi:

• Masa giliran (menunggu akses perkakasan kuantum)
• Masa pelaksanaan (menjalankan algoritma bf-DCQO dengan kira-kira 10 lelaran)
• Masa pasca-pemprosesan (carian setempat klasik)

Masa penyiapan biasa berkisar dari beberapa minit hingga puluhan minit bergantung kepada keadaan giliran.

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

Langkah 4: Pasca-proses dan kembalikan keputusan dalam format klasik yang diingini

Kini kita pasca-proses keputusan pelaksanaan kuantum. Ini merangkumi:

• Menganalisis struktur penyelesaian
• Mengesahkan pemenuhan kekangan
• Penanda aras berbanding pendekatan klasik

Analisis keputusan

Fahami struktur keputusan

Iskay mengembalikan kamus keputusan komprehensif yang mengandungi:

• solution: Kamus yang memetakan indeks pemboleh ubah kepada nilai optimum mereka (0 atau 1)
• solution_info: Maklumat terperinci termasuk:
  • bitstring: Tugasan optimum sebagai rentetan binari
  • cost: Nilai fungsi objektif (sepatutnya 0 untuk pemenuhan kekangan yang sempurna)
  • mapping: Cara kedudukan rentetan bit dipetakan kepada pemboleh ubah masalah
  • seed_transpiler: Benih yang digunakan untuk kebolehhasilan semula
• prob_type: Sama ada penyelesaian dalam format binari atau spin

Mari kita periksa penyelesaian yang dikembalikan oleh pengoptimum kuantum.

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

Pengesahan penyelesaian

Kini kita sahkan sama ada penyelesaian kuantum memenuhi kekangan Market Split. Proses pengesahan menyemak:

Apakah pelanggaran kekangan?

• Untuk setiap produk $i$, kita mengira jualan sebenar di Kawasan A: $(Ax)_i$
• Kita membandingkan ini dengan sasaran jualan $b_i$
• Pelanggaran ialah perbezaan mutlak: $|(Ax)_i - b_i|$
• Penyelesaian yang boleh dilaksanakan mempunyai sifar pelanggaran untuk semua produk

Apa yang kita jangkakan:

• Kes ideal: Jumlah pelanggaran = 0 (semua kekangan dipenuhi dengan sempurna)
  • Kawasan A mendapat tepat 1002 unit Produk 1, 879 unit Produk 2, dan 1040 unit Produk 3
  • Kawasan B mendapat unit yang selebihnya (juga 1002, 879, dan 1040 masing-masing)
• Kes baik: Jumlah pelanggaran adalah kecil (penyelesaian hampir optimum)
• Kes lemah: Pelanggaran besar menunjukkan penyelesaian tidak memenuhi keperluan perniagaan

Fungsi pengesahan akan mengira:

1. Jualan sebenar setiap produk dalam setiap kawasan
2. Pelanggaran kekangan untuk setiap produk
3. Pengagihan pasaran antara kawasan

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)

Tafsirkan keputusan pengesahan

Keputusan pengesahan menunjukkan sama ada Pengoptimum Kuantum menemui penyelesaian yang boleh dilaksanakan. Mari kita periksa perkara berikut:

Semakan kebolehlaksanaan:

• is_feasible = True bermaksud penyelesaian memenuhi semua kekangan dengan sempurna (jumlah pelanggaran = 0)
• is_feasible = False bermaksud beberapa kekangan dilanggar

Analisis jualan:

• Bandingkan jualan Sasaran berbanding Sebenar untuk setiap produk
• Untuk penyelesaian yang sempurna: Sebenar = Sasaran untuk semua produk dalam kedua-dua kawasan
• Perbezaan menunjukkan seberapa dekat kita dengan pembahagian pasaran yang diingini

Pengagihan pasaran:

• Menunjukkan berapa banyak pasaran yang ditugaskan kepada setiap kawasan
• Tiada keperluan untuk bilangan pasaran yang sama, hanya sasaran jualan yang perlu dipenuhi

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

Penilaian kualiti penyelesaian

Berdasarkan keputusan pengesahan di atas, kita boleh menilai kualiti penyelesaian kuantum:

Jika is_feasible = True (Jumlah pelanggaran = 0):

• Pengoptimum Kuantum berjaya menemui penyelesaian yang optimum
• Semua kekangan perniagaan dipenuhi dengan sempurna
• Ini menunjukkan kelebihan kuantum pada masalah di mana penyelesai klasik bergelut [4]

Jika is_feasible = False (Jumlah pelanggaran > 0):

• Penyelesaian adalah hampir optimum tetapi tidak sempurna
• Pelanggaran kecil mungkin boleh diterima dalam amalan
• Pertimbangkan untuk melaraskan parameter pengoptimum:
  • Tingkatkan num_iterations untuk lebih banyak laluan pengoptimuman
  • Tingkatkan postprocessing_level untuk lebih banyak penapisan klasik
  • Tingkatkan shots untuk statistik pengukuran yang lebih baik

Interpretasi fungsi kos:

• Nilai cost daripada solution_info sama dengan $||Ax - b||^2$
• Kos = 0 menunjukkan pemenuhan kekangan yang sempurna
• Nilai kos yang lebih tinggi menunjukkan pelanggaran kekangan yang lebih besar

Kesimpulan

Apa yang kita capai

Dalam tutorial ini, kita berjaya:

1. Memuatkan masalah pengoptimuman sebenar: Mendapatkan instance Market Split yang mencabar daripada perpustakaan penanda aras QOBLIB [2]
2. Mengubah kepada format QUBO: Menukar masalah berkekangan kepada formulasi kuadratik tanpa kekangan [3]
3. Memanfaatkan algoritma kuantum canggih: Menggunakan algoritma bf-DCQO dari Kipu Quantum dengan sebutan counterdiabatic [1]
4. Mendapatkan penyelesaian optimum: Menemui penyelesaian yang boleh dilaksanakan yang memenuhi semua kekangan

Pengajaran utama

Inovasi algoritma: Algoritma bf-DCQO mewakili kemajuan yang signifikan [1]:

• 10 kali lebih sedikit gate berbanding pengannilan kuantum digital
• Kira-kira 10 lelaran berbanding kira-kira 100 untuk kaedah variatif
• Ketahanan ralat terbina dalam melalui kecekapan circuit

Sebutan counterdiabatic: Membolehkan evolusi kuantum yang cepat sambil mengekalkan ketepatan keadaan asas, menjadikan pengoptimuman kuantum praktikal pada perkakasan yang bising hari ini [1].

Panduan bias-field: Pendekatan bias-field berulang membolehkan setiap lelaran bermula berhampiran penyelesaian baik yang ditemui sebelumnya, menyediakan sejenis carian setempat dipertingkatkan kuantum [1].

Langkah seterusnya

Untuk memperdalam pemahaman anda dan meneroka lebih lanjut:

1. Cuba instance berbeza: Eksperimen dengan instance QOBLIB lain dengan saiz yang berbeza-beza
2. Laraskan parameter: Ubah num_iterations, preprocessing_level, postprocessing_level
3. Bandingkan dengan kaedah klasik: Uji penanda aras berbanding penyelesai pengoptimuman klasik
4. Cuba strategi berbeza: Cuba cari pengekodan yang lebih baik untuk masalah atau formulasikannya sebagai HUBO (jika mungkin)
5. Terapkan pada domain anda: Sesuaikan teknik formulasi QUBO/HUBO kepada masalah pengoptimuman anda sendiri

Rujukan

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