Löse das Market-Split-Problem mit dem ParityQC Parity Twine Optimizer

Geschätzte Nutzungsdauer: 10 Sekunden auf einem Nighthawk-r2-Prozessor. (HINWEIS: Dies ist nur eine Schätzung. Deine tatsächliche Laufzeit kann abweichen.)

Lernziele

• Beziehe das Market-Split-Problem aus der QOBLIB - Quantum Optimization Benchmarking Library und bereite es auf.

• Richte den Parity Twine Optimizer ein und verwende ihn, um eine Market-Split-Instanz zu lösen.

• Lerne, wie du Optionen für den Parity Twine Optimizer auswählst und welche Ergebnisse ausgegeben werden.

Hintergrund

Dieses Tutorial zeigt, wie du das Market-Split-Problem mit dem ParityQC Parity Twine Optimizer löst.

Die Probleminstanz stammt aus der QOBLIB - Quantum Optimization Benchmarking Library.

Market-Split-Problem

Das Market-Split-Problem ist ein reales, NP-schweres Ressourcenzuteilungsproblem und hat sich zu einem Benchmark für Quantenoptimierungsalgorithmen entwickelt. Es stellt eine anspruchsvolle logistische Herausforderung dar: wie man eine komplexe Landschaft aus Kunden und Produkten in überschaubare, ausgeglichene Gebiete aufteilt.

Das Ziel besteht darin, $n$ Märkte in zwei ausgeglichene Absatzregionen aufzuteilen, sodass jede Region genau die Hälfte der Gesamtnachfrage für $m$ Produkte erhält. Die Lösung ist die spezifische Konfiguration, die die bestmögliche gleichmäßige Verteilung der Produktnachfrage erreicht, sodass ein Unternehmen eine Logistik- und Personalstrategie umsetzen kann, bei der beide Regionen ausgeglichen sind, wodurch Risiken wie lokale Produktengpässe oder überfüllte Lager minimiert werden.

Mit zunehmender Anzahl von Märkten und Produkten wächst die Anzahl der möglichen Permutationen exponentiell, was es schwierig macht, die beste Aufteilung mit klassischer vollständiger Suche (Brute Force) zu finden.

Mathematische Formulierung

Sei $A$ eine $m \times n$-Matrix, die die Nachfrage nach Produkten über die Märkte hinweg darstellt, wobei $A_{ij}$ die Nachfrage nach Produkt $i$ in Markt $j$ ist.

Ein binärer Zuweisungsvektor $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ wird definiert, wobei gilt:

• $x_j = 1$ weist Markt $j$ der Region A zu.
• $x_j = 0$ weist Markt $j$ der Region B zu.

Sei $d = [d_1, d_2, \dots, d_m]^T$ der Gesamtnachfragevektor für jedes Produkt, berechnet als $d = A \cdot \mathbf{1}$. Das Zielabsatzvolumen pro Region für Produkt $i$ beträgt genau $\frac{d_i}{2}$.

Die Optimierungs- bzw. Zulässigkeitsbedingung verlangt, dass die Region A zugewiesenen Gesamtverkäufe für jedes Produkt genau der Hälfte der Gesamtnachfrage entsprechen:

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

Da eine exakte Aufteilung in der Praxis selten möglich ist, wird das Problem so formuliert, dass die quadrierte Verletzung der Nebenbedingung (die Kostenfunktion) minimiert wird:

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

Das Ausmultiplizieren ergibt eine Form, die einem quadratischen uneingeschränkten binären Optimierungsproblem (QUBO) entspricht.

Nach dem Lösen bestimmt der Lösungsvektor $x$, welcher Region der Markt zugewiesen wird. Dies ist die Konfiguration, die die bestmögliche ausgeglichene Verteilung der Produktnachfrage erreicht.

Voraussetzungen

Stelle vor Beginn dieses Tutorials sicher, dass Folgendes installiert ist:

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

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

Außerdem benötigst du eine Berechtigung für den Zugriff auf die ParityQC-Twine-Optimizer-Function. Um Zugriff zu beantragen, fülle dieses Formular aus.

Setup

(Dieser Code setzt voraus, dass du dein Konto bereits gespeichert hast.)

Importiere zunächst alle erforderlichen Pakete für dieses 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

Lade den Parity Twine Optimizer aus dem Qiskit Functions-Katalog:

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

Schritt 1: Das Problem als Zielfunktion definieren

Rufe wie folgt eine Market-Split-Probleminstanz aus der QOBLIB - Quantum Optimization Benchmarking Library ab.

Die Funktion load_market_split_problem ruft ein gegebenes Problem aus QOBLIB ab und wandelt es in ein QUBO-Problem um.

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)

Die Funktion load_market_split_problem benötigt die folgenden Parser-Funktionen, um die Market-Split-Problemdaten aus QOBLIB abzurufen und zu verarbeiten.

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)

Sobald definiert, kann load_marketsplit_problem verwendet werden, um eine bestimmte Probleminstanz aus der Bibliothek zu laden:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Schritt 2: In das JSON-Format umwandeln

Im ersten Schritt hast du die QUBO-Form des Problems erhalten. Wandle es nun für die Optimizer-Funktion in das JSON-Format um:

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

Die QUBO-Instanz des Market-Split-Problems wird nun wie folgt in das JSON-Format umgewandelt:

json_ms_problem = optimization_problem_to_json(ms_problem)

Schritt 3: Das Problem mit dem Parity Twine Optimizer lösen

Nachdem du das Market-Split-Problem erhalten und in die richtige Form umgewandelt hast, kannst du mit dem Twine Optimizer und einem ausgewählten IBM®-Backend eine Lösung finden.

Um die Funktion auszuführen, wähle ein geeignetes Backend-Gerät aus, zum Beispiel ibm_phoenix.

Du kannst options für (optionale) zusätzliche Kontrolle über die Übermittlung verwenden:

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

wobei shots eine Ganzzahl ist, die die Anzahl der Schaltkreisausführungen angibt, postprocessing_level bestimmt, ob eine Nachbearbeitung auf das Ergebnis angewendet wird, transpile_only gibt an, ob das Problem nur in einen Schaltkreis transpiliert (und nicht gelöst) wird, und job_tags ist die Bezeichnung, mit der der Job auf der IBM Quantum® Platform identifiziert wird.

Führe den Optimizer aus:

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

Überprüfe den Job-Status:

# Monitor the job status
function_job.status()

Rufe die Ergebnisse ab:

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

result

Das Ergebnis hat die Form:

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

wobei das solution-Dictionary den im Problem definierten Qubits entspricht und deren optimierte Spin-Werte angibt. metadata liefert Informationen zur Transpilation (Anzahl/Tiefe der Zwei-Qubit-Gates, verwendete Gates, aktive Qubits) und verschiedene Laufzeiten.

Im Kontext des Market-Split-Problems stellt der Lösungs-Bitstring einen binären Zuweisungsvektor dar, der verwendet wird, um Märkte in zwei separate Regionen aufzuteilen. Ein Wert von 1 weist den betreffenden Markt Region A zu, während ein Wert von 0 ihn Region B zuweist. Bei der optimalen Lösung gleicht die Kombination die Aufteilung aus, das heißt, beide Regionen erhalten genau die Hälfte der gesamten Nachfrage des Unternehmens für jedes Produkt.

Nächste Schritte

Empfehlungen

• Fordere Zugriff auf die Funktion an, indem du dieses Formular ausfüllst.
• Besuche die API-Referenz für diese Qiskit-Funktion.
• Lies den Leitfaden.
• Probiere das Tutorial aus, um den Parity Twine Optimizer auf das Sherrington-Kirkpatrick-Modell anzuwenden.
• Sieh dir den ArXiv-Preprint Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025) an.