Resolver el problema de Market Split con el Iskay Quantum Optimizer de Kipu Quantum

Nota

Las Qiskit Functions son una funcionalidad experimental disponible únicamente para usuarios del Plan Premium, Plan Flex y Plan On-Prem (a través de la API de IBM Quantum Platform) de IBM Quantum®. Se encuentran en estado de versión preliminar y están sujetas a cambios.

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

Antecedentes

Este tutorial demuestra cómo resolver el problema de Market Split utilizando el optimizador cuántico Iskay de Kipu Quantum [1]. El problema de Market Split representa un desafío real de asignación de recursos en el que los mercados deben dividirse en regiones de ventas equilibradas para cumplir objetivos exactos de demanda.

El desafío del Market Split

El problema de Market Split presenta un desafío engañosamente simple pero computacionalmente formidable en la asignación de recursos. Considera una empresa con $m$ productos que se venden en $n$ mercados diferentes, donde cada mercado adquiere un paquete específico de productos (representado por las columnas de la matriz $A$). El objetivo comercial es dividir estos mercados en dos regiones de ventas equilibradas de modo que cada región reciba exactamente la mitad de la demanda total de cada producto.

Formulación matemática:

Buscamos un vector de asignación binaria $x$, 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
• La restricción $Ax = b$ debe satisfacerse, donde $b$ representa las ventas objetivo (típicamente la mitad de la demanda total por producto)

Función de costo:

Para resolver este problema, minimizamos la violación cuadrática de las restricciones:

$C(x) = ||Ax - b||^2 = \sum_{i=1}^{m} \left(\sum_{j=1}^{n} A_{ij}x_j - b_i\right)^2$

donde:

• $A_{ij}$ representa las ventas del producto $i$ en el mercado $j$
• $x_j \in \{0,1\}$ es la asignación binaria del mercado $j$
• $b_i$ es la meta de ventas para el producto $i$ en cada región
• El costo es igual a cero precisamente cuando todas las restricciones se satisfacen

Cada término en la suma representa la desviación cuadrática respecto a la meta de ventas de un producto en particular. Cuando expandimos esta función de costo, obtenemos:

$C(x) = x^T A^T A x - 2b^T A x + b^T b$

Dado que $b^T b$ es una constante, minimizar $C(x)$ equivale a minimizar la función cuadrática $x^T A^T A x - 2b^T A x$, que es exactamente un problema QUBO (Quadratic Unconstrained Binary Optimization).

Complejidad computacional:

A pesar de su interpretación comercial directa, este problema exhibe una notable intratabilidad computacional:

• Fallo a pequeña escala: Los solucionadores convencionales de Programación Entera Mixta fallan en instancias con tan solo siete productos bajo un tiempo límite de una hora [4]
• Crecimiento exponencial: El espacio de soluciones crece exponencialmente ($2^n$ asignaciones posibles), lo que hace inviables los enfoques de fuerza bruta

Esta severa barrera computacional, combinada con su relevancia práctica para la planificación territorial y la asignación de recursos, convierte al problema de Market Split en un punto de referencia ideal para algoritmos de optimización cuántica [4].

¿Qué hace único al enfoque de Iskay?

El optimizador Iskay utiliza el algoritmo bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], que representa un avance significativo en la optimización cuántica:

Eficiencia de circuitos: El algoritmo bf-DCQO logra una reducción notable de compuertas [1]:

• Hasta 10 veces menos compuertas de entrelazamiento que el Digital Quantum Annealing (DQA)
• Circuitos significativamente menos profundos que permiten:
  • Menor acumulación de errores durante la ejecución cuántica
  • Capacidad para abordar problemas más grandes en el hardware cuántico actual
  • Sin necesidad de técnicas de mitigación de errores

Diseño no variacional: A diferencia de los algoritmos variacionales que requieren aproximadamente 100 iteraciones, bf-DCQO típicamente necesita solo aproximadamente 10 iteraciones [1]. Esto se logra mediante:

• Cálculos inteligentes del campo de sesgo a partir de distribuciones de estados medidos
• Inicio de cada iteración desde un estado energético cercano a la solución anterior
• Post-procesamiento clásico integrado con búsqueda local

Protocolos contradiabáticos: El algoritmo incorpora términos contradiabáticos que suprimen excitaciones cuánticas no deseadas durante tiempos de evolución cortos, permitiendo que el sistema permanezca cerca del estado fundamental incluso con transiciones rápidas [1].

Requisitos

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

• Qiskit IBM Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions (pip install qiskit-ibm-catalog)
• NumPy (pip install numpy)
• Requests (pip install requests)
• Opt Mapper Qiskit addon (pip install qiskit-addon-opt-mapper)

También necesitarás obtener acceso a la función Iskay Quantum Optimizer del Catálogo de Qiskit Functions.

Configuración

Primero, importa todos los paquetes necesarios para este tutorial.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit-addon-opt-mapper qiskit-ibm-catalog requests

import os
import tempfile
import time
from typing import Tuple, Optional

import numpy as np
import requests

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

print("All required libraries imported successfully")

Configurar las credenciales de IBM Quantum

Define tus credenciales de IBM Quantum® Platform. Necesitarás:

• Token de API: Su clave de API de 44 caracteres de IBM Quantum Platform
• CRN de instancia: Su identificador de instancia de IBM Cloud®

token = "<YOUR_API_KEY>"
instance = "<YOUR_INSTANCE_CRN>"

Paso 1: Mapear las entradas clásicas a un problema cuántico

Comenzamos mapeando nuestro problema clásico a una representación compatible con la computación cuántica. Este paso involucra:

1. Conexión al Iskay Quantum Optimizer
2. Carga y formulación del problema de Market Split
3. Comprensión del algoritmo bf-DCQO que lo resolverá

Conexión al Iskay Quantum Optimizer

Comenzamos estableciendo una conexión al Catálogo de Qiskit Functions y cargando el Iskay Quantum Optimizer. El optimizador Iskay es una función cuántica proporcionada por Kipu Quantum que implementa el algoritmo bf-DCQO para resolver problemas de optimización en hardware cuántico.

catalog = QiskitFunctionsCatalog(token=token, instance=instance)
iskay_solver = catalog.load("kipu-quantum/iskay-quantum-optimizer")

print("Iskay optimizer loaded successfully")
print("Ready to solve optimization problems using bf-DCQO algorithm")

Cargar y formular el problema

Comprender el formato de datos del problema

Las instancias de problemas de QOBLIB (Quantum Optimization Benchmarking Library) [2] se almacenan en un formato de texto simple. Examinemos el contenido real de nuestra instancia objetivo ms_03_200_177.dat:

3 20
60   92  161   53   97    2   75   81    6  139  132   45  108  112  181   93  152  200  164   51 1002
176  196   41  143    2   88    0   79   10   71   75  148   82  135   34  187   33  155   58   46  879
68   68  179  173  127  163   48   49   99   78   44   52  173  131   73  198   84  109  180   95 1040

Estructura del formato:

• Primera línea: 3 20

  • 3 = número de productos (restricciones/filas en la matriz $A$)
  • 20 = número de mercados (variables/columnas en la matriz $A$)

• Siguientes 3 líneas: Matriz de coeficientes $A$ y vector objetivo $b$

  • Cada línea tiene 21 números: los primeros 20 son coeficientes de fila, el último es el objetivo
  • Línea 2: 60 92 161 ... 51 | 1002
    • Los primeros 20 números: Cuánto del Producto 1 vende cada uno de los 20 mercados
    • Último número (1002): Ventas objetivo del Producto 1 en una región
  • Línea 3: 176 196 41 ... 46 | 879
    • Ventas del Producto 2 por mercado y objetivo (879)
  • Línea 4: 68 68 179 ... 95 | 1040
    • Ventas del Producto 3 por mercado y objetivo (1040)

Interpretación comercial:

• El Mercado 0 vende: 60 unidades del Producto 1, 176 unidades del Producto 2, 68 unidades del Producto 3
• El Mercado 1 vende: 92 unidades del Producto 1, 196 unidades del Producto 2, 68 unidades del Producto 3
• Y así sucesivamente para los 20 mercados...
• Objetivo: Dividir estos 20 mercados en dos regiones donde cada región reciba exactamente 1002 unidades del Producto 1, 879 unidades del Producto 2 y 1040 unidades del Producto 3

Transformación QUBO

De restricciones a QUBO: la transformación matemática

El poder de la optimización cuántica reside en transformar problemas restringidos en formas cuadráticas sin restricciones [4]. Para el problema de Market Split, convertimos las restricciones de igualdad

$Ax = b$

donde $x \in \{0,1\}^n$, en un QUBO penalizando las violaciones de restricciones.

El método de penalización: Dado que necesitamos que $Ax = b$ se cumpla exactamente, minimizamos la violación cuadrática: $f(x) = ||Ax - b||^2$

Esto es igual a cero precisamente cuando todas las restricciones se satisfacen. Expandiendo algebraicamente: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Objetivo QUBO: Dado que $b^T b$ es constante, nuestra optimización se convierte en: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Información clave: Esta transformación es exacta, no aproximada. Las restricciones de igualdad se elevan al cuadrado de forma natural en forma cuadrática sin requerir variables auxiliares ni parámetros de penalización, lo que hace que esta formulación sea matemáticamente elegante y computacionalmente eficiente para los solucionadores cuánticos [4]. Utilizaremos la clase OptimizationProblem para definir nuestro problema restringido y luego lo convertiremos al formato QUBO usando OptimizationProblemToQubo, ambas del paquete qiskit_addon_opt_mapper. Esto maneja automáticamente la transformación basada en penalización.

Implementar funciones de carga de datos y conversión a QUBO

Ahora definimos tres funciones utilitarias:

1. parse_marketsplit_dat() - Analiza el formato de archivo .dat y extrae las matrices $A$ y $b$
2. fetch_marketsplit_data() - Descarga instancias del problema directamente del repositorio QOBLIB

def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:
    """
    Parse a market split problem from a .dat file format.

    Parameters
    ----------
    filename : str
        Path to the .dat file containing the market split problem data.

    Returns
    -------
    A : np.ndarray
        Coefficient matrix of shape (m, n) where m is the number of products
        and n is the number of markets.
    b : np.ndarray
        Target vector of shape (m,) containing the target sales per product.
    """
    with open(filename, "r", 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)
    m, n = map(int, lines[0].split())

    # Next m lines: each row of A followed by corresponding element of b
    A, b = [], []
    for i in range(1, m + 1):
        values = list(map(int, lines[i].split()))
        A.append(values[:-1])  # First n values: product sales per market
        b.append(values[-1])  # Last value: target sales for this product

    return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)

def fetch_marketsplit_data(
    instance_name: str = "ms_03_200_177.dat",
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Fetch market split data directly from the QOBLIB repository.

    Parameters
    ----------
    instance_name : str
        Name of the .dat file to fetch (default: "ms_03_200_177.dat").

    Returns
    -------
    A : np.ndarray or None
        Coefficient matrix if successful, None if failed.
    b : np.ndarray or None
        Target vector if successful, None if failed.
    """
    url = f"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}"

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".dat", delete=False, encoding="utf-8"
        ) as f:
            f.write(response.text)
            temp_path = f.name

        try:
            return parse_marketsplit_dat(temp_path)
        finally:
            os.unlink(temp_path)
    except Exception as e:
        print(f"Error: {e}")
        return None, None

Cargar la instancia del problema

Ahora cargamos la instancia específica del problema ms_03_200_177.dat de QOBLIB [2]. Esta instancia tiene:

• 3 productos (restricciones)
• 20 mercados (variables de decisión binarias)
• Más de 1 millón de asignaciones posibles de mercados por explorar ($2^{20} = 1,048,576$)

# Load the problem instance
instance_name = "ms_03_200_177.dat"
A, b = fetch_marketsplit_data(instance_name=instance_name)

if A is not None:
    print("Successfully loaded problem instance from QOBLIB")
    print("\nProblem Instance Analysis:")
    print("=" * 50)
    print(f"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}")
    print(f"   → {A.shape[0]} products (constraints)")
    print(f"   → {A.shape[1]} markets (decision variables)")
    print(f"Target Vector b: {b}")
    print("   → Target sales per product for each region")
    print(
        f"Solution Space: 2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Convertir al formato QUBO

Ahora transformamos el problema de optimización con restricciones al formato QUBO:

# Create optimization problem
ms = OptimizationProblem(instance_name.replace(".dat", ""))

# Add binary variables (one for each market)
ms.binary_var_list(A.shape[1])

# Add equality constraints (one for each product)
for idx, rhs in enumerate(b):
    ms.linear_constraint(A[idx, :], sense="==", rhs=rhs)

# Convert to QUBO with penalty parameter
qubo = OptimizationProblemToQubo(penalty=1).convert(ms)

print("QUBO Conversion Complete:")
print("=" * 50)
print(f"Number of variables: {qubo.get_num_vars()}")
print(f"Constant term: {qubo.objective.constant}")
print(f"Linear terms: {len(qubo.objective.linear.to_dict())}")
print(f"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}")

Convertir QUBO al formato de Iskay

Ahora necesitamos convertir el objeto QUBO al formato de diccionario requerido por el Iskay Optimizer de Kipu Quantum.

Los argumentos problem y problem_type codifican un problema de optimización de la forma

$$\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}$$

donde

$$C(x_1, ... , x_n) = a + \sum_{i} b_i x_i + \sum_{i, j} c_{i, j} x_i x_j + ... + \sum_{k_1, ..., k_m} g_{k_1, ..., k_m} x_{k_1} ... x_{k_m}$$

• Al elegir problem_type = "binary", especificas que la función de costo está en formato binary, lo que significa que $D = \{0, 1\}^{n}$, es decir, la función de costo está escrita en formulación QUBO/HUBO.
• Por otro lado, al elegir problem_type = "spin", la función de costo está escrita en formulación de Ising, donde $D = \{-1, 1\}^{n}$.

Los coeficientes del problema deben codificarse en un diccionario de la siguiente manera:

$$\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \quad (i \neq j) \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"}&: \quad &g_{k_1, ..., k_m}, \quad (k_1 \neq k_2 \neq \dots \neq k_m) \\ \nonumber &\texttt{\}} \end{align}$$

Ten en cuenta que las claves del diccionario deben ser cadenas que contengan una tupla válida de enteros no repetidos. Para problemas binarios, sabemos que:

$$x_i^2 = x_i$$

para $i=j$ (ya que $x_i \in \{0,1\}$ implica $x_i \cdot x_i = x_i$). Entonces, en su formulación QUBO, si tiene tanto contribuciones lineales $b_i x_i$ como contribuciones cuadráticas diagonales $c_{i,i} x_i^2$, estos términos deben combinarse en un único coeficiente lineal:

Coeficiente lineal total para la variable $x_i$: $b_i + c_{i,i}$

Esto significa:

• Los términos lineales como "(i, )" contienen: coeficiente lineal original + coeficiente cuadrático diagonal
• Los términos cuadráticos diagonales como "(i, i)" NO deben aparecer en el diccionario final
• Solo los términos cuadráticos fuera de la diagonal como "(i, j)" donde $i \neq j$ deben incluirse como entradas separadas

Ejemplo: Si su QUBO tiene $3x_1 + 2x_1^2 + 4x_1 x_2$, el diccionario de Iskay debe contener:

• "(0, )": 5.0 (combinando $3 + 2 = 5$)
• "(0, 1)": 4.0 (término fuera de la diagonal)

NO entradas separadas para "(0, )": 3.0 y "(0, 0)": 2.0.

# Convert QUBO to Iskay dictionary format:

# Create empty Iskay input dictionary
iskay_input_problem = {}

# Convert QUBO to Iskay dictionary format
iskay_input_problem = {"()": qubo.objective.constant}

for i in range(qubo.get_num_vars()):
    for j in range(i, qubo.get_num_vars()):
        if i == j:
            # Add linear term (including diagonal quadratic contribution)
            iskay_input_problem[f"({i}, )"] = float(
                qubo.objective.linear.to_dict().get(i)
            ) + float(qubo.objective.quadratic.to_dict().get((i, i)))
        else:
            # Add off-diagonal quadratic term
            iskay_input_problem[f"({i}, {j})"] = float(
                qubo.objective.quadratic.to_dict().get((i, j))
            )

# Display Iskay dictionary summary
print("Iskay Dictionary Format:")
print("=" * 50)
print(f"Total coefficients: {len(iskay_input_problem)}")
print(f"  • Constant term: {iskay_input_problem['()']}")
print(
    f"  • Linear terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

# Get first 10 and last 5 items properly
items = list(iskay_input_problem.items())
first_10 = list(enumerate(items[:10]))
last_5 = list(enumerate(items[-5:], start=len(items) - 5))

for i, (key, value) in first_10 + last_5:
    coeff_type = (
        "constant"
        if key == "()"
        else "linear"
        if ", )" in key
        else "quadratic"
    )
    print(f"  {key}: {value} ({coeff_type})")
print("  ...")
print("\n✓ Problem ready for Iskay optimizer!")

Comprender el algoritmo bf-DCQO

Antes de ejecutar la optimización, comprendamos el sofisticado algoritmo cuántico que impulsa a Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

¿Qué es bf-DCQO?

bf-DCQO se basa en la evolución temporal de un sistema cuántico donde la solución del problema está codificada en el estado fundamental (estado de menor energía) del Hamiltoniano cuántico final [1]. El algoritmo aborda un desafío fundamental en la optimización cuántica:

El desafío: La computación cuántica adiabática tradicional requiere una evolución muy lenta para mantener las condiciones del estado fundamental según el teorema adiabático. Esto exige circuitos cuánticos cada vez más profundos a medida que crece la complejidad del problema, lo que conduce a más operaciones de compuertas y errores acumulados.

La solución: bf-DCQO utiliza protocolos contradiabáticos para permitir una evolución rápida mientras mantiene la fidelidad del estado fundamental, reduciendo drásticamente la profundidad de los circuitos.

Marco matemático

El algoritmo minimiza una función de costo de la forma:

$\min_{(x_1,x_2,...,x_n) \in D} C(x_1,x_2,...,x_n)$

donde $D = \{0,1\}^n$ para variables binarias y:

$C(x) = a + \sum_i b_i x_i + \sum_{i,j} c_{ij} x_i x_j + ... + \sum g_{k_1,...,k_m} x_{k_1}...x_{k_m}$

Para nuestro problema de Market Split, la función de costo es:

$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$

El papel de los términos contradiabáticos

Los términos contradiabáticos son términos adicionales introducidos en el Hamiltoniano dependiente del tiempo que suprimen las excitaciones no deseadas durante la evolución cuántica. A continuación se explica por qué son cruciales:

En la optimización cuántica adiabática, evolucionamos el sistema de acuerdo con un Hamiltoniano dependiente del tiempo:

$H(t) = \left(1 - \frac{t}{T}\right) H_{\text{initial}} + \frac{t}{T} H_{\text{problem}}$

donde $H_{\text{problem}}$ codifica nuestro problema de optimización. Para mantener el estado fundamental durante una evolución rápida, añadimos términos contradiabáticos:

$H_{\text{CD}}(t) = H(t) + H_{\text{counter}}(t)$

Estos términos contradiabáticos hacen lo siguiente:

1. Suprimen transiciones no deseadas: Evitan que el estado cuántico salte a estados excitados durante una evolución rápida
2. Permiten tiempos de evolución más cortos: Nos permiten alcanzar el estado final mucho más rápido sin violar la adiabaticidad
3. Reducen la profundidad del circuito: Una evolución más corta conduce a menos compuertas y menos errores

El impacto práctico es dramático: bf-DCQO utiliza hasta 10 veces menos compuertas de entrelazamiento que el Digital Quantum Annealing [1], lo que lo hace práctico para el hardware cuántico ruidoso de la actualidad.

Optimización iterativa con campo de sesgo

A diferencia de los algoritmos variacionales que optimizan los parámetros del circuito a través de muchas iteraciones, bf-DCQO utiliza un enfoque guiado por campo de sesgo que converge en aproximadamente 10 iteraciones [1]:

Proceso de iteración:

1. Evolución cuántica inicial: Comenzar con un circuito cuántico que implementa el protocolo de evolución contradiabática

2. Medición: Medir el estado cuántico para obtener una distribución de probabilidad sobre cadenas de bits

3. Cálculo del campo de sesgo: Analizar las estadísticas de medición y calcular un campo de sesgo óptimo $h_i$ para cada qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Siguiente iteración: El campo de sesgo modifica el Hamiltoniano para la siguiente iteración: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Esto permite comenzar cerca de la solución buena encontrada previamente, realizando efectivamente una forma de "búsqueda local cuántica"

5. Convergencia: Repetir hasta que la calidad de la solución se estabilice o se alcance un número máximo de iteraciones

Ventaja clave: Cada iteración proporciona un progreso significativo hacia la solución óptima al incorporar información de mediciones anteriores, a diferencia de los métodos variacionales que deben explorar el espacio de parámetros a ciegas.

Post-procesamiento clásico integrado

Después de que la optimización cuántica converge, Iskay realiza un post-procesamiento clásico de búsqueda local:

• Exploración por inversión de bits: Invertir bits de manera sistemática o aleatoria en la mejor solución medida
• Evaluación de energía: Calcular $C(x)$ para cada solución modificada
• Selección voraz: Aceptar mejoras que reduzcan la función de costo
• Múltiples pasadas: Realizar varias pasadas (controladas por postprocessing_level)

Este enfoque híbrido compensa los errores de inversión de bits causados por imperfecciones del hardware y errores de lectura, asegurando soluciones de alta calidad incluso en dispositivos cuánticos ruidosos.

Por qué bf-DCQO sobresale en el hardware actual

El algoritmo bf-DCQO está diseñado específicamente para sobresalir en los dispositivos cuánticos ruidosos de escala intermedia (NISQ) actuales [1]:

1. Resiliencia ante errores: Menos compuertas (reducción de 10 veces) significa dramáticamente menos acumulación de errores
2. Sin necesidad de mitigación de errores: La eficiencia inherente del algoritmo elimina la necesidad de técnicas costosas de mitigación de errores [1]
3. Escalabilidad: Puede manejar problemas con hasta 156 qubits (156 variables binarias) con mapeo directo de qubits [1]
4. Rendimiento comprobado: Alcanza razones de aproximación del 100% en instancias de referencia de MaxCut y HUBO [1]

Ahora veamos este poderoso algoritmo en acción con nuestro problema de Market Split.

Paso 2: Optimizar el problema para la ejecución en hardware cuántico

El algoritmo bf-DCQO maneja automáticamente la optimización de circuitos, creando circuitos cuánticos poco profundos con términos contradiabáticos diseñados específicamente para el backend objetivo.

Configurar la optimización

El Iskay Optimizer requiere varios parámetros clave para resolver eficazmente su problema de optimización. Examinemos cada parámetro y tu función en el proceso de optimización cuántica:

Parámetros requeridos

Parámetro	Tipo	Descripción	Ejemplo
problem	Dict[str, float]	Coeficientes QUBO en formato de claves de cadena	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Especificación de formato: "binary" para QUBO o "spin" para Ising	"binary"
backend_name	str	Dispositivo cuántico objetivo	"ibm_fez"

Conceptos esenciales

• Formato del problema: Utilizamos "binary" ya que nuestras variables son binarias (0/1), representando asignaciones de mercados.
• Selección de backend: Elige entre las QPUs disponibles (por ejemplo, "ibm_fez") según sus necesidades e instancia de recursos de cómputo.
• Estructura QUBO: Nuestro diccionario del problema contiene los coeficientes exactos de la transformación matemática.

Opciones avanzadas (opcional)

Iskay proporciona capacidades de ajusta fino a través de parámetros opcionales. Si bien los valores predeterminados funcionan bien para la mayoría de los problemas, puede personalizar el comportamiento para requisitos específicos:

Parámetro	Tipo	Predeterminado	Descripción
shots	int	10000	Mediciones cuánticas por iteración (mayor = más preciso)
num_iterations	int	10	Iteraciones del algoritmo (más iteraciones pueden mejorar la calidad de la solución)
use_session	bool	True	Usar sesiones de IBM para reducir tiempos de cola
seed_transpiler	int	None	Establecer para compilación reproducible de circuitos cuánticos
direct_qubit_mapping	bool	False	Mapear qubits virtuales directamente a qubits físicos
job_tags	List[str]	None	Etiquetas personalizadas para el seguimiento de trabajos
preprocessing_level	int	0	Intensidad del preprocesamiento del problema (0-3) - ve detalles a continuación
postprocessing_level	int	2	Nivel de refinamiento de la solución (0-2) - ve detalles a continuación
transpilation_level	int	0	Pruebas de optimización del transpilador (0-5) - ve detalles a continuación
transpile_only	bool	False	Analizar la optimización de circuitos sin ejecutar la ejecución completa

Niveles de preprocesamiento (0-3): Especialmente importantes para problemas más grandes que actualmente no caben en los tiempos de coherencia del hardware. Los niveles de preprocesamiento más altos logran profundidades de circuito más reducidas mediante aproximaciones en la transpilación del problema:

• Nivel 0: Exacto, circuitos más largos
• Nivel 1: Buen equilibrio entre precisión y aproximación, eliminando solo las compuertas con ángulos en el percentil más bajo del 10%
• Nivel 2: Aproximación ligeramente mayor, eliminando las compuertas con ángulos en el percentil más bajo del 20% y usando approximation_degree=0.95 en la transpilación
• Nivel 3: Nivel máximo de aproximación, eliminando las compuertas en el percentil más bajo del 30% y usando approximation_degree=0.90 en la transpilación

Niveles de transpilación (0-5): Controlan las pruebas avanzadas de optimización del transpilador para la compilación de circuitos cuánticos. Esto puede generar un aumento en la sobrecarga clásica, y en algunos casos puede no cambiar la profundidad del circuito. El valor predeterminado 2 en general produce el circuito más pequeño y es relativamente rápido.

• Nivel 0: Optimización del circuito DCQO descompuesto (disposición, enrutamiento, programación)
• Nivel 1: Optimización de PauliEvolutionGate y luego del circuito DCQO descompuesto (max_trials=10)
• Nivel 2: Optimización de PauliEvolutionGate y luego del circuito DCQO descompuesto (max_trials=15)
• Nivel 3: Optimización de PauliEvolutionGate y luego del circuito DCQO descompuesto (max_trials=20)
• Nivel 4: Optimización de PauliEvolutionGate y luego del circuito DCQO descompuesto (max_trials=25)
• Nivel 5: Optimización de PauliEvolutionGate y luego del circuito DCQO descompuesto (max_trials=50)

Niveles de post-procesamiento (0-2): Controlan cuánta optimización clásica se realiza, compensando errores de inversión de bits con diferente número de pasadas voraces de una búsqueda local:

• Nivel 0: 1 pasada
• Nivel 1: 2 pasadas
• Nivel 2: 3 pasadas

Modo solo transpilación: Ahora disponible para usuarios que desean analizar la optimización de circuitos sin ejecutar el algoritmo cuántico completo.

Ejemplo de configuración personalizada

A continuación se muestra cómo podría configurar Iskay con diferentes ajustes:

custom_options = {
    "shots": 15_000,                                        # Higher shot count for better statistics
    "num_iterations": 12,                                   # More iterations for solution refinement
    "preprocessing_level": 1,                               # Light preprocessing for problem simplification
    "postprocessing_level": 2,                              # Maximum postprocessing for solution quality
    "transpilation_level": 3,                               # Using higher transpilation level for circuit optimization
    "seed_transpiler": 42,                                  # Fixed seed for reproducible results
    "job_tags": ["market_split"]                            # Custom tracking tags
}

Para este tutorial, mantendremos la mayoría de los parámetros predeterminados y solo cambiaremos el número de iteraciones del campo de sesgo:

# Specify the target backend
backend_name = "ibm_fez"

# Set the number of bias-field iterations and set a tag to identify the jobs
options = {
    "num_iterations": 3,  # Change number of bias-field iterations
    "job_tags": ["market_split_example"],  # Tag to identify jobs
}

# Configure Iskay optimizer
iskay_input = {
    "problem": iskay_input_problem,
    "problem_type": "binary",
    "backend_name": backend_name,
    "options": options,
}

print("Iskay Optimizer Configuration:")
print("=" * 40)
print(f"  Backend: {backend_name}")
print(f"  Problem: {len(iskay_input['problem'])} terms")
print("  Algorithm: bf-DCQO")

Paso 3: Ejecutar utilizando primitivas de Qiskit

Ahora enviamos nuestro problema para ejecutarlo en hardware de IBM Quantum. El algoritmo bf-DCQO realizarás lo siguiente:

1. Construir circuitos cuánticos poco profundos con términos contradiabáticos
2. Ejecutar aproximadamente 10 iteraciones con optimización de campo de sesgo
3. Realizar post-procesamiento clásico con búsqueda local
4. Devolver la asignación óptima de mercados

# Submit the optimization job
print("Submitting optimization job to Kipu Quantum...")
print(
    f"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms"
)
print(
    "Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)"
)

job = iskay_solver.run(**iskay_input)

print("\nJob successfully submitted!")
print(f"Job ID: {job.job_id}")
print("Optimization in progress...")
print(
    f"The bf-DCQO algorithm will efficiently explore {2**A.shape[1]:,} possible assignments"
)

Monitorear el estado del trabajo

Puedes verificar el estado actual de tu trabajo de optimización. Los estados posibles son:

• QUEUED: El trabajo está esperando en la cola
• RUNNING: El trabajo se está ejecutando actualmente en hardware cuántico
• DONE: El trabajo se completó exitosamente
• CANCELED: El trabajo fue cancelado
• ERROR: El trabajo encontró un error

# Check job status
print(f"Job status: {job.status()}")

Esperar la finalización

Esta celda se bloqueará hasta que el trabajo se complete. El proceso de optimización incluye:

• Tiempo de cola (espera para acceder al hardware cuántico)
• Tiempo de ejecución (ejecución del algoritmo bf-DCQO con aproximadamente 10 iteraciones)
• Tiempo de post-procesamiento (búsqueda local clásica)

Los tiempos típicos de finalización varían desde unos pocos minutos hasta decenas de minutos dependiendo de las condiciones de la cola.

# Wait for job completion
while True:
    status = job.status()
    print(
        f"Waiting for job {job.job_id} to complete... (status: {status})",
        end="\r",
        flush=True,
    )
    if status in ["DONE", "CANCELED", "ERROR"]:
        print(
            f"\nJob {job.job_id} completed with status: {status}" + " " * 20
        )
        break
    time.sleep(30)

# Retrieve the optimization results
result = job.result()
print("\nOptimization complete!")

Paso 4: Post-procesar y devolver el resultado en el formato clásico deseado

Ahora post-procesamos los resultados de la ejecución cuántica. Esto incluye:

• Análisis de la estructura de la solución
• Validación del cumplimiento de restricciones
• Comparación con enfoques clásicos

Analizar resultados

Comprender la estructura del resultado

Iskay devuelve un diccionario de resultados completo que contiene:

• solution: Un diccionario que mapea índices de variables a sus valores óptimos (0 o 1)
• solution_info: Información detallada que incluye:
  • bitstring: La asignación óptima como una cadena binaria
  • cost: El valor de la función objetivo (debe ser 0 para una satisfacción perfecta de las restricciones)
  • mapping: Cómo las posiciones de la cadena de bits se mapean a las variables del problema
  • seed_transpiler: Semilla utilizada para la reproducibilidad
• prob_type: Si la solución está en formato binario o de espín

Examinemos la solución devuelta por el optimizador cuántico.

# Display the optimization results
print("Optimization Results")
print("=" * 50)
print(f"Problem Type: {result['prob_type']}")
print("\nSolution Info:")
print(f"  Bitstring: {result['solution_info']['bitstring']}")
print(f"  Cost: {result['solution_info']['cost']}")
print("\nSolution (first 10 variables):")
for i, (var, val) in enumerate(list(result["solution"].items())[:10]):
    print(f"  {var}: {val}")
print("  ...")

Validación de la solución

Ahora validamos si la solución cuántica satisface las restricciones del Market Split. El proceso de validación verifica:

¿Qué es una violación de restricción?

• Para cada producto $i$, calculamos las ventas reales en la Región A: $(Ax)_i$
• Lo comparamos con las ventas objetivo $b_i$
• La violación es la diferencia absoluta: $|(Ax)_i - b_i|$
• Una solución factible tiene cero violaciones para todos los productos

Lo que esperamos:

• Caso ideal: Violación total = 0 (todas las restricciones perfectamente satisfechas)
  • La Región A recibe exactamente 1002 unidades del Producto 1, 879 unidades del Producto 2 y 1040 unidades del Producto 3
  • La Región B recibe las unidades restantes (también 1002, 879 y 1040 respectivamente)
• Caso bueno: La violación total es pequeña (solución casi óptima)
• Caso deficiente: Violaciones grandes indican que la solución no satisface los requisitos comerciales

La función de validación calculará:

1. Las ventas reales por producto en cada región
2. Las violaciones de restricciones para cada producto
3. La distribución de mercados entre regiones

def validate_solution(A, b, solution):
    """Validate market split solution."""
    x = np.array(solution)
    region_a = A @ x
    region_b = A @ (1 - x)
    violations = np.abs(region_a - b)

    return {
        "target": b,
        "region_a": region_a,
        "region_b": region_b,
        "violations": violations,
        "total_violation": np.sum(violations),
        "is_feasible": np.sum(violations) == 0,
        "region_a_markets": int(np.sum(x)),
        "region_b_markets": len(x) - int(np.sum(x)),
    }

# Convert bitstring to list of integers and validate
optimal_assignment = [
    int(bit) for bit in result["solution_info"]["bitstring"]
]
validation = validate_solution(A, b, optimal_assignment)

Interpretar los resultados de la validación

Los resultados de la validación muestran si el optimizador cuántico encontró una solución factible. Examinemos lo siguiente:

Verificación de factibilidad:

• is_feasible = True significa que la solución satisface perfectamente todas las restricciones (violación total = 0)
• is_feasible = False significa que algunas restricciones fueron violadas

Análisis de ventas:

• Compare las ventas objetivo versus las reales para cada producto
• Para una solución perfecta: Real = Objetivo para todos los productos en ambas regiones
• La diferencia indica qué tan cerca estamos de la división de mercados deseada

Distribución de mercados:

• Muestra cuántos mercados están asignados a cada región
• No hay requisito de que el número de mercados sea igual, solo que se cumplan los objetivos de ventas

print("Solution Validation")
print("=" * 50)
print(f"Feasible solution: {validation['is_feasible']}")
print(f"Total constraint violation: {validation['total_violation']}")

print("\nSales Analysis (Target vs Actual):")
for i, (target, actual_a, actual_b) in enumerate(
    zip(validation["target"], validation["region_a"], validation["region_b"])
):
    violation_a = abs(actual_a - target)
    violation_b = abs(actual_b - target)
    print(f"  Product {i+1}:")
    print(f"    Target: {target}")
    print(f"    Region A: {actual_a} (violation: {violation_a})")
    print(f"    Region B: {actual_b} (violation: {violation_b})")

print("\nMarket Distribution:")
print(f"  Region A: {validation['region_a_markets']} markets")
print(f"  Region B: {validation['region_b_markets']} markets")

Evaluación de la calidad de la solución

Basándonos en los resultados de la validación anteriores, podemos evaluar la calidad de la solución cuántica:

Si is_feasible = True (Violación total = 0):

• El optimizador cuántico encontró exitosamente una solución óptima
• Todas las restricciones comerciales se satisfacen perfectamente
• Esto demuestra una ventaja cuántica en un problema donde los solucionadores clásicos tienen dificultades [4]

Si is_feasible = False (Violación total > 0):

• La solución es casi óptima pero no perfecta
• Las violaciones pequeñas pueden ser aceptables en la práctica
• Considera ajustar los parámetros del optimizador:
  • Aumente num_iterations para más pasadas de optimización
  • Aumente postprocessing_level para más refinamiento clásico
  • Aumente shots para mejores estadísticas de medición

Interpretación de la función de costo:

• El valor de cost de solution_info es igual a $||Ax - b||^2$
• Costo = 0 indica satisfacción perfecta de las restricciones
• Valores de costo más altos indican violaciones de restricciones mayores

Conclusión

Lo que logramos

En este tutorial, logramos exitosamente:

1. Cargar un problema real de optimización: Obtuvimos una instancia desafiante de Market Split de la biblioteca de referencia QOBLIB [2]
2. Transformar al formato QUBO: Convertimos el problema con restricciones en una formulación cuadrática sin restricciones [3]
3. Aprovechar algoritmos cuánticos avanzados: Utilizamos el algoritmo bf-DCQO de Kipu Quantum con términos contradiabáticos [1]
4. Obtener soluciones óptimas: Encontramos soluciones factibles que satisfacen todas las restricciones

Conclusiones clave

Innovación algorítmica: El algoritmo bf-DCQO representa un avance significativo [1]:

• 10 veces menos compuertas que el digital quantum annealing
• Aproximadamente 10 iteraciones en lugar de aproximadamente 100 para métodos variacionales
• Resiliencia ante errores integrada mediante la eficiencia de los circuitos

Términos contradiabáticos: Permiten una evolución cuántica rápida mientras mantienen la fidelidad del estado fundamental, haciendo que la optimización cuántica sea práctica en el hardware ruidoso actual [1].

Guía por campo de sesgo: El enfoque iterativo de campo de sesgo permite que cada iteración comience cerca de las buenas soluciones encontradas previamente, proporcionando una forma de búsqueda local mejorada cuánticamente [1].

Próximos pasos

Para profundizar su comprensión y explorar más:

1. Probar diferentes instancias: Experimente con otras instancias de QOBLIB de tamaños variados
2. Ajustar parámetros: Modifica num_iterations, preprocessing_level, postprocessing_level
3. Comparar con métodos clásicos: Realiza comparaciones con solucionadores de optimización clásicos
4. Probar diferentes estrategias: Intente encontrar una mejor codificación para el problema o formúlelo como HUBO (si es posible)
5. Aplicar a su dominio: Adapte las técnicas de formulación QUBO/HUBO a sus propios problemas de optimización

Referencias

[1] IBM Quantum. "Kipu Quantum Optimization." IBM Quantum Documentation.

[2] QOBLIB - Quantum Optimization Benchmarking Library. Zuse Institute Berlin (ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] Glover, F., Kochenberger, G., & Du, Y. (2019). "Quantum bridge analytics I: a tutorial on formulating and using QUBO models." 4OR: A Quarterly Journal of Operations Research, 17(4), 335-371.

[4] Lodi, A., Tramontani, A., & Weninger, K. (2023). "The Intractable Decathlon: Benchmarking Hard Combinatorial Problems." INFORMS Journal on Computing.