Lutasin ang market split problem gamit ang ParityQC Parity Twine Optimizer

Tinatayang paggamit: 10 segundo sa isang Nighthawk r2 processor. (TANDAAN: Isa lamang itong pagtatantya. Maaaring mag-iba ang iyong runtime.)

Mga Matututunan

Kunin at i-format ang Market Split problem mula sa QOBLIB - Quantum Optimization Benchmarking Library.
I-setup at gamitin ang Parity Twine Optimizer para lutasin ang isang Market Split instance.
Alamin kung paano pumili ng options para sa Parity Twine Optimizer at kung anong mga resulta ang output.

Kaligiran

Ipinapakita ng tutorial na ito kung paano lutasin ang Market Split problem gamit ang ParityQC Parity Twine Optimizer.

Ang problem instance ay kinuha mula sa QOBLIB - Quantum Optimization Benchmarking Library.

Ang market split problem

Ang market split problem ay isang real-world, NP-hard na resource allocation problem at naging benchmark para sa mga quantum optimization algorithm. Kumakatawan ito sa isang mabigat at kritikal na hamon sa logistics: kung paano hatiin ang isang komplikadong landscape ng mga customer at produkto tungo sa manageable at equalized na mga teritoryo.

Ang layunin ay hatiin ang $n$ na markets sa dalawang balanced na sales regions kung saan ang bawat rehiyon ay tumatanggap ng eksaktong kalahati ng total demand para sa $m$ na produkto. Ang solusyon ay ang partikular na configuration na nakakamit ng pinaka-even na distribution ng product demand na posible, na nagpapahintulot sa isang kompanya na magpatupad ng logistics at staffing strategy kung saan pantay ang parehong rehiyon, na binabawasan ang mga panganib tulad ng localized na product shortages o warehouse overflows.

Habang tumataas ang bilang ng markets at produkto, exponentially rin tumataas ang bilang ng posibleng permutations, kaya mahirap hanapin ang pinakamahusay na split gamit ang tradisyonal na exhaustive search.

Mathematical na formulation

Ipagpalagay na ang $A$ ay isang $m \times n$ matrix na kumakatawan sa demand ng mga produkto sa iba't ibang markets, kung saan ang $A_{ij}$ ay ang demand para sa produkto $i$ sa market $j$ .

Isang binary assignment vector, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ , ay tinutukoy kung saan:

Itinatalaga ng $x_j = 1$ ang market $j$ sa Rehiyon A.
Itinatalaga ng $x_j = 0$ ang market $j$ sa Rehiyon B.

Ipagpalagay na ang $d = [d_1, d_2, \dots, d_m]^T$ ay ang total demand vector para sa bawat produkto, kinakalkula bilang $d = A \cdot \mathbf{1}$ . Ang target sales volume kada rehiyon para sa produkto $i$ ay eksaktong $\frac{d_i}{2}$ .

Hinihingi ng optimization o feasibility constraint na eksaktong tumugma ang total sales na inilaan sa Rehiyon A sa kalahati ng total demand para sa bawat produkto:

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

Sa praktika, dahil bihirang posible ang eksaktong division, binubuo ang problema para i-minimize ang squared constraint violation (ang cost function):

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

Kapag pinalawak ito, nagbibigay ito ng anyo na katumbas ng quadratic unconstrained binary optimization (QUBO) problem.

Pagkatapos malutas, itinatakda ng solution vector $x$ kung saang rehiyon itinalaga ang market. Ito ang configuration na nakakamit ng pinaka-balanced na distribution ng product demand na posible.

Mga Kailangan

Bago simulan ang tutorial na ito, siguraduhing naka-install ang mga sumusunod:

Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)
Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)
NumPy (pip install numpy)

Kailangan mo rin ng pahintulot para ma-access ang ParityQC Twine Optimizer function. Para humiling ng access, kumpletuhin ang form na ito.

Pag-setup

(Ipinapalagay ng code na ito na na-save mo na ang iyong account sa iyong local environment.)

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

# 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

I-load ang Parity Twine Optimizer mula sa Qiskit Functions catalog:

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

Hakbang 1: Tukuyin ang problema bilang isang objective function

Kumuha ng market split problem instance mula sa QOBLIB - Quantum Optimization Benchmarking Library gaya ng sumusunod.

Ang function na load_market_split_problem ay kumukuha ng ibinigay na problema mula sa QOBLIB at kino-convert ito sa isang QUBO problem.

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)

Kailangan ng function na load_market_split_problem ng mga sumusunod na parser function upang kunin at iproseso ang data ng market split problem mula sa 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)

Kapag natukoy na, magagamit ang load_marketsplit_problem upang i-load ang isang partikular na problem instance mula sa library:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Hakbang 2: I-convert sa JSON format

Sa unang hakbang, nakuha mo ang QUBO form ng problema. Ngayon, i-convert ito sa JSON format para sa optimizer function:

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

Ang QUBO instance ng Market Split problem ay na-convert na ngayon sa JSON format bilang:

json_ms_problem = optimization_problem_to_json(ms_problem)

Hakbang 3: Lutasin ang problema gamit ang Parity Twine Optimizer

Ngayong nakuha mo na ang market split problem at na-convert ito sa tamang form, mahahanap mo na ang solusyon gamit ang Twine Optimizer at isang piniling IBM® backend.

Upang patakbuhin ang function, pumili ng angkop na backend device; halimbawa, ibm_phoenix.

Maaari mong gamitin ang options para sa (opsyonal) karagdagang kontrol sa submission:

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

kung saan ang shots ay isang integer na tumutukoy sa bilang ng circuit executions, ang postprocessing_level ay nagpapasiya kung ilalapat ang post-processing sa resulta, ang transpile_only ay tumutukoy kung ang problema ay tine-transpile lamang sa isang circuit (at hindi nalulutas), at ang job_tags ay ang label na ginagamit upang tukuyin ang job sa IBM Quantum® Platform.

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

Suriin ang status ng job:

# Monitor the job status
function_job.status()

Kunin ang mga resulta:

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

result

Ang resulta ay nasa form na:

{
    '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},
        },
    }
}

kung saan ang solution dictionary ay tumutugma sa mga qubit na tinukoy sa problema at nagbibigay ng kanilang na-optimize na spin values. Ang metadata ay nagbibigay ng impormasyon tungkol sa transpilation (two-qubit gates counts/depth, mga gate na ginamit, aktibong qubits), at iba't ibang runtimes.

Sa konteksto ng market split problem, ang solution bitstring ay kumakatawan sa isang binary assignment vector na ginagamit upang hatiin ang mga market sa dalawang magkahiwalay na rehiyon. Itinatalaga ng halagang 1 ang spesipikong market na iyon sa Rehiyon A samantalang itinatalaga naman ng halagang 0 ito sa Rehiyon B. Para sa optimal na solusyon, ang kombinasyon ay nagbabalanse sa split, na nangangahulugang parehong rehiyon ay tumatanggap nang eksaktong kalahati ng kabuuang demand ng kumpanya para sa bawat produkto.

Mga susunod na hakbang

Mga Rekomendasyon

Humiling ng access sa function sa pamamagitan ng pagkumpleto ng form na ito.
Bisitahin ang API reference para sa Qiskit Function na ito.
Basahin ang guide.
Subukan ang tutorial para sa paglalapat ng Parity Twine Optimizer sa Sherrington-Kirkpatrick model.
Suriin ang Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025) ArXiv preprint.

Mga Matututunan​

Kaligiran​

Ang market split problem​

Mathematical na formulation​

Mga Kailangan​

Pag-setup​

Hakbang 1: Tukuyin ang problema bilang isang objective function​

Hakbang 2: I-convert sa JSON format​

Hakbang 3: Lutasin ang problema gamit ang Parity Twine Optimizer​

Mga susunod na hakbang​