Rozwiąż problem podziału rynku za pomocą ParityQC Parity Twine Optimizer

Szacowany czas wykonania: 10 sekund na procesorze Nighthawk r2. (UWAGA: to tylko szacunek. Rzeczywisty czas wykonania może się różnić.)

Efekty uczenia się

• Pobierz i sformatuj problem podziału rynku z QOBLIB - Quantum Optimization Benchmarking Library.

• Skonfiguruj i użyj Parity Twine Optimizer, aby rozwiązać instancję problemu podziału rynku.

• Dowiedz się, jak wybierać opcje dla Parity Twine Optimizer i jakie wyniki są zwracane.

Kontekst

Ten samouczek pokazuje, jak rozwiązać problem podziału rynku za pomocą ParityQC Parity Twine Optimizer.

Instancja problemu pochodzi z QOBLIB - Quantum Optimization Benchmarking Library.

Problem podziału rynku

Problem podziału rynku jest rzeczywistym, NP-trudnym problemem alokacji zasobów, który stał się benchmarkiem dla algorytmów optymalizacji kwantowej. Stanowi on trudne logistycznie wyzwanie o wysokiej stawce: jak podzielić złożony krajobraz klientów i produktów na łatwe w zarządzaniu, wyrównane terytoria.

Celem jest podzielenie $n$ rynków na dwa zrównoważone regiony sprzedaży w taki sposób, aby każdy region otrzymał dokładnie połowę całkowitego popytu na $m$ produktów. Rozwiązaniem jest konkretna konfiguracja, która osiąga możliwie najbardziej równomierny rozkład popytu na produkty, umożliwiając firmie wdrożenie strategii logistycznej i kadrowej, w której oba regiony są zrównoważone, minimalizując ryzyka, takie jak lokalne niedobory produktów lub przepełnienie magazynów.

Wraz ze wzrostem liczby rynków i produktów liczba możliwych permutacji rośnie wykładniczo, co utrudnia znalezienie najlepszego podziału za pomocą tradycyjnego przeglądu zupełnego.

Sformułowanie matematyczne

Niech $A$ będzie macierzą $m \times n$ reprezentującą popyt na produkty w poszczególnych rynkach, gdzie $A_{ij}$ to popyt na produkt $i$ na rynku $j$.

Definiuje się binarny wektor przypisania, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, gdzie:

• $x_j = 1$ przypisuje rynek $j$ do Regionu A.
• $x_j = 0$ przypisuje rynek $j$ do Regionu B.

Niech $d = [d_1, d_2, \dots, d_m]^T$ będzie wektorem całkowitego popytu dla każdego produktu, obliczonym jako $d = A \cdot \mathbf{1}$. Docelowy wolumen sprzedaży na region dla produktu $i$ wynosi dokładnie $\frac{d_i}{2}$.

Ograniczenie optymalizacyjne lub warunek wykonalności wymaga, aby całkowita sprzedaż przypisana do Regionu A dokładnie odpowiadała połowie całkowitego popytu na każdy produkt:

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

W praktyce, ponieważ dokładny podział jest rzadko możliwy, problem jest formułowany tak, aby zminimalizować kwadrat naruszenia ograniczenia (funkcję kosztu):

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

Rozwinięcie tego wyrażenia daje formę równoważną problemowi kwadratowej nieograniczonej optymalizacji binarnej (QUBO).

Po rozwiązaniu, wektor rozwiązania $x$ określa, do którego regionu przypisany jest dany rynek. Jest to konfiguracja, która osiąga możliwie najbardziej zrównoważony rozkład popytu na produkty.

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że zainstalowane są następujące elementy:

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

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

Potrzebujesz również uprawnień dostępu do funkcji ParityQC Twine Optimizer. Aby poprosić o dostęp, wypełnij ten formularz.

Konfiguracja

(Ten kod zakłada, że zapisałeś już swoje konto w swoim lokalnym środowisku.)

Najpierw zaimportuj wszystkie pakiety wymagane w tym samouczku.

# 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

Załaduj Parity Twine Optimizer z katalogu Qiskit Functions:

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

Krok 1: Zdefiniuj problem jako funkcję celu

Uzyskaj instancję problemu podziału rynku z QOBLIB - Quantum Optimization Benchmarking Library w następujący sposób.

Funkcja load_market_split_problem pobiera dany problem z QOBLIB i konwertuje go na 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)

Funkcja load_market_split_problem wymaga następujących funkcji parsujących do pobrania i przetworzenia danych problemu market split 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 zdefiniowaniu, load_marketsplit_problem może być użyta do wczytania konkretnej instancji problemu z biblioteki:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Krok 2: Konwertuj do formatu JSON

W pierwszym kroku uzyskałeś formę QUBO problemu. Teraz przekonwertuj ją do formatu JSON dla funkcji optymalizatora:

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

Instancja QUBO problemu Market Split jest teraz przekonwertowana do formatu JSON jako:

json_ms_problem = optimization_problem_to_json(ms_problem)

Krok 3: Rozwiąż problem za pomocą Parity Twine Optimizer

Teraz, gdy uzyskałeś problem market split i przekonwertowałeś go na poprawną formę, możesz znaleźć rozwiązanie, używając Twine Optimizer i wybranego backendu IBM®.

Aby uruchomić funkcję, wybierz odpowiedni backend (urządzenie kwantowe); na przykład ibm_phoenix.

Możesz użyć options, aby (opcjonalnie) uzyskać dodatkową kontrolę nad przesyłaniem zadania:

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

gdzie shots to liczba całkowita określająca liczbę wykonań obwodu, postprocessing_level określa, czy do wyniku zastosowane jest post-processing, transpile_only określa, czy problem jest jedynie transpilowany do obwodu (a nie rozwiązywany), a job_tags to etykieta używana do identyfikacji zadania na platformie IBM Quantum®.

Uruchom optymalizator:

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

Sprawdź status zadania:

# Monitor the job status
function_job.status()

Pobierz wyniki:

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

result

Wynik ma postać:

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

gdzie słownik solution odpowiada kubitom zdefiniowanym w problemie i podaje ich zoptymalizowane wartości spinów. metadata podaje informacje o transpilacji (liczba/głębokość bramek dwukubitowych, użyte bramki, aktywne kubity) oraz różne czasy wykonania.

W kontekście problemu market split, ciąg bitów rozwiązania reprezentuje binarny wektor przypisania używany do podziału rynków na dwa oddzielne regiony. Wartość 1 przypisuje dany rynek do Regionu A, natomiast wartość 0 przypisuje go do Regionu B. W optymalnym rozwiązaniu kombinacja równoważy podział, co oznacza, że oba regiony otrzymują dokładnie połowę całkowitego popytu firmy na każdy produkt.

Kolejne kroki

Zalecenia

• Poproś o dostęp do funkcji, wypełniając ten formularz.
• Odwiedź dokumentację API dla tej Qiskit Function.
• Przeczytaj przewodnik.
• Wypróbuj samouczek dotyczący zastosowania Parity Twine Optimizer do modelu Sherringtona-Kirkpatricka.
• Zapoznaj się z preprintem ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).