Resuelve el problema de reparto de mercado con el ParityQC Parity Twine Optimizer

Estimación de uso: 10 segundos en un procesador Nighthawk r2. (NOTA: Esto es solo una estimación. Tu tiempo de ejecución puede variar.)

Resultados de aprendizaje

• Obtener y dar formato al problema de reparto de mercado (Market Split) a partir de QOBLIB - Quantum Optimization Benchmarking Library.

• Configurar y utilizar el Parity Twine Optimizer para resolver una instancia de reparto de mercado.

• Aprender a elegir opciones para el Parity Twine Optimizer y qué resultados se obtienen.

Contexto

Este tutorial muestra cómo resolver el problema de reparto de mercado utilizando el ParityQC Parity Twine Optimizer.

La instancia del problema se obtiene de QOBLIB - Quantum Optimization Benchmarking Library.

Problema de reparto de mercado

El problema de reparto de mercado es un problema real de asignación de recursos, NP-difícil, que se ha convertido en una referencia para los algoritmos de optimización cuántica. Representa un desafío logístico de alto riesgo: cómo dividir un panorama complejo de clientes y productos en territorios manejables y equilibrados.

El objetivo es dividir $n$ mercados en dos regiones de ventas equilibradas de modo que cada región reciba exactamente la mitad de la demanda total de $m$ productos. La solución es la configuración específica que logra la distribución más uniforme posible de la demanda de productos, lo que permite a una empresa implementar una estrategia de logística y personal en la que ambas regiones estén equilibradas, minimizando riesgos como la escasez local de productos o la saturación de los almacenes.

A medida que aumenta el número de mercados y productos, el número de permutaciones posibles crece exponencialmente, lo que dificulta encontrar la mejor división mediante búsquedas exhaustivas tradicionales.

Formulación matemática

Sea $A$ una matriz de $m \times n$ que representa la demanda de productos en los distintos mercados, donde $A_{ij}$ es la demanda del producto $i$ en el mercado $j$.

Se define un vector de asignación binario, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$, donde:

• $x_j = 1$ asigna el mercado $j$ a la Región A.
• $x_j = 0$ asigna el mercado $j$ a la Región B.

Sea $d = [d_1, d_2, \dots, d_m]^T$ el vector de demanda total de cada producto, calculado como $d = A \cdot \mathbf{1}$. El volumen de ventas objetivo por región para el producto $i$ es exactamente $\frac{d_i}{2}$.

La restricción de optimización o factibilidad exige que las ventas totales asignadas a la Región A coincidan exactamente con la mitad de la demanda total de cada producto:

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

En la práctica, dado que rara vez es posible una división exacta, el problema se formula para minimizar la violación cuadrática de la restricción (la función de 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.$

Al expandir esto se obtiene una forma equivalente a un problema de optimización binaria cuadrática sin restricciones (QUBO).

Una vez resuelto, el vector solución $x$ determina a qué región se asigna cada mercado. Esta es la configuración que logra la distribución más equilibrada posible de la demanda de productos.

Requisitos

Antes de comenzar este tutorial, asegúrate de tener instalado lo siguiente:

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

• Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)

• NumPy (pip install numpy)

También necesitas permiso para acceder a la función ParityQC Twine Optimizer. Para solicitar acceso, completa este formulario.

Configuración

(Este código asume que ya has guardado tu cuenta en tu entorno local.)

Primero, importa todos los paquetes necesarios para este 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

Carga el Parity Twine Optimizer desde el catálogo de Qiskit Functions:

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

Paso 1: Definir el problema como una función objetivo

Obtén una instancia del problema de reparto de mercado de la QOBLIB - Quantum Optimization Benchmarking Library de la siguiente manera.

La función load_market_split_problem recupera un problema dado de QOBLIB y lo convierte en 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 función load_market_split_problem requiere las siguientes funciones de análisis (parser) para recuperar y procesar los datos del problema market split de 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 vez definida, load_marketsplit_problem se puede usar para cargar una instancia específica del problema desde la biblioteca:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

Paso 2: Convertir a formato JSON

En el primer paso, obtuviste la forma QUBO del problema. Ahora, conviértela a formato JSON para la función del optimizador:

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

La instancia QUBO del problema de reparto de mercado ya está convertida a formato JSON, como se muestra a continuación:

json_ms_problem = optimization_problem_to_json(ms_problem)

Paso 3: Resolver el problema usando el Parity Twine Optimizer

Ahora que has obtenido el problema market split y lo has convertido a la forma correcta, puedes encontrar una solución usando el Twine Optimizer y un backend de IBM® elegido.

Para ejecutar la función, elige un dispositivo backend adecuado; por ejemplo, ibm_phoenix.

Puedes usar options para tener control adicional (opcional) sobre el envío:

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

donde shots es un entero que especifica el número de ejecuciones del circuito, postprocessing_level determina si se aplica posprocesamiento al resultado, transpile_only especifica si el problema solo se transpila a un circuito (y no se resuelve), y job_tags es la etiqueta usada para identificar el job en IBM Quantum® Platform.

Ejecuta el optimizador:

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

Comprueba el estado del job:

# Monitor the job status
function_job.status()

Recupera los resultados:

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

result

El resultado tiene la 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},
        },
    }
}

donde el diccionario solution corresponde a los qubits definidos en el problema y proporciona sus valores de espín optimizados. metadata proporciona información sobre la transpilación (recuentos/profundidad de puertas de dos qubits, puertas utilizadas, qubits activos), y varios tiempos de ejecución.

En el contexto del problema market split, la cadena de bits de la solución representa un vector de asignación binaria usado para dividir los mercados en dos regiones separadas. Un valor de 1 asigna ese mercado específico a la Región A, mientras que un valor de 0 lo asigna a la Región B. Para la solución óptima, la combinación equilibra la división, lo que significa que ambas regiones reciben exactamente la mitad de la demanda total de la empresa para cada producto.

Próximos pasos

Recomendaciones

• Solicita acceso a la función completando este formulario.
• Visita la referencia de la API para esta Qiskit Function.
• Lee la guía.
• Prueba el tutorial para aplicar el Parity Twine Optimizer al modelo de Sherrington-Kirkpatrick.
• Revisa el preprint de ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).