Selesaikan masalah Market Split dengan Iskay Quantum Optimizer dari Kipu Quantum

Catatan

Qiskit Functions adalah fitur eksperimental yang hanya tersedia untuk pengguna IBM Quantum® Premium Plan, Flex Plan, dan On-Prem (melalui IBM Quantum Platform API) Plan. Fitur ini masih dalam status rilis pratinjau dan dapat berubah sewaktu-waktu.

Estimasi penggunaan: 20 detik pada prosesor Heron r2. (CATATAN: Ini hanya estimasi. Waktu eksekusi aktual bisa berbeda.)

Latar belakang

Tutorial ini menunjukkan cara menyelesaikan masalah Market Split menggunakan Iskay quantum optimizer dari Kipu Quantum [1]. Masalah Market Split merepresentasikan tantangan alokasi sumber daya di dunia nyata, di mana pasar harus dipartisi menjadi wilayah penjualan yang seimbang untuk memenuhi target permintaan yang tepat.

Tantangan Market Split

Masalah Market Split menghadirkan tantangan yang tampak sederhana namun secara komputasi sangat sulit dalam hal alokasi sumber daya. Bayangkan sebuah perusahaan dengan $m$ produk yang dijual di $n$ pasar berbeda, di mana setiap pasar membeli sekumpulan produk tertentu (direpresentasikan oleh kolom-kolom matriks $A$). Tujuan bisnis adalah membagi pasar-pasar tersebut menjadi dua wilayah penjualan yang seimbang sehingga setiap wilayah menerima tepat setengah dari total permintaan untuk setiap produk.

Formulasi matematis:

Kita mencari vektor penugasan biner $x$, di mana:

• $x_j = 1$ menugaskan pasar $j$ ke Wilayah A
• $x_j = 0$ menugaskan pasar $j$ ke Wilayah B
• Kendala $Ax = b$ harus dipenuhi, di mana $b$ merepresentasikan target penjualan (biasanya setengah dari total permintaan per produk)

Fungsi biaya:

Untuk menyelesaikan masalah ini, kita meminimalkan kuadrat pelanggaran kendala:

$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}$ merepresentasikan penjualan produk $i$ di pasar $j$
• $x_j \in \{0,1\}$ adalah penugasan biner pasar $j$
• $b_i$ adalah target penjualan produk $i$ di setiap wilayah
• Biaya sama dengan nol tepat ketika semua kendala terpenuhi

Setiap suku dalam jumlah mewakili deviasi kuadrat dari target penjualan untuk produk tertentu. Ketika kita mengekspansi fungsi biaya ini, kita mendapatkan:

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

Karena $b^T b$ adalah konstanta, meminimalkan $C(x)$ setara dengan meminimalkan fungsi kuadratik $x^T A^T A x - 2b^T A x$, yang merupakan masalah QUBO (Quadratic Unconstrained Binary Optimization).

Kompleksitas komputasi:

Meskipun interpretasi bisnisnya lugas, masalah ini menunjukkan kerumitan komputasi yang luar biasa:

• Kegagalan skala kecil: Solver Mixed Integer Programming konvensional gagal pada instans dengan hanya tujuh produk dalam batas waktu satu jam [4]
• Pertumbuhan eksponensial: Ruang solusi tumbuh secara eksponensial ($2^n$ kemungkinan penugasan), membuat pendekatan brute force tidak layak

Hambatan komputasi yang parah ini, dikombinasikan dengan relevansinya yang nyata dalam perencanaan wilayah dan alokasi sumber daya, menjadikan masalah Market Split sebagai tolok ukur ideal untuk algoritma optimasi kuantum [4].

Apa yang membuat pendekatan Iskay unik?

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

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

• Hingga 10 kali lebih sedikit entangling gate dibandingkan Digital Quantum Annealing (DQA)
• Circuit yang jauh lebih dangkal memungkinkan:
  • Akumulasi error yang lebih sedikit selama eksekusi kuantum
  • Kemampuan menangani masalah yang lebih besar pada perangkat keras kuantum saat ini
  • Tidak perlu teknik mitigasi error

Desain non-variasional: Berbeda dengan algoritma variasional yang membutuhkan sekitar 100 iterasi, bf-DCQO biasanya hanya membutuhkan sekitar 10 iterasi [1]. Hal ini dicapai melalui:

• Perhitungan bias-field yang cerdas dari distribusi state yang terukur
• Memulai setiap iterasi dari state energi dekat solusi sebelumnya
• Post-processing klasikal terintegrasi dengan local search

Protokol counterdiabatic: Algoritma ini menggabungkan suku-suku counterdiabatic yang menekan eksitasi kuantum yang tidak diinginkan selama waktu evolusi singkat, memungkinkan sistem tetap mendekati ground state bahkan dengan transisi cepat [1].

Persyaratan

Sebelum memulai tutorial ini, pastikan kamu telah menginstal hal-hal 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)

Kamu juga perlu mendapatkan akses ke fungsi Iskay Quantum Optimizer dari Qiskit Functions Catalog.

Pengaturan

Pertama, impor semua paket 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")

Konfigurasi kredensial IBM Quantum

Definisikan kredensial IBM Quantum® Platform kamu. Kamu akan membutuhkan:

• API Token: Kunci API 44 karakter dari IBM Quantum Platform
• Instance CRN: Pengenal instans IBM Cloud® kamu

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

Langkah 1: Petakan input klasikal ke masalah kuantum

Kita mulai dengan memetakan masalah klasikal kita ke representasi yang kompatibel dengan kuantum. Langkah ini melibatkan:

1. Menghubungkan ke Iskay Quantum Optimizer
2. Memuat dan memformulasikan masalah Market Split
3. Memahami algoritma bf-DCQO yang akan menyelesaikannya

Hubungkan ke Iskay Quantum Optimizer

Kita mulai dengan membuat koneksi ke Qiskit Functions Catalog dan memuat Iskay Quantum Optimizer. Iskay Optimizer adalah fungsi kuantum yang disediakan oleh Kipu Quantum yang mengimplementasikan algoritma bf-DCQO untuk menyelesaikan masalah optimasi pada perangkat keras 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")

Muat dan formulasikan masalah

Pahami format data masalah

Instans masalah dari QOBLIB (Quantum Optimization Benchmarking Library) [2] disimpan dalam format teks sederhana. Mari kita periksa konten aktual dari instans target 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 = jumlah produk (kendala/baris dalam matriks $A$)
  • 20 = jumlah pasar (variabel/kolom dalam matriks $A$)

• 3 baris berikutnya: Matriks koefisien $A$ dan vektor target $b$

  • Setiap baris memiliki 21 angka: 20 pertama adalah koefisien baris, terakhir adalah targetnya
  • Baris 2: 60 92 161 ... 51 | 1002
    • 20 angka pertama: Berapa banyak Produk 1 yang dijual masing-masing dari 20 pasar
    • Angka terakhir (1002): Target penjualan Produk 1 di satu wilayah
  • Baris 3: 176 196 41 ... 46 | 879
    • Penjualan Produk 2 per pasar dan target (879)
  • Baris 4: 68 68 179 ... 95 | 1040
    • Penjualan Produk 3 per pasar dan target (1040)

Interpretasi bisnis:

• Pasar 0 menjual: 60 unit Produk 1, 176 unit Produk 2, 68 unit Produk 3
• Pasar 1 menjual: 92 unit Produk 1, 196 unit Produk 2, 68 unit Produk 3
• Dan seterusnya untuk semua 20 pasar...
• Tujuan: Bagi 20 pasar ini menjadi dua wilayah di mana setiap wilayah mendapatkan tepat 1002 unit Produk 1, 879 unit Produk 2, dan 1040 unit Produk 3

Transformasi QUBO

Dari kendala ke QUBO: transformasi matematis

Kekuatan optimasi kuantum terletak pada transformasi masalah berkendala menjadi bentuk kuadratik tanpa kendala [4]. Untuk masalah Market Split, kita mengonversi kendala persamaan

$Ax = b$

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

Metode penalti: Karena kita membutuhkan $Ax = b$ terpenuhi secara tepat, kita meminimalkan kuadrat pelanggaran: $f(x) = ||Ax - b||^2$

Ini sama dengan nol tepat ketika semua kendala terpenuhi. Mengekspansi secara aljabar: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Objektif QUBO: Karena $b^T b$ adalah konstanta, optimasi kita menjadi: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Wawasan utama: Transformasi ini bersifat eksak, bukan aproksimasi. Kendala persamaan secara alami dikuadratkan menjadi bentuk kuadratik tanpa membutuhkan variabel bantu atau parameter penalti — menjadikan formulasi ini elegan secara matematis dan efisien secara komputasi untuk solver kuantum [4]. Kita akan menggunakan kelas OptimizationProblem untuk mendefinisikan masalah berkendala kita, lalu mengonversinya ke format QUBO menggunakan OptimizationProblemToQubo, keduanya dari paket qiskit_addon_opt_mapper. Ini secara otomatis menangani transformasi berbasis penalti.

Implementasi fungsi pemuatan data dan konversi QUBO

Kita sekarang mendefinisikan tiga fungsi utilitas:

1. parse_marketsplit_dat() - Mengurai format file .dat dan mengekstrak matriks $A$ dan $b$
2. fetch_marketsplit_data() - Mengunduh instans masalah langsung dari 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

Muat instans masalah

Sekarang kita memuat instans masalah spesifik ms_03_200_177.dat dari QOBLIB [2]. Instans ini memiliki:

• 3 produk (kendala)
• 20 pasar (variabel keputusan biner)
• Lebih dari 1 juta kemungkinan penugasan pasar untuk dieksplorasi ($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"
    )

Konversi ke format QUBO

Kita sekarang mentransformasi masalah optimasi berkendala menjadi 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())}")

Konversi QUBO ke format Iskay

Sekarang kita perlu mengonversi objek QUBO ke format kamus yang diperlukan oleh Iskay Optimizer dari Kipu Quantum.

Argumen problem dan problem_type mengodekan masalah optimasi 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", kamu menentukan bahwa fungsi biaya dalam format binary, yang berarti $D = \{0, 1\}^{n}$, yaitu fungsi biaya ditulis dalam formulasi QUBO/HUBO.
• Di sisi lain, dengan memilih problem_type = "spin", fungsi biaya ditulis dalam formulasi Ising, di mana $D = \{-1, 1\}^{n}$.

Koefisien masalah harus dikodekan dalam kamus sebagai 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 bahwa kunci kamus harus berupa string yang mengandung tuple integer non-berulang yang valid. Untuk masalah biner, kita tahu bahwa:

$$x_i^2 = x_i$$

untuk $i=j$ (karena $x_i \in \{0,1\}$ berarti $x_i \cdot x_i = x_i$). Jadi, dalam formulasi QUBO kamu, jika kamu memiliki kontribusi linear $b_i x_i$ dan kontribusi kuadratik diagonal $c_{i,i} x_i^2$, suku-suku ini harus digabungkan menjadi satu koefisien linear:

Total koefisien linear untuk variabel $x_i$: $b_i + c_{i,i}$

Ini berarti:

• Suku linear seperti "(i, )" mengandung: koefisien linear asli + koefisien kuadratik diagonal
• Suku kuadratik diagonal seperti "(i, i)" TIDAK boleh muncul dalam kamus akhir
• Hanya suku kuadratik off-diagonal seperti "(i, j)" di mana $i \neq j$ yang harus dimasukkan sebagai entri terpisah

Contoh: Jika QUBO kamu memiliki $3x_1 + 2x_1^2 + 4x_1 x_2$, kamus Iskay harus mengandung:

• "(0, )": 5.0 (menggabungkan $3 + 2 = 5$)
• "(0, 1)": 4.0 (suku off-diagonal)

BUKAN entri terpisah 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!")

Pahami algoritma bf-DCQO

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

Apa itu bf-DCQO?

bf-DCQO didasarkan pada evolusi waktu sistem kuantum di mana solusi masalah dikodekan dalam ground state (state energi terendah) dari Hamiltonian kuantum akhir [1]. Algoritma ini mengatasi tantangan mendasar dalam optimasi kuantum:

Tantangannya: Komputasi kuantum adiabatik tradisional membutuhkan evolusi yang sangat lambat untuk mempertahankan kondisi ground state sesuai dengan teorema adiabatik. Ini membutuhkan Circuit yang semakin dalam seiring bertambahnya kompleksitas masalah, menghasilkan lebih banyak operasi gate dan akumulasi error.

Solusinya: bf-DCQO menggunakan protokol counterdiabatic untuk memungkinkan evolusi cepat sambil mempertahankan fidelitas ground state, yang secara dramatis mengurangi kedalaman Circuit.

Kerangka matematis

Algoritma meminimalkan fungsi biaya 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 variabel biner 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 biayanya adalah:

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

Peran suku-suku counterdiabatic

Suku-suku counterdiabatic adalah suku-suku tambahan yang dimasukkan ke dalam Hamiltonian bergantung-waktu yang menekan eksitasi yang tidak diinginkan selama evolusi kuantum. Berikut mengapa mereka sangat penting:

Dalam optimasi kuantum adiabatik, kita mengevolusi sistem sesuai dengan Hamiltonian bergantung-waktu:

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

di mana $H_{\text{problem}}$ mengodekan masalah optimasi kita. Untuk mempertahankan ground state selama evolusi cepat, kita menambahkan suku-suku counterdiabatic:

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

Suku-suku counterdiabatic ini melakukan hal berikut:

1. Menekan transisi yang tidak diinginkan: Mencegah state kuantum melompat ke state tereksitasi selama evolusi cepat
2. Memungkinkan waktu evolusi yang lebih singkat: Memungkinkan kita mencapai state akhir jauh lebih cepat tanpa melanggar adiabatisitas
3. Mengurangi kedalaman Circuit: Evolusi yang lebih singkat menghasilkan lebih sedikit gate dan lebih sedikit error

Dampak praktisnya sangat dramatis: bf-DCQO menggunakan hingga 10 kali lebih sedikit entangling gate dibandingkan Digital Quantum Annealing [1], membuatnya praktis untuk perangkat keras kuantum saat ini yang masih bising.

Optimasi iteratif berbasis bias-field

Berbeda dengan algoritma variasional yang mengoptimalkan parameter Circuit melalui banyak iterasi, bf-DCQO menggunakan pendekatan berbasis bias-field yang konvergen dalam sekitar 10 iterasi [1]:

Proses iterasi:

1. Evolusi kuantum awal: Mulai dengan Circuit kuantum yang mengimplementasikan protokol evolusi counterdiabatic

2. Pengukuran: Ukur state kuantum untuk mendapatkan distribusi probabilitas atas bitstring

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

4. Iterasi berikutnya: Bias-field memodifikasi Hamiltonian untuk iterasi berikutnya: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Ini memungkinkan memulai dekat solusi baik yang ditemukan sebelumnya, secara efektif melakukan "quantum local search"

5. Konvergensi: Ulangi hingga kualitas solusi stabil atau jumlah iterasi maksimum tercapai

Keunggulan utama: Setiap iterasi memberikan kemajuan berarti menuju solusi optimal dengan menggabungkan informasi dari pengukuran sebelumnya, tidak seperti metode variasional yang harus mengeksplorasi ruang parameter secara buta.

Post-processing klasikal terintegrasi

Setelah optimasi kuantum konvergen, Iskay melakukan local search post-processing klasikal:

• Eksplorasi bit-flip: Membalik bit secara sistematis atau acak dalam solusi terukur terbaik
• Evaluasi energi: Hitung $C(x)$ untuk setiap solusi yang dimodifikasi
• Seleksi greedy: Terima perbaikan yang menurunkan fungsi biaya
• Beberapa pass: Lakukan beberapa pass (dikontrol oleh postprocessing_level)

Pendekatan hybrid ini mengkompensasi error bit-flip dari ketidaksempurnaan perangkat keras dan error readout, memastikan solusi berkualitas tinggi bahkan pada perangkat kuantum yang bising.

Mengapa bf-DCQO unggul pada perangkat keras saat ini

Algoritma bf-DCQO dirancang khusus untuk unggul pada perangkat kuantum noisy intermediate-scale (NISQ) saat ini [1]:

1. Ketahanan terhadap error: Lebih sedikit gate (pengurangan 10 kali) berarti akumulasi error yang jauh lebih sedikit
2. Tidak perlu mitigasi error: Efisiensi inheren algoritma menghilangkan kebutuhan teknik mitigasi error yang mahal [1]
3. Skalabilitas: Dapat menangani masalah dengan hingga 156 qubit (156 variabel biner) dengan direct qubit-mapping [1]
4. Kinerja terbukti: Mencapai rasio aproksimasi 100% pada instans benchmark MaxCut dan HUBO [1]

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

Langkah 2: Optimalkan masalah untuk eksekusi di perangkat keras kuantum

Algoritma bf-DCQO secara otomatis menangani optimasi Circuit, membuat Circuit kuantum dangkal dengan suku-suku counterdiabatic yang dirancang khusus untuk Backend yang dituju.

Konfigurasi optimasi

Iskay Optimizer memerlukan beberapa parameter kunci untuk menyelesaikan masalah optimasi kamu secara efektif. Mari kita lihat setiap parameter dan perannya dalam proses optimasi kuantum:

Parameter yang wajib ada

Parameter	Tipe	Deskripsi	Contoh
problem	Dict[str, float]	Koefisien QUBO dalam format string-key	{"()": -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	Perangkat kuantum yang dituju	"ibm_fez"

Konsep penting

• Format masalah: Kita pakai "binary" karena variabel-variabel kita bersifat biner (0/1), yang merepresentasikan penugasan pasar.
• Pemilihan Backend: Pilih dari QPU yang tersedia (misalnya, "ibm_fez") sesuai kebutuhan dan instance sumber daya komputasi kamu.
• Struktur QUBO: Kamus masalah kita berisi koefisien-koefisien yang tepat dari transformasi matematis.

Opsi lanjutan (opsional)

Iskay menyediakan kemampuan penyetelan halus melalui parameter opsional. Meski nilai default-nya sudah bekerja dengan baik untuk kebanyakan masalah, kamu bisa menyesuaikan perilakunya untuk kebutuhan spesifik:

Parameter	Tipe	Default	Deskripsi
shots	int	10000	Pengukuran kuantum per iterasi (lebih tinggi = lebih akurat)
num_iterations	int	10	Iterasi algoritma (lebih banyak iterasi bisa meningkatkan kualitas solusi)
use_session	bool	True	Gunakan Session IBM untuk waktu antre yang lebih singkat
seed_transpiler	int	None	Tetapkan untuk kompilasi Circuit kuantum yang dapat direproduksi
direct_qubit_mapping	bool	False	Petakan Qubit virtual langsung ke Qubit fisik
job_tags	List[str]	None	Tag kustom untuk pelacakan job
preprocessing_level	int	0	Intensitas pra-pemrosesan masalah (0-3) - lihat detail di bawah
postprocessing_level	int	2	Level penyempurnaan solusi (0-2) - lihat detail di bawah
transpilation_level	int	0	Percobaan optimasi Transpiler (0-5) - lihat detail di bawah
transpile_only	bool	False	Analisis optimasi Circuit tanpa menjalankan eksekusi penuh

Level Preprocessing (0-3): Sangat penting untuk masalah yang lebih besar yang saat ini tidak bisa muat dalam waktu koherensi perangkat keras. Level preprocessing yang lebih tinggi menghasilkan kedalaman Circuit yang lebih dangkal melalui aproksimasi dalam transpilasi masalah:

• Level 0: Eksak, Circuit lebih panjang
• Level 1: Keseimbangan baik antara akurasi dan aproksimasi, hanya memotong Gate dengan sudut di persentil 10 terendah
• Level 2: Aproksimasi sedikit lebih tinggi, memotong Gate dengan sudut di persentil 20 terendah dan menggunakan approximation_degree=0.95 dalam transpilasi
• Level 3: Level aproksimasi maksimum, memotong Gate di persentil 30 terendah dan menggunakan approximation_degree=0.90 dalam transpilasi

Level Transpilasi (0-5): Mengontrol percobaan optimasi Transpiler lanjutan untuk kompilasi Circuit kuantum. Ini bisa menyebabkan peningkatan overhead klasik, dan untuk beberapa kasus mungkin tidak mengubah kedalaman Circuit. Nilai default 2 secara umum menghasilkan Circuit terkecil dan relatif cepat.

• Level 0: Optimasi Circuit DCQO yang sudah didekomposisi (layout, routing, scheduling)
• Level 1: Optimasi PauliEvolutionGate lalu Circuit DCQO yang sudah didekomposisi (max_trials=10)
• Level 2: Optimasi PauliEvolutionGate lalu Circuit DCQO yang sudah didekomposisi (max_trials=15)
• Level 3: Optimasi PauliEvolutionGate lalu Circuit DCQO yang sudah didekomposisi (max_trials=20)
• Level 4: Optimasi PauliEvolutionGate lalu Circuit DCQO yang sudah didekomposisi (max_trials=25)
• Level 5: Optimasi PauliEvolutionGate lalu Circuit DCQO yang sudah didekomposisi (max_trials=50)

Level Postprocessing (0-2): Mengontrol seberapa banyak optimasi klasik yang mengkompensasi kesalahan bit-flip dengan jumlah greedy pass yang berbeda dari local search:

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

Mode transpile-only: Kini tersedia untuk pengguna yang ingin menganalisis optimasi Circuit tanpa menjalankan eksekusi algoritma kuantum penuh.

Contoh konfigurasi kustom

Berikut cara mengonfigurasi Iskay dengan pengaturan berbeda:

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 memakai sebagian besar parameter default dan hanya mengubah jumlah iterasi 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: Eksekusi menggunakan Qiskit primitives

Kita sekarang mengirimkan masalah kita untuk dijalankan di perangkat keras IBM Quantum. Algoritma bf-DCQO akan:

1. Membangun Circuit kuantum dangkal dengan suku-suku counterdiabatic
2. Mengeksekusi sekitar 10 iterasi dengan optimasi bias-field
3. Melakukan post-processing klasik dengan local search
4. Mengembalikan penugasan pasar yang optimal

# 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 job

Kamu bisa memeriksa status terkini dari job optimasi kamu. Status yang mungkin muncul adalah:

• QUEUED: Job sedang menunggu dalam antrean
• RUNNING: Job sedang dieksekusi di perangkat keras kuantum
• DONE: Job selesai dengan sukses
• CANCELED: Job dibatalkan
• ERROR: Job mengalami error

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

Tunggu hingga selesai

Cell ini akan memblokir hingga job selesai. Proses optimasi mencakup:

• Waktu antre (menunggu akses ke perangkat keras kuantum)
• Waktu eksekusi (menjalankan algoritma bf-DCQO dengan sekitar 10 iterasi)
• Waktu post-processing (local search klasik)

Waktu penyelesaian biasanya berkisar dari beberapa menit hingga puluhan menit tergantung kondisi antrean.

# 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: Post-process dan kembalikan hasil dalam format klasik yang diinginkan

Kita sekarang melakukan post-process pada hasil eksekusi kuantum. Ini mencakup:

• Menganalisis struktur solusi
• Memvalidasi pemenuhan constraint
• Membandingkan dengan pendekatan klasik

Analisis hasil

Memahami struktur hasil

Iskay mengembalikan kamus hasil yang komprehensif yang berisi:

• solution: Kamus yang memetakan indeks variabel ke nilai optimalnya (0 atau 1)
• solution_info: Informasi detail yang meliputi:
  • bitstring: Penugasan optimal sebagai string biner
  • cost: Nilai fungsi objektif (seharusnya 0 untuk pemenuhan constraint yang sempurna)
  • mapping: Bagaimana posisi bitstring dipetakan ke variabel masalah
  • seed_transpiler: Seed yang digunakan untuk reproduktibilitas
• prob_type: Apakah solusinya dalam format biner atau spin

Mari kita periksa solusi yang dikembalikan oleh optimizer 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("  ...")

Validasi solusi

Sekarang kita validasi apakah solusi kuantum memenuhi constraint Market Split. Proses validasi memeriksa:

Apa itu pelanggaran constraint?

• Untuk setiap produk $i$, kita hitung penjualan aktual di Wilayah A: $(Ax)_i$
• Kita bandingkan ini dengan target penjualan $b_i$
• Pelanggaran adalah selisih absolut: $|(Ax)_i - b_i|$
• Solusi yang layak memiliki nol pelanggaran untuk semua produk

Yang kita harapkan:

• Kasus ideal: Total pelanggaran = 0 (semua constraint terpenuhi dengan sempurna)
  • Wilayah A mendapat tepat 1002 unit Produk 1, 879 unit Produk 2, dan 1040 unit Produk 3
  • Wilayah B mendapat unit yang tersisa (juga 1002, 879, dan 1040 masing-masing)
• Kasus baik: Total pelanggaran kecil (solusi hampir optimal)
• Kasus buruk: Pelanggaran besar menunjukkan solusi tidak memenuhi persyaratan bisnis

Fungsi validasi akan menghitung:

1. Penjualan aktual per produk di setiap wilayah
2. Pelanggaran constraint untuk setiap produk
3. Distribusi pasar antara wilayah

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)

Interpretasi hasil validasi

Hasil validasi menunjukkan apakah Quantum Optimizer menemukan solusi yang layak. Mari kita periksa hal-hal berikut:

Pemeriksaan kelayakan:

• is_feasible = True berarti solusi memenuhi semua constraint dengan sempurna (total pelanggaran = 0)
• is_feasible = False berarti ada beberapa constraint yang dilanggar

Analisis penjualan:

• Bandingkan Target versus Penjualan Aktual untuk setiap produk
• Untuk solusi yang sempurna: Aktual = Target untuk semua produk di kedua wilayah
• Selisihnya menunjukkan seberapa dekat kita dengan pembagian pasar yang diinginkan

Distribusi pasar:

• Menunjukkan berapa banyak pasar yang ditugaskan ke setiap wilayah
• Tidak ada persyaratan untuk jumlah pasar yang sama, hanya target penjualan yang harus terpenuhi

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 kualitas solusi

Berdasarkan hasil validasi di atas, kita bisa menilai kualitas solusi kuantum:

Jika is_feasible = True (Total pelanggaran = 0):

• Quantum Optimizer berhasil menemukan solusi yang optimal
• Semua constraint bisnis terpenuhi dengan sempurna
• Ini mendemonstrasikan keunggulan kuantum pada masalah di mana solver klasik kesulitan [4]

Jika is_feasible = False (Total pelanggaran > 0):

• Solusinya hampir optimal tapi tidak sempurna
• Pelanggaran kecil mungkin masih bisa diterima dalam praktik
• Pertimbangkan untuk menyesuaikan parameter optimizer:
  • Tambah num_iterations untuk lebih banyak pass optimasi
  • Tambah postprocessing_level untuk lebih banyak penyempurnaan klasik
  • Tambah shots untuk statistik pengukuran yang lebih baik

Interpretasi fungsi cost:

• Nilai cost dari solution_info sama dengan $||Ax - b||^2$
• Cost = 0 menandakan pemenuhan constraint yang sempurna
• Nilai cost yang lebih tinggi menandakan pelanggaran constraint yang lebih besar

Kesimpulan

Yang berhasil kita capai

Dalam tutorial ini, kita berhasil:

1. Memuat masalah optimasi nyata: Mendapatkan instance Market Split yang menantang dari pustaka benchmark QOBLIB [2]
2. Transformasi ke format QUBO: Mengubah masalah yang ada constraint menjadi formulasi kuadratik tanpa constraint [3]
3. Memanfaatkan algoritma kuantum canggih: Menggunakan algoritma bf-DCQO Kipu Quantum dengan suku-suku counterdiabatic [1]
4. Mendapatkan solusi optimal: Menemukan solusi yang layak yang memenuhi semua constraint

Poin-poin utama

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

• 10 kali lebih sedikit Gate dibandingkan digital quantum annealing
• Sekitar 10 iterasi alih-alih sekitar 100 untuk metode variasional
• Ketahanan terhadap error yang built-in melalui efisiensi Circuit

Suku-suku counterdiabatic: Memungkinkan evolusi kuantum yang cepat sambil mempertahankan kesetiaan ground state, membuat optimasi kuantum praktis di perangkat keras berderau saat ini [1].

Panduan bias-field: Pendekatan bias-field iteratif memungkinkan setiap iterasi untuk memulai dekat dengan solusi baik yang ditemukan sebelumnya, memberikan bentuk quantum-enhanced local search [1].

Langkah selanjutnya

Untuk memperdalam pemahaman kamu dan mengeksplorasi lebih jauh:

1. Coba instance berbeda: Eksperimen dengan instance QOBLIB lain dari berbagai ukuran
2. Setel parameter: Sesuaikan num_iterations, preprocessing_level, postprocessing_level
3. Bandingkan dengan klasik: Lakukan benchmark terhadap solver optimasi klasik
4. Coba strategi berbeda: Coba temukan encoding yang lebih baik untuk masalah atau formulasikan sebagai HUBO (jika memungkinkan)
5. Terapkan ke domain kamu: Adaptasikan teknik formulasi QUBO/HUBO ke masalah optimasi kamu sendiri

Referensi

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