Selesaikan Masalah Pemisahan Pasaran dengan ParityQC Parity Twine Optimizer

Anggaran penggunaan: 10 saat pada pemproses Nighthawk r2. (NOTA: Ini hanyalah anggaran. Masa larian anda mungkin berbeza.)

Hasil Pembelajaran

• Dapatkan dan format masalah Market Split daripada QOBLIB - Quantum Optimization Benchmarking Library.

• Sediakan dan gunakan Parity Twine Optimizer untuk menyelesaikan satu instance Market Split.

• Pelajari cara memilih pilihan (options) untuk Parity Twine Optimizer dan hasil apa yang dikeluarkan.

Latar Belakang

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

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

Masalah Market Split

Masalah market split adalah masalah peruntukan sumber dunia sebenar yang NP-hard dan telah menjadi penanda aras bagi algoritma pengoptimuman kuantum. Ia mewakili cabaran logistik bertaruhan tinggi: bagaimana untuk membahagikan landskap kompleks pelanggan dan produk kepada wilayah yang boleh diurus dan seimbang.

Matlamatnya adalah untuk membahagikan $n$ pasaran kepada dua wilayah jualan yang seimbang sedemikian rupa sehingga setiap wilayah menerima tepat separuh daripada jumlah permintaan untuk $m$ produk. Penyelesaiannya ialah konfigurasi khusus yang mencapai taburan permintaan produk yang paling sekata yang mungkin, membolehkan sesebuah syarikat melaksanakan strategi logistik dan kakitangan di mana kedua-dua wilayah seimbang, meminimumkan risiko seperti kekurangan produk tempatan atau limpahan gudang.

Apabila bilangan pasaran dan produk meningkat, bilangan kemungkinan permutasi berkembang secara eksponen, menjadikannya sukar untuk mencari pembahagian terbaik menggunakan carian menyeluruh tradisional.

Perumusan Matematik

Katakan $A$ ialah matriks $m \times n$ yang mewakili permintaan produk merentasi pasaran, di mana $A_{ij}$ ialah permintaan untuk produk $i$ di pasaran $j$.

Vektor penugasan binari, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, ditakrifkan di mana:

• $x_j = 1$ menugaskan pasaran $j$ kepada Wilayah A.
• $x_j = 0$ menugaskan pasaran $j$ kepada Wilayah B.

Biar $d = [d_1, d_2, \dots, d_m]^T$ menjadi vektor jumlah permintaan untuk setiap produk, dikira sebagai $d = A \cdot \mathbf{1}$. Volum jualan sasaran bagi setiap wilayah untuk produk $i$ adalah tepat $\frac{d_i}{2}$.

Kekangan pengoptimuman atau kebolehlaksanaan memerlukan jumlah jualan yang diperuntukkan kepada Wilayah A sepadan sepenuhnya dengan separuh daripada jumlah permintaan untuk setiap produk:

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

Dalam praktiknya, oleh kerana pembahagian yang tepat jarang mungkin, masalah ini dirumuskan untuk meminimumkan kuasa dua pelanggaran kekangan (fungsi kos):

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

Mengembangkan ini memberikan bentuk yang setara dengan masalah pengoptimuman binari kuadratik tanpa kekangan (QUBO).

Setelah diselesaikan, vektor penyelesaian $x$ menentukan kepada wilayah mana pasaran tersebut ditugaskan. Ini adalah konfigurasi yang mencapai taburan permintaan produk yang paling seimbang yang mungkin.

Keperluan

Sebelum memulakan tutorial ini, pastikan yang berikut telah dipasang:

• 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 kebenaran untuk mengakses fungsi ParityQC Twine Optimizer. Untuk memohon akses, lengkapkan borang ini.

Persediaan

(Kod ini menganggap anda sudah menyimpan akaun anda ke persekitaran tempatan anda.)

Pertama, import semua pakej 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

Muatkan Parity Twine Optimizer daripada katalog Qiskit Functions:

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

Langkah 1: Takrifkan masalah sebagai fungsi objektif

Perolehi satu contoh masalah market split daripada QOBLIB - Quantum Optimization Benchmarking Library seperti berikut.

Fungsi load_market_split_problem mendapatkan semula masalah yang diberikan daripada QOBLIB dan menukarkannya kepada 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 mendapatkan semula dan memproses data masalah market split daripada 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 ditakrifkan, load_marketsplit_problem boleh digunakan untuk memuatkan contoh masalah tertentu daripada pustaka:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Langkah 2: Tukar kepada format JSON

Dalam langkah pertama, anda telah memperoleh bentuk QUBO masalah tersebut. Sekarang, tukarkannya kepada format JSON untuk fungsi pengoptimum:

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

Contoh QUBO bagi masalah Market Split kini ditukar kepada format JSON seperti berikut:

json_ms_problem = optimization_problem_to_json(ms_problem)

Langkah 3: Selesaikan masalah menggunakan Parity Twine Optimizer

Setelah anda memperoleh masalah market split dan menukarkannya kepada bentuk yang betul, anda boleh mencari penyelesaian dengan menggunakan Twine Optimizer dan backend IBM® pilihan.

Untuk menjalankan fungsi, pilih peranti backend yang sesuai; contohnya, ibm_phoenix.

Anda boleh menggunakan options untuk kawalan tambahan (pilihan) terhadap penghantaran:

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

dengan shots ialah integer yang menentukan bilangan pelaksanaan litar, postprocessing_level menentukan sama ada pasca-pemprosesan digunakan pada hasil, transpile_only menentukan sama ada masalah hanya ditranspilasi kepada litar (dan tidak diselesaikan), dan job_tags ialah label yang digunakan untuk mengenal pasti job pada IBM Quantum® Platform.

Jalankan pengoptimum:

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

Semak status job:

# Monitor the job status
function_job.status()

Dapatkan 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},
        },
    }
}

dengan kamus solution sepadan dengan qubit yang ditakrifkan dalam masalah dan memberikan nilai spin yang dioptimumkan bagi setiap satu. metadata memberikan maklumat tentang transpilasi (bilangan/kedalaman gate dua-qubit, gate yang digunakan, qubit aktif), dan pelbagai masa jalan.

Dalam konteks masalah market split, bitstring penyelesaian mewakili vektor penugasan binari yang digunakan untuk membahagikan pasaran kepada dua wilayah yang berasingan. Nilai 1 menugaskan pasaran tertentu itu kepada Wilayah A manakala nilai 0 menugaskannya kepada Wilayah B. Untuk penyelesaian optimum, gabungan tersebut mengimbangi pembahagian, bermakna kedua-dua wilayah menerima tepat separuh daripada jumlah permintaan syarikat bagi setiap produk.

Langkah seterusnya

Cadangan

• Minta akses kepada fungsi ini dengan melengkapkan borang ini.
• Lawati rujukan API untuk Qiskit Function ini.
• Baca panduan.
• Cuba tutorial untuk menggunakan Parity Twine Optimizer pada model Sherrington-Kirkpatrick.
• Semak prapencetakan ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).