Rezolvă problema market split cu ParityQC Parity Twine Optimizer

Estimare de utilizare: 10 secunde pe un procesor Nighthawk r2. (NOTĂ: Aceasta este doar o estimare. Timpul tău de execuție poate varia.)

Rezultate ale învățării

• Obține și formatează problema Market Split din QOBLIB - Quantum Optimization Benchmarking Library.

• Configurează și folosește Parity Twine Optimizer pentru a rezolva o instanță Market Split.

• Învață cum să alegi opțiuni pentru Parity Twine Optimizer și ce rezultate sunt generate.

Context

Acest tutorial demonstrează cum să rezolvi problema Market Split folosind ParityQC Parity Twine Optimizer.

Instanța problemei este obținută din QOBLIB - Quantum Optimization Benchmarking Library.

Problema market split

Problema market split este o problemă reală, NP-hard, de alocare a resurselor și a devenit un benchmark pentru algoritmii de optimizare cuantică. Ea reprezintă o provocare logistică cu miză mare: cum să împarți un peisaj complex de clienți și produse în teritorii gestionabile și echilibrate.

Scopul este de a împărți $n$ piețe în două regiuni de vânzări echilibrate, astfel încât fiecare regiune să primească exact jumătate din cererea totală pentru $m$ produse. Soluția este configurația specifică care realizează cea mai uniformă distribuție posibilă a cererii de produse, permițând unei companii să implementeze o strategie logistică și de personal în care ambele regiuni sunt echilibrate, minimizând riscurile precum lipsurile localizate de produse sau supraîncărcarea depozitelor.

Pe măsură ce numărul de piețe și produse crește, numărul de permutări posibile crește exponențial, ceea ce face dificilă găsirea celei mai bune împărțiri folosind căutări exhaustive tradiționale.

Formulare matematică

Fie $A$ o matrice $m \times n$ care reprezintă cererea de produse pe piețe, unde $A_{ij}$ este cererea pentru produsul $i$ pe piața $j$.

Se definește un vector binar de atribuire, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, unde:

• $x_j = 1$ atribuie piața $j$ Regiunii A.
• $x_j = 0$ atribuie piața $j$ Regiunii B.

Fie $d = [d_1, d_2, \dots, d_m]^T$ vectorul cererii totale pentru fiecare produs, calculat ca $d = A \cdot \mathbf{1}$. Volumul țintă de vânzări pe regiune pentru produsul $i$ este exact $\frac{d_i}{2}$.

Restricția de optimizare sau de fezabilitate cere ca vânzările totale alocate Regiunii A să corespundă perfect jumătății din cererea totală pentru fiecare produs:

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

În practică, deoarece o împărțire exactă este rareori posibilă, problema este formulată pentru a minimiza violarea la pătrat a restricției (funcția de cost):

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

Dezvoltând această expresie obținem o formă echivalentă cu o problemă de optimizare binară pătratică fără restricții (QUBO).

După rezolvare, vectorul soluție $x$ dictează cărei regiuni îi este atribuită piața. Aceasta este configurația care realizează cea mai echilibrată distribuție posibilă a cererii de produse.

Cerințe

Înainte de a începe acest tutorial, asigură-te că următoarele sunt instalate:

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

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

De asemenea, ai nevoie de permisiune pentru a accesa funcția ParityQC Twine Optimizer. Pentru a solicita acces, completează acest formular.

Configurare

(Acest cod presupune că ți-ai salvat deja contul în mediul local.)

Mai întâi, importă toate pachetele necesare pentru acest tutorial.

# 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

Încarcă Parity Twine Optimizer din catalogul Qiskit Functions:

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

Pasul 1: Definește problema ca o funcție obiectiv

Obține o instanță a problemei market split din QOBLIB - Quantum Optimization Benchmarking Library astfel.

Funcția load_market_split_problem preia o problemă dată din QOBLIB și o convertește într-o problemă 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)

Funcția load_market_split_problem necesită următoarele funcții parser pentru a prelua și procesa datele problemei market split din 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)

Odată definită, load_marketsplit_problem poate fi folosită pentru a încărca o instanță specifică a problemei din bibliotecă:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Pasul 2: Convertește în format JSON

În primul pas, ai obținut forma QUBO a problemei. Acum, convertește-o în format JSON pentru funcția optimizatorului:

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

Instanța QUBO a problemei Market Split este acum convertită în format JSON astfel:

json_ms_problem = optimization_problem_to_json(ms_problem)

Pasul 3: Rezolvă problema folosind Parity Twine Optimizer

Acum că ai obținut problema market split și ai convertit-o în forma corectă, poți găsi o soluție folosind Twine Optimizer și un backend IBM® ales.

Pentru a rula funcția, alege un dispozitiv backend potrivit; de exemplu, ibm_phoenix.

Poți folosi options pentru un control suplimentar (opțional) asupra trimiterii:

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

unde shots este un număr întreg care specifică numărul de execuții ale circuitului, postprocessing_level determină dacă se aplică post-procesare rezultatului, transpile_only specifică dacă problema este doar transpilată într-un circuit (și nu rezolvată), iar job_tags este eticheta folosită pentru a identifica job-ul pe platforma IBM Quantum®.

Rulează optimizatorul:

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

Verifică starea job-ului:

# Monitor the job status
function_job.status()

Preia rezultatele:

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

result

Rezultatul are forma:

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

unde dicționarul solution corespunde qubiților definiți în problemă și oferă valorile lor de spin optimizate. metadata oferă informații despre transpilare (numărul/adâncimea porților cu doi qubiți, porțile folosite, qubiții activi) și diverși timpi de execuție.

În contextul problemei market split, șirul de biți al soluției reprezintă un vector de atribuire binară folosit pentru a împărți piețele în două regiuni separate. O valoare de 1 atribuie acea piață specifică Regiunii A, în timp ce o valoare de 0 o atribuie Regiunii B. Pentru soluția optimă, combinația echilibrează împărțirea, ceea ce înseamnă că ambele regiuni primesc exact jumătate din cererea totală a companiei pentru fiecare produs.

Pașii următori

Recomandări

• Solicită acces la funcție completând acest formular.
• Vizitează referința API pentru această funcție Qiskit.
• Citește ghidul.
• Încearcă tutorialul pentru aplicarea Parity Twine Optimizer la modelul Sherrington-Kirkpatrick.
• Consultă preprintul ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).