Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Resumen Técnico: Evaluación de la Precisión y el Rendimiento de Solucionadores Cuánticos, Clásicos e Híbridos para el Problema Max-Cut

Definición del Problema
Este estudio aborda el problema Max-Cut, que es NP-duro, y su formulación equivalente, el problema de Optimización Binaria Cuadrática sin Restricciones (QUBO). El objetivo es particionar los vértices de un grafo no dirigido ponderado en dos conjuntos disjuntos de tal manera que se maximice la suma de los pesos de las aristas que conectan los conjuntos. El artículo evalúa la capacidad de varios solucionadores para encontrar soluciones cercanas al óptimo global, reconociendo que, para instancias grandes, las soluciones exactas suelen ser computacionalmente intratables, lo que requiere heurísticas aproximadas.

Metodología y Configuración Experimental
Los autores llevaron a cabo un estudio de benchmarking exhaustivo utilizando tres conjuntos de datos distintos que comprenden 139 instancias de problemas con tamaños que van desde 100 hasta 10,000 nodos.

• Conjuntos de Datos:
  1. Billionnet y Elloumi (be): 50 instancias con $n \in \{101, 121, 151\}$. Los óptimos globales fueron computados utilizando los solucionadores exactos BiqBin y MADAM.
  2. Colección Beasley (bqp): 20 instancias con $n \in \{251, 501\}$. Los óptimos para $n=251$ se computaron exactamente; para $n=501$, se utilizaron los mejores valores conocidos de la literatura.
  3. Conjunto de datos G (G): 69 instancias con $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$. Los óptimos globales son desconocidos; se utilizaron como referencia los mejores valores conocidos de la literatura.
• Solucionadores Evaluados:
  • Recocido Cuántico (QPU): Sistema D-Wave Advantage que utiliza una característica de "recocido rápido" (fast annealing) para aislar los qubits de los efectos ambientales. Limitado a instancias con $n \le 151$.
  • Solucionador Híbrido: El "LeapHybridSampler" de D-Wave, basado en la nube, que combina iterativamente métodos clásicos (recocido simulado interrumpible, búsqueda tabú, temple paralelo) con llamadas a la QPU. Capaz de manejar todos los tamaños de instancia.
  • Recocido Simulado Clásico (SA): Se implementaron dos variantes del algoritmo de [3]:
    • SA1: Tamaño de paso agresivo, temperatura inicial 10,000 (optimizado para un tiempo de ejecución comparable al de la QPU).
    • SA2: Tamaño de paso conservador, temperatura inicial 40,000 (optimizado para la calidad de la solución).
  • Máquina de Bifurcación Simulada (SBM): El solucionador de hardware de Toshiba. Los resultados se tomaron de la literatura existente [4], ya que los autores no tuvieron acceso directo al solucionador.

Resultados Clave

• Instancias Pequeñas ($n \le 151$): El solucionador híbrido y ambas variantes de SA (SA1, SA2) alcanzaron consistentemente el óptimo global para todas las instancias. La QPU, sin embargo, produjo consistentemente soluciones significativamente alejadas del óptimo global.
• Instancias Medianas ($n = 251, 501$): El solucionador híbrido y las variantes de SA nuevamente igualaron los óptimos globales (para $n=251$) o los mejores valores conocidos (para $n=501$). La QPU no pudo ser probada debido a límites de capacidad.
• Instancias Grandes ($n \ge 800$):
  • Calidad de la Solución: El SBM y el SA2 produjeron las soluciones de mayor calidad, encontrando a menudo los mejores valores conocidos. El solucionador híbrido funcionó notablemente peor que el SCM y el SA2, mientras que el SA1 produjo las soluciones de menor calidad entre los métodos probados.
  • Tiempo Computacional: El solucionador híbrido y el SBM demostraron tiempos de computación eficientes (segundos a decenas de segundos). El SA2 requirió significativamente más tiempo (cientos de segundos, aproximadamente 1000 veces más lento que el Híbrido/SBM en algunas comparaciones) para lograr una calidad de solución superior. El SA1 tuvo un tiempo de ejecución comparable al del solucionador híbrido, pero arrojó soluciones inferiores.

Significancia y Reivindicaciones
El artículo afirma avanzar en la comprensión de la optimización asistida por computación cuántica mediante la prueba rigurosa del nuevo QPU de recocido rápido de D-Wave y su solucionador híbrido contra métodos clásicos de vanguardia en un conjunto estandarizado y públicamente disponible de instancias de Max-Cut.

Los autores concluyen que:

1. Limitaciones de la QPU: La QPU de D-Wave, incluso con recocido rápido, no logra encontrar soluciones óptimas para las instancias probadas y está limitada por el tamaño del problema ($n \le 151$).
2. Eficacia Híbrida: El solucionador híbrido de D-Wave es altamente eficiente en términos de velocidad y escalabilidad (manejando hasta 10,000 nodos) y produce soluciones cercanas al óptimo para instancias más pequeñas. Sin embargo, para las instancias más grandes, es superado en calidad de solución por el SA clásico (específicamente la variante SA2) y el SBM.
3. Competitividad Clásica: Los algoritmos de recocido simulado clásicos transparentes (específicamente la variante SA2) siguen siendo altamente competitivos, superando a menudo al solucionador híbrido de "caja negra" en calidad de solución, aunque a un costo computacional mayor.
4. Brecha de Transparencia: Los autores expresan frustración respecto a la naturaleza de "caja negra" del solucionador híbrido, señalando que la falta de conocimiento sobre su flujo de trabajo interno y la utilización de recursos cuánticos dificulta el análisis científico.

El estudio no reclama una ventaja cuántica para los solucionadores y las instancias de problemas específicos probados; más bien, destaca que para Max-Cut, las heurísticas clásicas actuales (específicamente cuando se ajustan para calidad) y el hardware especializado como el SBM pueden superar o igualar el rendimiento de los enfoques cuánticos y híbridos probados.