Selesaikan masalah market split dengan ParityQC Parity Twine Optimizer

Perkiraan penggunaan: 10 detik pada prosesor Nighthawk r2. (CATATAN: Ini hanya perkiraan. Runtime Anda mungkin berbeda.)

Hasil Pembelajaran

• Mendapatkan dan memformat masalah Market Split dari QOBLIB - Quantum Optimization Benchmarking Library.

• Menyiapkan dan menggunakan Parity Twine Optimizer untuk menyelesaikan sebuah instance Market Split.

• Pelajari cara memilih opsi untuk Parity Twine Optimizer dan hasil apa yang dikeluarkan.

Latar Belakang

Tutorial ini mendemonstrasikan cara menyelesaikan masalah Market Split menggunakan ParityQC Parity Twine Optimizer.

Instance masalah ini diperoleh dari QOBLIB - Quantum Optimization Benchmarking Library.

Masalah market split

Masalah market split adalah masalah alokasi sumber daya dunia nyata yang bersifat NP-hard dan telah menjadi benchmark untuk algoritme optimisasi kuantum. Ini merepresentasikan tantangan logistik yang berisiko tinggi: bagaimana membagi lanskap pelanggan dan produk yang kompleks menjadi wilayah-wilayah yang dapat dikelola dan setara.

Tujuannya adalah membagi $n$ pasar menjadi dua wilayah penjualan yang seimbang sedemikian rupa sehingga setiap wilayah menerima tepat setengah dari total permintaan untuk $m$ produk. Solusinya adalah konfigurasi spesifik yang mencapai distribusi permintaan produk paling merata yang mungkin, memungkinkan sebuah perusahaan menerapkan strategi logistik dan staf di mana kedua wilayah seimbang, meminimalkan risiko seperti kekurangan produk lokal atau kelebihan kapasitas gudang.

Seiring bertambahnya jumlah pasar dan produk, jumlah kemungkinan permutasi tumbuh secara eksponensial, sehingga menyulitkan pencarian pembagian terbaik menggunakan pencarian menyeluruh (exhaustive search) tradisional.

Formulasi matematis

Misalkan $A$ adalah matriks $m \times n$ yang merepresentasikan permintaan produk di seluruh pasar, di mana $A_{ij}$ adalah permintaan untuk produk $i$ di pasar $j$.

Sebuah vektor penugasan biner, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, didefinisikan di mana:

• $x_j = 1$ menugaskan pasar $j$ ke Wilayah A.
• $x_j = 0$ menugaskan pasar $j$ ke Wilayah B.

Misalkan $d = [d_1, d_2, \dots, d_m]^T$ adalah vektor total permintaan untuk setiap produk, dihitung sebagai $d = A \cdot \mathbf{1}$. Target volume penjualan per wilayah untuk produk $i$ adalah tepat $\frac{d_i}{2}$.

Kendala optimisasi atau kelayakan mensyaratkan bahwa total penjualan yang dialokasikan ke Wilayah A sama persis dengan setengah dari total permintaan untuk setiap produk:

$A x = \frac{1}{2} A \mathbf{1} = b.$

Dalam praktiknya, karena pembagian yang eksak jarang memungkinkan, masalah ini diformulasikan untuk meminimalkan kuadrat pelanggaran kendala (fungsi biaya):

$\min_{x} \left\Vert{} A x - b \right\Vert{}^2 = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} A_{ij} x_j - b\right)^2.$

Menjabarkan persamaan ini menghasilkan bentuk yang setara dengan masalah quadratic unconstrained binary optimization (QUBO).

Setelah diselesaikan, vektor solusi $x$ menentukan ke wilayah mana sebuah pasar ditugaskan. Ini adalah konfigurasi yang mencapai distribusi permintaan produk paling seimbang yang mungkin.

Persyaratan

Sebelum memulai tutorial ini, pastikan hal berikut telah terinstal:

• Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

Anda juga memerlukan izin untuk mengakses function ParityQC Twine Optimizer. Untuk meminta akses, lengkapi formulir ini.

Pengaturan

(Kode ini mengasumsikan Anda sudah menyimpan akun Anda ke lingkungan lokal Anda.)

Pertama, impor semua paket yang diperlukan untuk tutorial ini.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"numpy": "numpy", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog", "requests": "requests"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

import tempfile

from collections.abc import Callable
from pathlib import Path

import numpy as np
import requests

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

Muat Parity Twine Optimizer dari katalog Qiskit Functions:

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
function = catalog.load("parityqc/parity-twine-optimizer")

Langkah 1: Definisikan masalah sebagai fungsi objektif

Dapatkan instance masalah market split dari QOBLIB - Quantum Optimization Benchmarking Library sebagai berikut.

Fungsi load_market_split_problem mengambil masalah tertentu dari QOBLIB dan mengonversinya menjadi masalah QUBO.

def load_market_split_problem(instance_name: str) -> OptimizationProblem:
    """Load and formulate a market split optimization problem from an QOBLIB instance.

    The QOBLIB library can be found here:
    https://github.com/ZIB-AOPT/QOBLIB.

    Args:
        instance_name: Name of the market split instance to load as specified by the .dat file
            in the QOBLIB repo.

    Returns:
        The output OptimizationProblem containing the loaded market split problem.
    """

    problem_matrix, problem_vector = fetch_and_parse(
        instance_name, "01-marketsplit", parse_marketsplit_dat
    )

    # Create optimization problem
    optimization_problem = OptimizationProblem(instance_name)

    # Add binary variables (one for each market)
    optimization_problem.binary_var_list(problem_matrix.shape[1])

    # Add equality constraints (one for each product)
    for idx, rhs in enumerate(problem_vector):
        optimization_problem.linear_constraint(
            problem_matrix[idx, :], sense="==", rhs=rhs
        )

    # Convert to QUBO with penalty parameter
    return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)

Fungsi load_market_split_problem memerlukan fungsi parser berikut untuk mengambil dan memproses data masalah market split dari QOBLIB.

def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):
    """Generic function to fetch and parse data from QOBLIB repository.

    Args:
        instance_name: Name of the instance to fetch.
        problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').
        parse_func: Function used to parse the downloaded file
            (e.g., parse_marketsplit_dat, parse_gph_file).

    Returns:
        Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit
        or nx.Graph for MIS.
    """
    base_url = (
        "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/"
    )
    url = (
        base_url
        + problem
        + "/instances/"
        + instance_name
        + (".dat" if problem == "01-marketsplit" else ".gph")
    )

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w",
            suffix=".dat" if problem == "01-marketsplit" else ".gph",
            delete=False,
            encoding="utf-8",
        ) as temp_file:
            temp_file.write(response.text)
            temp_file_path = temp_file.name

        try:
            return parse_func(temp_file_path)
        finally:
            Path(temp_file_path).unlink(missing_ok=True)

    except requests.RequestException as e:
        print(f"Error fetching data from repository: {e}")
    except (ValueError, OSError) as e:
        print(f"Error processing data: {e}")
        return None

def parse_marketsplit_dat(filename: str) -> tuple[np.ndarray, np.ndarray]:
    """Parse a market split problem from a .dat file format.

    Args:
        filename: Path to the .dat file.

    Returns:
        Tuple of (A, b) where:
            - A: (m, n) array of coefficients.
            - b: (m,) array of target values.

    Raises:
        ValueError: If file format is invalid or file is empty.
    """
    with Path(filename).open(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)
    try:
        m, n = map(int, lines[0].split())
    except (ValueError, IndexError) as e:
        raise ValueError(
            "Invalid file format: first line must contain 'm n' integers"
        ) from e

    if len(lines) < m + 1:
        raise ValueError(
            f"File contains {len(lines)} lines but expected {m + 1} lines"
        )

    # Next m lines: each row of A followed by corresponding element of b
    mat_a = []
    vec_b = []

    for i in range(1, m + 1):
        try:
            values = list(map(int, lines[i].split()))
        except ValueError as e:
            raise ValueError(f"Invalid integer values in line {i + 1}") from e

        if len(values) != n + 1:
            raise ValueError(
                f"Line {i + 1} contains {len(values)} values but expected {n + 1}"
            )

        mat_a.append(values[:-1])  # First n values: product sales per market
        vec_b.append(values[-1])  # Last value: target sales for this product

    return np.array(mat_a), np.array(vec_b)

Setelah didefinisikan, load_marketsplit_problem dapat digunakan untuk memuat instance masalah tertentu dari library:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Langkah 2: Konversi ke format JSON

Pada langkah pertama, Anda memperoleh bentuk QUBO dari masalah tersebut. Sekarang, konversikan ke format JSON untuk fungsi optimizer:

def optimization_problem_to_json(
    problem: OptimizationProblem,
) -> dict[str, float]:
    """
    Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables
    to the JSON input format of the Parity Twine Qiskit Function.

    Args:
        problem: The optimization problem to convert to JSON.

    Returns:
        The JSON input format of the given problem.
    """
    ising, constant = problem.to_ising()
    output = {"()": float(constant)}
    for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):
        # Invert the label strings because Qiskit has opposite convention
        qubits = tuple(
            num
            for num, pauli in enumerate(op.to_label()[::-1])
            if pauli == "Z"
        )
        output[str(qubits)] = float(coefficient)
    return output

Instance QUBO dari masalah Market Split sekarang dikonversi ke format JSON sebagai berikut:

json_ms_problem = optimization_problem_to_json(ms_problem)

Langkah 3: Selesaikan masalah menggunakan Parity Twine Optimizer

Sekarang setelah Anda memperoleh masalah market split dan mengonversinya ke bentuk yang benar, Anda dapat menemukan solusi dengan menggunakan Twine Optimizer dan backend IBM® pilihan Anda.

Untuk menjalankan fungsi tersebut, pilih perangkat backend yang sesuai; misalnya, ibm_phoenix.

Anda dapat menggunakan options untuk kontrol tambahan (opsional) atas pengiriman:

options = {
    "shots": 100000,
    "postprocessing_level": 1,
    "transpile_only": False,
    "job_tags": ["market_split"],
}

di mana shots adalah bilangan bulat yang menentukan jumlah eksekusi circuit, postprocessing_level menentukan apakah post-processing diterapkan pada hasil, transpile_only menentukan apakah masalah hanya ditranspilasi menjadi circuit (dan tidak diselesaikan), dan job_tags adalah label yang digunakan untuk mengidentifikasi job pada IBM Quantum® Platform.

Jalankan optimizer:

function_job = function.run(
    problem=json_ms_problem,
    variable_type="spin",
    backend_name="ibm_phoenix",
    options=options,
)
print(f"Job ID: {function_job.job_id}")

Periksa status job:

# Monitor the job status
function_job.status()

Ambil hasil:

# Retrieve the job result if the status is DONE
result = function_job.result()

result

Hasilnya berbentuk:

{
    'solution': {'0': 1, '1': -1, '10': 1, ... },
    'objective_value':  1.0,
    'solution_bitstring': '010000011101111011001001110010',
    'metadata': {
        'circuit_metrics': {
            'depth': 309,
            'gate_count': 3880,
            'two_qubit_gate_depth': 116,
            'two_qubit_gate_count': 899,
            'num_qubits': 30,
            'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},
        },
        'solver_info': {
            'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },
            'bitstring_distributions': {
                'before_postprocessing': {'011101110010110111001110011000': 1, ...},
                'after_postprocessing': {'011011110000110101001111011000': 1, ...}
            },
            'best_parameters': {
                'beta': [-0.18054534155552715],
                'gamma': [1.4141236348317905]
            }
        },
        'resource_usage': {
            'RUNNING: MAPPING': {'CPU_TIME': 172.936},
            'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},
            'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},
            'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},
            'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},
        },
    }
}

di mana dictionary solution berkorespondensi dengan qubit yang didefinisikan dalam masalah dan memberikan nilai spin yang dioptimalkan. metadata memberikan informasi tentang transpilasi (jumlah/kedalaman gate dua-qubit, gate yang digunakan, qubit aktif), dan berbagai runtime.

Dalam konteks masalah market split, bitstring solusi merepresentasikan vektor penugasan biner yang digunakan untuk membagi pasar menjadi dua wilayah terpisah. Nilai 1 menetapkan pasar tertentu ke Wilayah A sedangkan nilai 0 menetapkannya ke Wilayah B. Untuk solusi optimal, kombinasi tersebut menyeimbangkan pembagian, artinya kedua wilayah menerima tepat setengah dari total permintaan perusahaan untuk setiap produk.

Langkah selanjutnya

Rekomendasi

• Minta akses ke fungsi ini dengan mengisi formulir ini.
• Kunjungi referensi API untuk Qiskit Function ini.
• Baca panduannya.
• Coba tutorial untuk menerapkan Parity Twine Optimizer pada model Sherrington-Kirkpatrick.
• Tinjau preprint ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).