A Hybrid Classical-Quantum Annealing Algorithm for the TSP

Este artículo propone un algoritmo híbrido de recocido clásico-cuántico para el Problema del Viajante que utiliza la contracción de grafos para reducir la dimensionalidad del problema, permitiendo una solución eficiente en dispositivos cuánticos actuales como el recocedor D-Wave, con un rendimiento validado mediante simulación clásica y hardware cuántico.

Lo esencial

Imagina que eres un agente de viajes tratando de planificar el viaje por carretera perfecto para un cliente. Tienes una lista de 1.000 ciudades que desea visitar y necesitas determinar la única ruta más corta que pase por cada ciudad exactamente una vez y los devuelva a casa. Este es el famoso Problema del Viajante de Comercio (TSP).

El problema es que, a medida que crece el número de ciudades, el número de rutas posibles explota tan rápido que incluso las supercomputadoras más potentes del mundo pueden quedarse atascadas intentando encontrar el camino absolutamente mejor. Es como intentar encontrar un grano de arena específico en una playa que sigue haciéndose más grande cada segundo.

Este artículo propone una estrategia ingeniosa de "trabajo en equipo" para resolver este rompecabezas combinando lo mejor de dos mundos: ordenadores clásicos (el tipo que usamos hoy) y ordenadores cuánticos (el tipo futurista y experimental).

Así es como funciona su método, explicado mediante analogías simples:

1. El Problema: Demasiadas Opciones

Piensa en el TSP como una bola gigante y enredada de ovillo de lana. Si intentas desenredar todo de una vez, es imposible. Los ordenadores cuánticos actuales son como manos pequeñas y delicadas; son increíblemente potentes pero solo pueden sostener un pequeño trozo de lana a la vez. No pueden manejar toda la bola de 1.000 ciudades porque no tienen suficientes "dedos" (qubits) ni las conexiones adecuadas para agarrarlo todo.

2. La Solución: La "Columna Vertebral Confiable"

El ingrediente secreto de los autores es una técnica llamada Contracción de Grafos. Imagina que tienes un grupo de 500 agentes de viajes diferentes, cada uno bosquejando su propia idea de una buena ruta para las 1.000 ciudades.

• El Pool: Reúnes todos estos 500 bosquejos.
• El Patrón: Observas de cerca los mapas. Notas que en casi todos y cada uno de los bosquejos, los agentes coinciden en que la Ciudad A debe estar conectada con la Ciudad B, y la Ciudad C con la Ciudad D. Estas son las conexiones "confiables".
• El Atajo: En lugar de tratar cada ciudad como una parada separada, tomas esas conexiones acordadas y las "pegas" juntas. Conviertes una larga cadena de ciudades (A-B-C-D) en una sola "mega-ciudad" de tamaño superlativo.

Al hacer esto, no estás cambiando el destino; solo estás simplificando el mapa. Podrías convertir un problema de 1.000 ciudades en un problema de 50 ciudades. Esto es la contracción.

3. El Paso Cuántico: La "Brújula Mágica"

Ahora que has reducido el mapa a un tamaño manejable (digamos, 50 ciudades), entregas este rompecabezas más pequeño al Recocido Cuántico (como la máquina D-Wave que utilizaron).

• Los Ordenadores Clásicos suelen resolver estos rompecabezas probando un camino, quedándose atascados y probando otro (como un ratón en un laberinto).
• Los Ordenadores Cuánticos utilizan un fenómeno llamado "túnel cuántico". Imagina que el laberinto tiene valles profundos donde el ratón se queda atascado. Un ordenador cuántico es como un fantasma que puede simplemente tunelar a través de las paredes del valle para encontrar la salida al otro lado.

Los autores utilizaron una simulación de esta capacidad cuántica de "fantasma" (llamada Monte Carlo de Integral de Camino) para encontrar la mejor ruta para el mapa pequeño y contraído. Debido a que el mapa ahora es lo suficientemente pequeño, el ordenador cuántico puede resolverlo realmente de manera eficiente.

4. El Resultado: Volviendo a Ensamblarlo

Una vez que el ordenador cuántico encuentra la mejor ruta para las "mega-ciudades", el algoritmo las despegar, expandiendo el camino de nuevo hasta las 1.000 ciudades originales. Debido a que las partes "pegadas" eran las conexiones más fiables encontradas desde el principio, la ruta final está muy cerca de la solución perfecta.

¿Qué Descubrieron?

El equipo probó esto con datos de viajes del mundo real (de una biblioteca llamada TSPLIB):

• Viajes Pequeños: Para grupos pequeños de ciudades, su método encontró la ruta perfecta cada vez.
• Viajes Grandes: Para viajes masivos (como 1.000+ ciudades), lograron reducir el problema a un tamaño que un ordenador cuántico podía manejar. Las rutas resultantes fueron muy buenas (generalmente dentro de un 2-4% de la distancia perfecta), lo cual es una gran mejora sobre intentar resolver todo el problema con un ordenador cuántico solo.
• La Compensación: Descubrieron que si pegaban demasiadas ciudades juntas (siendo demasiado agresivos), corrían el riesgo de cometer un error. Si pegaban muy pocas, el ordenador cuántico seguía abrumado. Tuvieron que encontrar un umbral "Ricitos de Oro" para obtener los mejores resultados.

La Conclusión

El artículo no afirma que esto resuelva cada problema de viaje instantáneamente. En cambio, muestra una forma práctica de utilizar los ordenadores cuánticos limitados de hoy. Al usar un ordenador clásico para realizar el trabajo pesado de "simplificar" el mapa primero, pueden entregar un rompecabezas manejable a la máquina cuántica, que luego utiliza sus poderes especiales de "tunelización" para encontrar una respuesta casi perfecta. Es un equipo híbrido donde el ordenador clásico actúa como el organizador, y el ordenador cuántico actúa como el solucionador experto para la parte final y más complicada.

Resumen técnico

Resumen Técnico: Un Algoritmo Híbrido de Recocido Clásico-Cuántico para el Problema del Viajante de Comercio

Enunciado del Problema

El Problema del Viajante de Comercio (TSP) es un problema fundamental de optimización NP-duro que requiere la identificación del ciclo hamiltoniano más corto en un grafo completo ponderado. Aunque los solucionadores clásicos exactos (por ejemplo, Concorde) pueden manejar instancias grandes, a menudo luchan con la escalabilidad en tiempo polinomial. Por el contrario, los enfoques cuánticos, particularmente el Recocido Cuántico (QA), ofrecen un mecanismo alternativo prometedor al ruido térmico para escapar de mínimos locales. Sin embargo, los dispositivos cuánticos actuales de escala intermedia con ruido (NISQ), como los recocedores D-Wave, enfrentan limitaciones físicas severas en cuanto a la cantidad de qubits y la conectividad topológica. Estas restricciones impiden el mapeo directo de instancias de TSP a gran escala, que requieren conectividad densa, hacia las Unidades de Procesamiento Cuántico (QPUs) existentes.

Metodología

Los autores proponen un algoritmo híbrido clásico-cuántico que cierra la brecha entre las instancias de TSP a gran escala y las capacidades actuales del hardware cuántico. El enfoque sintetiza dos metodologías fundamentales: una simulación de Recocido Cuántico mediante Monte Carlo de Integral de Camino (PIMC) y una estrategia de extracción de subQUBO.

1. Contracción de Grafos mediante Frecuencia de Aristas

La innovación central es una técnica de contracción de grafos que reduce la dimensionalidad del problema original.

• Generación de Pool: El algoritmo inicializa un pool de soluciones candidatas ($P$) utilizando permutaciones aleatorias refinadas por Recocido Simulado (SA) con movimientos 2-opt.
• Identificación de la Columna Vertebral Confiable: En lugar de analizar todo el pool, el algoritmo muestrea un subconjunto ($S$) para calcular la frecuencia de las aristas que aparecen en las soluciones. Las aristas que aparecen con una frecuencia por encima de un umbral de confianza ($\tau$) se identifican como una "columna vertebral confiable".
• Contracción: Estas aristas de alta frecuencia se fijan y los nodos conectados se fusionan en "super-nodos". Esto transforma el grafo original $G$ en una instancia de sub-TSP significativamente más pequeña ($G_{sub}$). La matriz de distancias para el subproblema se recalcula para tener en cuenta la fusión lógica de caminos (cabeza y cola de los super-nodos).

2. Bucle de Optimización Híbrida

El algoritmo opera en un bucle iterativo:

1. Refinamiento: Heurísticas clásicas refinan el pool de soluciones para mejorar la fiabilidad de la frecuencia de las aristas.
2. Muestreo y Contracción: Se muestrea un subconjunto de soluciones para determinar las aristas fijas y contraer el grafo.
3. Resolución Cuántica: El sub-TSP reducido se resuelve utilizando un solucionador cuántico. En los experimentos del artículo, esto se implementó mediante:
   • Simulación Clásica: Monte Carlo de Integral de Camino (PIMC) basado en el esquema de Martoňák et al., que mapea el TSP a un sistema tipo Ising restringido utilizando movimientos 2-opt como operadores de energía cinética.
   • Ejecución en Hardware: Ejecución directa en una QPU D-Wave Advantage_system 4.1.
4. Expansión y Actualización: La solución del subproblema se expande de nuevo al grafo original reinsertando las aristas fijas. La nueva ruta se añade al pool y se actualiza la mejor global si se encuentra una mejora.
5. Terminación: El proceso se repite hasta que $K$ iteraciones consecutivas no producen ninguna mejora.

Contribuciones Clave

• Marco Híbrido Escalable: El artículo introduce un método para eludir los límites de qubits y conectividad de los dispositivos NISQ reduciendo las instancias grandes de TSP a tamaños manejables por el hardware actual (por ejemplo, reducir una instancia de 1.002 ciudades a ~185 nodos).
• Integración de PIMC y SubQUBO: El trabajo combina la promesa teórica del túnel cuántico PIMC (eficaz para navegar paisajes energéticos complejos) con la necesidad práctica de la extracción de subQUBO (particionamiento iterativo del problema).
• Validación Empírica en Hardware: Los autores demostraron exitosamente el algoritmo en un recocedor cuántico D-Wave, mostrando que la estrategia de contracción permite la inserción directa de subproblemas de TSP que de otro modo serían intratables.

Resultados Experimentales

El algoritmo se evaluó en instancias de TSPLIB que van desde 14 hasta 11.849 ciudades.

• Sensibilidad a Parámetros:
  • Umbral ($\tau$): Reducir $\tau$ aumenta la compresión (reduciendo el tamaño del problema) pero arriesga fijar aristas subóptimas, aumentando la brecha de optimalidad. Un umbral de $\tau=0.75$ ofreció un equilibrio favorable para instancias medianas.
  • Tamaño del Pool ($N_I$) y Tamaño de Muestra ($N_S$): Un tamaño de pool de 500 con un tamaño de muestra de 250 (50%) produjo los mejores resultados para instancias de tamaño mediano a grande, lo que sugiere que el muestreo estocástico evita que la selección de aristas se vuelva demasiado determinista.
• Rendimiento frente a Líneas Base Clásicas:
  • Para instancias pequeñas (por ejemplo, burma14, ulysses22), el algoritmo encontró el óptimo global (0% de brecha).
  • Para instancias grandes (por ejemplo, pr2392), el algoritmo mantuvo una brecha de optimalidad promedio inferior al 4%, superando a OR-Tools de Google en varios casos (por ejemplo, rl11849 logró una brecha del 7.36% frente al 14.58% de OR-Tools).
• Resultados en Hardware D-Wave:
  • Al ejecutarse en la QPU de D-Wave, el enfoque híbrido logró brechas de optimalidad significativamente mejores que el solucionador híbrido BQM nativo de D-Wave. Por ejemplo, en ulysses22, el método propuesto logró una brecha del 2.57% en comparación con el 16.88% del solucionador híbrido, resolviendo subproblemas de solo ~5 nodos.
• Cuellos de Botella:
  • La fase de simulación PIMC se identificó como el principal cuello de botella computacional en la simulación clásica.
  • Para instancias muy grandes (por ejemplo, rl11849), la sobrecarga clásica (inicialización y refinamiento del pool) se volvió dominante, representando ~70% del tiempo de ejecución, lo que sugiere que los beneficios de la aceleración cuántica están actualmente compensados por los costos de preprocesamiento clásico a escalas extremas.

Significado y Afirmaciones

El artículo afirma que su técnica híbrida mitiga eficazmente las limitaciones físicas de los dispositivos cuánticos actuales. Al aprovechar la optimización clásica para contraer el grafo, los autores demuestran que:

1. Viabilidad: Las instancias grandes de TSP pueden reducirse a una escala adecuada para su inserción en recocedores NISQ sin perder la integridad estructural requerida para soluciones de alta calidad.
2. Potencial de Ventaja Cuántica: Aunque la simulación PIMC actual es clásica, el marco está diseñado para ser directamente adaptable al hardware cuántico. Los resultados sugieren que si el paso PIMC se ejecutara en un recocedor cuántico, el costo computacional podría reducirse drásticamente, ofreciendo potencialmente aceleraciones exponenciales para la fase de optimización.
3. Robustez: El método es robusto a través de tamaños de instancia variables, logrando soluciones exactas para problemas pequeños y manteniendo brechas de optimalidad bajas para problemas a gran escala donde las heurísticas clásicas luchan.

Los autores concluyen que, aunque la sobrecarga clásica sigue siendo un desafío para instancias masivas, la estrategia de contracción propuesta lleva con éxito el TSP al alcance de la tecnología actual de recocido cuántico, validando la viabilidad de los enfoques híbridos clásico-cuánticos para la optimización combinatoria.