Vyřeš problém market split pomocí ParityQC Parity Twine Optimizer

Odhadovaná doba běhu: 10 sekund na procesoru Nighthawk r2. (POZNÁMKA: Toto je pouze odhad. Skutečná doba běhu se může lišit.)

Co se naučíš

Získej a naformátuj problém Market Split z QOBLIB - Quantum Optimization Benchmarking Library.
Nastav a použij Parity Twine Optimizer k vyřešení instance Market Split.
Nauč se, jak vybrat možnosti pro Parity Twine Optimizer a jaké výsledky jsou na výstupu.

Kontext

Tento tutoriál ukazuje, jak vyřešit problém Market Split pomocí ParityQC Parity Twine Optimizer.

Instance problému je získána z QOBLIB - Quantum Optimization Benchmarking Library.

Problém market split

Problém rozdělení trhu (market split) je reálný, NP-těžký problém alokace zdrojů, který se stal benchmarkem pro kvantové optimalizační algoritmy. Představuje logistickou výzvu, u níž je hodně v sázce: jak rozdělit složitou strukturu zákazníků a produktů na zvládnutelná, vyvážená území.

Cílem je rozdělit $n$ trhů do dvou vyvážených prodejních regionů tak, aby každý region obdržel přesně polovinu celkové poptávky po $m$ produktech. Řešením je konkrétní konfigurace, která dosahuje co nejrovnoměrnějšího rozdělení poptávky po produktech, což firmě umožňuje zavést logistickou a personální strategii, ve které jsou oba regiony vyvážené, a minimalizovat rizika, jako je lokální nedostatek produktů nebo přeplnění skladů.

S rostoucím počtem trhů a produktů roste počet možných permutací exponenciálně, což ztěžuje nalezení nejlepšího rozdělení pomocí tradičního vyčerpávajícího prohledávání.

Matematická formulace

Nechť $A$ je matice $m \times n$ reprezentující poptávku po produktech napříč trhy, kde $A_{ij}$ je poptávka po produktu $i$ na trhu $j$ .

Je definován binární přiřazovací vektor $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ , kde:

$x_j = 1$ přiřazuje trh $j$ do regionu A.
$x_j = 0$ přiřazuje trh $j$ do regionu B.

Nechť $d = [d_1, d_2, \dots, d_m]^T$ je vektor celkové poptávky pro každý produkt, vypočtený jako $d = A \cdot \mathbf{1}$ . Cílový objem prodeje na region pro produkt $i$ je přesně $\frac{d_i}{2}$ .

Optimalizační nebo proveditelnostní omezení vyžaduje, aby celkové prodeje přiřazené regionu A přesně odpovídaly polovině celkové poptávky pro každý produkt:

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

V praxi, protože přesné rozdělení je zřídka možné, je problém formulován tak, aby minimalizoval kvadratické porušení omezení (nákladovou funkci):

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

Rozepsáním tohoto výrazu získáme tvar, který je ekvivalentní problému kvadratické neomezené binární optimalizace (QUBO).

Po vyřešení určuje řešící vektor $x$ , do kterého regionu je trh přiřazen. Jedná se o konfiguraci, která dosahuje co nejvyváženějšího rozdělení poptávky po produktech.

Požadavky

Než začneš s tímto tutoriálem, ujisti se, že máš nainstalováno následující:

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

Kromě toho potřebuješ oprávnění pro přístup k funkci ParityQC Twine Optimizer. Pro požádání o přístup vyplň tento formulář.

Nastavení

(Tento kód předpokládá, že jste si již uložili svůj účet do svého lokálního prostředí.)

Nejprve naimportuj všechny balíčky potřebné pro tento tutoriál.

# 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

Načtěte Parity Twine Optimizer z katalogu Qiskit Functions:

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

Krok 1: Definování problému jako účelové funkce

Získej instanci problému rozdělení trhu (market split) z QOBLIB - Quantum Optimization Benchmarking Library následujícím způsobem.

Funkce load_market_split_problem načte daný problém z QOBLIB a převede ho na problém 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)

Funkce load_market_split_problem vyžaduje následující parserové funkce k načtení a zpracování dat problému rozdělení trhu z 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)

Po definování lze funkci load_marketsplit_problem použít k načtení konkrétní instance problému z knihovny:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Krok 2: Převod do formátu JSON

V prvním kroku jsi získal formu QUBO problému. Nyní ji převeď do formátu JSON pro optimalizační funkci:

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 problému rozdělení trhu je nyní převedena do formátu JSON takto:

json_ms_problem = optimization_problem_to_json(ms_problem)

Krok 3: Řešení problému pomocí Parity Twine Optimizeru

Nyní, když jste získali problém rozdělení trhu a převedli ho do správné formy, můžete najít řešení pomocí Twine Optimizeru a zvoleného backendu IBM®.

Chceš-li funkci spustit, zvol vhodné backendové zařízení, například ibm_phoenix.

Pro (volitelnou) další kontrolu nad odesláním můžete použít options:

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

kde shots je celé číslo, které určuje počet spuštění obvodu, postprocessing_level určuje, zda se na výsledek použije následné zpracování, transpile_only určuje, zda je problém pouze transpilován do obvodu (a nikoli vyřešen), a job_tags je štítek použitý k identifikaci úlohy na platformě IBM Quantum®.

Spusťte 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}")

Zkontrolujte stav úlohy:

# Monitor the job status
function_job.status()

Načtěte výsledky:

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

result

Výsledek má tvar:

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

kde slovník solution odpovídá qubitům definovaným v problému a udává jejich optimalizované hodnoty spinu. metadata poskytuje informace o transpilaci (počty/hloubka dvouqubitových hradel, použitá hradla, aktivní qubity) a různé časy běhu.

V kontextu problému rozdělení trhu představuje výsledný bitový řetězec binární vektor přiřazení použitý k rozdělení trhů do dvou samostatných regionů. Hodnota 1 přiřazuje daný trh do regionu A, zatímco hodnota 0 ho přiřazuje do regionu B. U optimálního řešení kombinace vyvažuje rozdělení, což znamená, že oba regiony dostanou přesně polovinu celkové poptávky firmy po každém produktu.

Další kroky

Doporučení

Požádejte o přístup k funkci vyplněním tohoto formuláře.
Navštivte referenční dokumentaci API pro tuto funkci Qiskit.
Přečtěte si průvodce.
Vyzkoušejte tutoriál pro použití Parity Twine Optimizeru na model Sherrington-Kirkpatrick.
Přečtěte si preprint Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025) na ArXiv.

Co se naučíš​

Kontext​

Problém market split​

Matematická formulace​

Požadavky​

Nastavení​

Krok 1: Definování problému jako účelové funkce​

Krok 2: Převod do formátu JSON​

Krok 3: Řešení problému pomocí Parity Twine Optimizeru​

Další kroky​