Risolvi il problema del market split con il ParityQC Parity Twine Optimizer

Stima di utilizzo: 10 secondi su un processore Nighthawk r2. (NOTA: questa è solo una stima. Il tuo runtime potrebbe variare.)

Risultati di apprendimento

• Ottenere e formattare il problema del Market Split dalla QOBLIB - Quantum Optimization Benchmarking Library.

• Configurare e usare il Parity Twine Optimizer per risolvere un'istanza di Market Split.

• Imparare come scegliere le opzioni per il Parity Twine Optimizer e quali risultati vengono restituiti.

Contesto

Questo tutorial mostra come risolvere il problema del Market Split usando il ParityQC Parity Twine Optimizer.

L'istanza del problema viene ottenuta dalla QOBLIB - Quantum Optimization Benchmarking Library.

Problema del market split

Il problema del market split è un problema di allocazione delle risorse reale e NP-hard, ed è diventato un benchmark per gli algoritmi di ottimizzazione quantistica. Rappresenta una sfida logistica ad alto rischio: come suddividere un panorama complesso di clienti e prodotti in territori gestibili ed equilibrati.

L'obiettivo è dividere $n$ mercati in due regioni di vendita bilanciate in modo che ciascuna regione riceva esattamente metà della domanda totale per $m$ prodotti. La soluzione è la configurazione specifica che raggiunge la distribuzione più equa possibile della domanda di prodotto, permettendo a un'azienda di implementare una strategia di logistica e personale in cui entrambe le regioni sono bilanciate, minimizzando i rischi come carenze localizzate di prodotto o sovraccarichi dei magazzini.

Man mano che il numero di mercati e prodotti aumenta, il numero di possibili permutazioni cresce esponenzialmente, rendendo difficile trovare la suddivisione migliore usando ricerche esaustive tradizionali.

Formulazione matematica

Sia $A$ una matrice $m \times n$ che rappresenta la domanda di prodotti nei vari mercati, dove $A_{ij}$ è la domanda per il prodotto $i$ nel mercato $j$.

Un vettore di assegnazione binario, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, è definito dove:

• $x_j = 1$ assegna il mercato $j$ alla Regione A.
• $x_j = 0$ assegna il mercato $j$ alla Regione B.

Sia $d = [d_1, d_2, \dots, d_m]^T$ il vettore della domanda totale per ogni prodotto, calcolato come $d = A \cdot \mathbf{1}$. Il volume di vendita target per regione per il prodotto $i$ è esattamente $\frac{d_i}{2}$.

Il vincolo di ottimizzazione o di fattibilità richiede che le vendite totali allocate alla Regione A corrispondano perfettamente a metà della domanda totale per ogni prodotto:

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

In pratica, poiché una divisione esatta è raramente possibile, il problema viene formulato per minimizzare la violazione quadratica del vincolo (la funzione di costo):

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

Espandendo questa espressione si ottiene una forma equivalente a un problema di ottimizzazione quadratica binaria non vincolata (QUBO).

Una volta risolto, il vettore soluzione $x$ determina a quale regione viene assegnato il mercato. Questa è la configurazione che raggiunge la distribuzione più bilanciata possibile della domanda di prodotto.

Requisiti

Prima di iniziare questo tutorial, assicurati che siano installati i seguenti elementi:

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

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

Hai anche bisogno del permesso per accedere alla funzione ParityQC Twine Optimizer. Per richiedere l'accesso, compila questo modulo.

Configurazione

(Questo codice presuppone che tu abbia già salvato il tuo account nel tuo ambiente locale.)

Innanzitutto, importa tutti i pacchetti richiesti per questo 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

Carica il Parity Twine Optimizer dal catalogo delle Qiskit Functions:

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

Passaggio 1: definisci il problema come funzione obiettivo

Ottieni un'istanza del problema di market split dalla QOBLIB - Quantum Optimization Benchmarking Library come segue.

La funzione load_market_split_problem recupera un dato problema da QOBLIB e lo converte in un problema 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)

La funzione load_market_split_problem richiede le seguenti funzioni di parsing per recuperare ed elaborare i dati del problema di market split da 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)

Una volta definita, load_marketsplit_problem può essere usata per caricare una specifica istanza di problema dalla libreria:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Passaggio 2: converti in formato JSON

Nel primo passaggio, hai ottenuto la forma QUBO del problema. Ora, convertila in formato JSON per la funzione dell'ottimizzatore:

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

L'istanza QUBO del problema Market Split è ora convertita in formato JSON come:

json_ms_problem = optimization_problem_to_json(ms_problem)

Passaggio 3: risolvi il problema usando il Parity Twine Optimizer

Ora che hai ottenuto il problema di market split e lo hai convertito nella forma corretta, puoi trovare una soluzione usando il Twine Optimizer e un backend IBM® a tua scelta.

Per eseguire la funzione, scegli un dispositivo backend adatto; per esempio, ibm_phoenix.

Puoi usare options per un controllo aggiuntivo (opzionale) sull'invio del job:

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

dove shots è un intero che specifica il numero di esecuzioni del circuito, postprocessing_level determina se il post-processing viene applicato al risultato, transpile_only specifica se il problema viene solo transpilato in un circuito (e non risolto), e job_tags è l'etichetta usata per identificare il job sulla IBM Quantum® Platform.

Esegui l'ottimizzatore:

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

Controlla lo stato del job:

# Monitor the job status
function_job.status()

Recupera i risultati:

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

result

Il risultato è nella 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},
        },
    }
}

dove il dizionario solution corrisponde ai qubit definiti nel problema e fornisce i loro valori di spin ottimizzati. metadata fornisce informazioni sulla transpilazione (conteggio/profondità dei gate a due qubit, gate usati, qubit attivi) e vari tempi di esecuzione.

Nel contesto del problema di market split, la stringa di bit della soluzione rappresenta un vettore di assegnazione binaria usato per suddividere i mercati in due regioni separate. Un valore di 1 assegna quel mercato specifico alla Regione A, mentre un valore di 0 lo assegna alla Regione B. Per la soluzione ottimale, la combinazione bilancia la suddivisione, il che significa che entrambe le regioni ricevono esattamente metà della domanda totale dell'azienda per ogni prodotto.

Passi successivi

Consigli

• Richiedi l'accesso alla funzione completando questo modulo.
• Visita il riferimento API per questa Qiskit Function.
• Leggi la guida.
• Prova il tutorial per applicare il Parity Twine Optimizer al modello di Sherrington-Kirkpatrick.
• Consulta il preprint ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).