Resumen Técnico: El Decatlón Intratable – Una Biblioteca de Benchmarking para la Optimización Cuántica

Definición del Problema

El artículo aborda la necesidad crítica de un benchmarking sistemático, justo y comparable de los algoritmos de optimización heurística cuántica frente a los solvers clásicos de vanguardia. Si bien el hardware cuántico ha avanzado hasta un punto en el que el benchmarking a gran escala es factible, el campo carece de un conjunto estandarizado de instancias de problemas que sean simultáneamente difíciles para los métodos clásicos en escalas manejables y relevantes para aplicaciones prácticas.

Los autores presentan el Decatlón Intratable, una colección de diez clases distintas de problemas de optimización combinatoria. Estos problemas se seleccionan porque:

1. Son difíciles para los solvers clásicos existentes (a menudo requiriendo la prueba de la optimalidad o el hallazgo de soluciones factibles) en tamaños de sistema que van desde menos de 100 hasta aproximadamente 100,000 variables de decisión.
2. Son predominantemente "difíciles de forma primal" (primal difficult), lo que significa que encontrar una buena solución es difícil, lo cual se alinea con las capacidades de los actuales algoritmos cuánticos heurísticos.
3. Se mapean a aplicaciones prácticamente relevantes en logística, finanzas, diseño de redes y física.
4. Pueden modelarse utilizando variables enteras (preferiblemente binarias) con coeficientes enteros, mitigando los problemas de precisión numérica comunes en las formulaciones cuánticas.

Las diez clases de problemas son:

• División de Mercado (Market Split): Problemas de suma de subconjuntos multidimensionales.
• Secuencias Binarias de Baja Autocorrelación (LABS): Búsqueda de secuencias binarias con mínima autocorrelación.
• Descomposición de Birkhoff Mínima: Descomponer matrices doubly estocásticas en el número mínimo de matrices de permutación.
• Empaquetamiento de Árboles de Steiner (Steiner Tree Packing): Empaquetar árboles de Steiner disjuntos en nodos dentro de un grafo.
• Programación de Torneos Deportivos: Programar torneos de doble vuelta con restricciones complejas.
• Optimización de Portafolio: Optimización de media-varianza multiperiodo con costos de transacción.
• Conjunto Independiente Máximo (MIS): Encontrar el conjunto más grande de vértices no adyacentes en un grafo.
• Diseño de Redes: Construir grafos dirigidos para minimizar la carga máxima de las aristas.
• Problema de Rutas de Vehículos (CVRP): Rutas de vehículos con capacidad limitada y tamaño de flota fijo.
• Diseño de Topología: Minimizar el diámetro de la red dado un orden y grado de los nodos (Problema de Orden y Grado).

Metodología

Los autores proponen un marco de benchmarking independiente del modelo para permitir la máxima flexibilidad en la elección de algoritmos, modelos y plataformas de hardware. La metodología incluye:

1. Formulación y Modelado de Problemas

• Enfoque en Enteros: Los problemas se definen sobre variables de decisión enteras $x \in \mathbb{Z}^n$ con objetivos y restricciones lineales o cuadráticas. Los coeficientes se reescalan a enteros para evitar imprecisiones numéricas.
• Agnosticismo del Modelo: Aunque la biblioteca proporciona formulaciones estándar de Programación Lineal Entera Mixta (MIP) y Optimización Binaria No Restringida Cuadrática (QUBO), el objetivo del benchmarking no está ligado a una formulación específica. Esto reconoce que reformular un problema (por ejemplo, de ILP a QUBO) puede cambiar drásticamente el tamaño y la densidad del problema, introduciendo potencialmente nuevos desafíos o ventajas para solvers específicos.
• Factibilidad vs. Optimización: El marco distingue entre problemas de factibilidad (encontrar cualquier solución válida) y problemas de optimización (encontrar la mejor solución). Dado que la mayoría de los algoritmos cuánticos son heurísticos sin garantías de optimalidad, el benchmark se centra en encontrar soluciones factibles de alta calidad en lugar de probar la optimalidad global.

2. Métricas e Informes

Para asegurar la reproducibilidad y comparabilidad, los autores definen métricas específicas:

• Calidad de la Solución: El mejor valor objetivo encontrado a través de las repeticiones. Para algoritmos estocásticos, se reporta el número de ejecuciones exitosas (encontrar una solución dentro de una tolerancia $\epsilon$ de la mejor solución encontrada).
• Recursos Computacionales:
  • Tiempo de Ejecución Total: Tiempo de reloj (wall-clock time) excluyendo tiempos de espera en cola o inactividad.
  • Desglose de Hardware: Separación del tiempo dedicado a CPUs, GPUs, Unidades de Procesamiento Cuántico (QPUs) y otro hardware.
  • Definición de Tiempo de Ejecución Cuántica: Definido específicamente para la plataforma IBM Quantum como el tiempo desde la recepción de la carga útil (payload) hasta la extracción de la muestra, incluyendo la preparación del circuito y su ejecución, pero excluyendo el tiempo de transpilación clásica (que se atribuye al pre-procesamiento).
• Directrices de Envío: Se proporciona una plantilla estandarizada (Tabla 10) para la Biblioteca de Benchmarking de Optimización Cuántica (QOBLIB) para asegurar que todos los detalles necesarios (enfoque de modelado, conteo de variables, rangos de coeficientes, pasos del flujo de trabajo) sean capturados.

3. Generación de Instancias

La biblioteca contiene instancias generadas para ser "difíciles de forma primal". Para problemas donde encontrar una solución factible es trivial, las instancias se construyen mediante ingeniería inversa a partir de soluciones conocidas para garantizar la dificultad. Las instancias varían en densidad, rangos de coeficientes y conteo de variables para probar diferentes cuellos de botella algorítmicos.

Contribuciones Clave

1. El Repositorio QOBLIB: Una biblioteca de código abierto que contiene instancias de problemas, modelos (MIP/QUBO), verificadores de soluciones y resultados base.
2. El Decatlón Intratable: Un conjunto curado de diez clases de problemas que cierran la brecha entre la dificultad teórica y la relevancia práctica, seleccionados específicamente para ser desafiantes para los solvers clásicos en tamaños accesibles para el hardware cuántico de la era NISQ (Near-term Intermediate-Scale Quantum).
3. Protocolo de Benchmarking Estandarizado: Un conjunto riguroso de definiciones para métricas, medición de tiempo de ejecución (especialmente para hardware cuántico) y formatos de reporte para facilitar la comparación justa entre diferentes enfoques cuánticos y clásicos.
4. Resultados Base (Baselines): El artículo proporciona extensos resultados base clásicos utilizando solvers de vanguardia (ej. Gurobi, CPLEX, heurísticas especializadas) para establecer suelos de rendimiento. También presenta resultados cuánticos ilustrativos para tres problemas específicos utilizando diferentes algoritmos cuánticos.

Resultados y Ejemplos Ilustrativos

El artículo presenta baselines clásicos para las diez clases de problemas, demostrando que muchas instancias son actualmente insolubles hacia una optimalidad probada por los solvers clásicos en tiempos razonables, o requieren recursos computacionales significativos.

Baselines Cuánticos Ilustrativos:
Los autores proporcionan resultados preliminares para tres clases de problemas utilizando algoritmos específicos para demostrar el formato de envío y las capacidades actuales:

• Secuencias Binarias de Baja Autocorrelación (LABS):

  • Algoritmo: Optimización Cuántica de Campo de Sesgo Digitizado Contra-Adiabática (BF-DCQO).
  • Resultado: En una longitud de secuencia de $n=20$ (superando las implementaciones cuánticas previas de $n=18$), el algoritmo encontró soluciones óptimas en el dispositivo ibm marrakesh. El tiempo de ejecución promedio fue de ~61 segundos (incluyendo pre/post-procesamiento), siendo el tiempo de ejecución de la QPU de ~60.8 segundos.
  • Comparación: El escalamiento de BF-DCQO fue comparable al de QAOA con $p=12$ capas, pero requirió seis veces menos puertas de entrelazamiento. Superó a los solvers clásicos exactos (Gurobi, CPLEX) en tiempo de solución para la instancia específica probada, aunque los solvers clásicos eventualmente encontraron soluciones óptimas para instancias más pequeñas.

• Descomposición de Birkhoff Mínima:

  • Algoritmo: Algoritmo Cuántico Variacional (VQA) utilizando un circuito cuántico parametrizado para muestrear matrices de permutación.
  • Resultado: Probado en matrices doubly estocásticas de $n=4$ y $n=5$. Para $n=4$, el algoritmo encontró consistentemente descomposiciones exactas con 3–4 permutaciones, igualando o superando a los solvers aproximados clásicos (Birkhoff+, Blended FW). Para $n=5$, el rendimiento se degradó, con solo algunas instancias alcanzando descomposiciones dispersas, lo que resalta las limitaciones actuales de los enfoques variacionales en instancias más grandes y complejas.

• Conjunto Independiente Máximo (MIS):

  • Algoritmo: Solver heurístico (ABS2) en hardware GPU.
  • Resultado: Proporcionó datos de rendimiento base para grafos de hasta 4000 nodos, mostrando la brecha entre las soluciones heurísticas y los límites óptimos, sirviendo como objetivo para las heurísticas cuánticas.

Significado y Reivindicaciones

El artículo afirma que QOBLIB y el Decatlón Intratable proporcionan la infraestructura necesaria para pasar del benchmarking a nivel de componente (ej. fidelidad de puerta) hacia el benchmarking a nivel de aplicación.

• Demostrar la Ventaja Cuántica: Los autores sostienen que solo resolviendo instancias de problemas que son difíciles para las computadoras clásicas (dificultad primal) se puede demostrar una verdadera ventaja cuántica. Las instancias seleccionadas están diseñadas para ser intratables para los solvers clásicos en tamaños donde los dispositivos cuánticos de corto plazo pueden operar.
• Colaboración de la Comunidad: El trabajo se enmarca como un llamado a la acción para que la comunidad de optimización utilice estas instancias para rastrear el progreso en algoritmos, software y hardware.
• Modestia sobre las Capacidades Actuales: El artículo es modesto respecto al rendimiento cuántico actual. Reconoce que, si bien los algoritmos cuánticos muestran promesa y escalamiento (como en el caso de LABS $n=20$), aún no superan consistentemente a los mejores heurísticos clásicos en todos los ámbitos. El objetivo principal es establecer un formato estandarizado para presentar soluciones de benchmarking que asegure la comparabilidad, la reproducibilidad y la capacidad de rastrear las mejoras a lo largo del tiempo.

Los autores concluyen que este marco es esencial para verificar la corrección de los algoritmos, identificar cuellos de botella y, en última instancia, determinar si las computadoras cuánticas pueden ofrecer una ventaja práctica en la resolución de problemas de optimización combinatoria del mundo real.