Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

Resumen Técnico: Problema de Rutas de Vehículos Cuántico con Inicialización Inteligente y Codificación de Subtours

Definición del Problema
El Problema de Rutas de Vehículos (VRP) es un desafío de optimización combinatoria cuyo objetivo es determinar rutas óptimas para una flota de vehículos que deben visitar un conjunto de destinos, partiendo y regresando a un depósito central. El problema es NP-Hard, lo que requiere un número exponencial de operaciones para obtener soluciones exactas clásicas, lo cual limita la escalabilidad de los resolvedores exactos para instancias grandes. Aunque existen métodos heurísticos, estos suelen arrojar resultados subóptimos. El artículo se centra en resolver el VRP utilizando el Algoritmo de Optimización Aproximada Cuántica (QAOA) en dispositivos cuánticos digitales. Un desafío específico al codificar el VRP para resolvedores cuánticos es la restricción de "eliminación de subtours" (Ecuación 1f), la cual evita ciclos cerrados que no incluyan el depósito. Las formulaciones tradicionales de QUBO (Optimización Binaria Cuadrática Sin Restricciones) a menudo excluyen esta restricción o requieren un número exponencial de variables binarias adicionales de holgura para imponerla, lo que conduce a requisitos excesivos de cúbits y a un procesamiento posterior complejo.

Metodología
Los autores proponen un marco basado en QAOA que aborda dos cuellos de botella primarios en la optimización cuántica: la mala inicialización de parámetros en paisajes mal condicionados y la alta sobrecarga de cúbits requerida para las restricciones de desigualdad.

1. Estrategia de Inicialización Inteligente:
   Para mitigar el fenómeno de "mesetas estériles" (barren plateaus) —donde los gradientes se desvanecen exponencialmente con el tamaño del sistema, dificultando el entrenamiento variacional— los autores introducen una estrategia de inicialización determinista. En lugar de una selección aleatoria de parámetros, realizan una búsqueda de cuadrícula (grid search) sobre un subconjunto específico del espacio de parámetros. Evalúan la energía esperada $\langle\psi(\gamma, \beta)| H_C |\psi(\gamma, \beta)\rangle$ para configuraciones donde $\gamma_k = \beta_k = \alpha_d$, con $\alpha_d = d\pi/D$. La configuración que arroja la energía más baja se selecciona como el punto de partida para el optimizador clásico. Este enfoque tiene como objetivo comenzar el entrenamiento cerca de un estado de baja energía, evitando las regiones de gradientes evanescentes.

2. Codificación de la Restricción de Subtour sin Variables de Holgura:
   Basándose en el trabajo de Montañez-Barrera et al. (2024), los autores integran la restricción de eliminación de subtours directamente en el Hamiltoniano QUBO sin introducir cúbits adicionales. Aproximan la restricción de desigualdad utilizando una expansión de Taylor de segundo orden de una función exponencial. Específicamente, la restricción de desigualdad $h_S(x) \geq 0$ se transforma en un problema de optimización relajado utilizando la aproximación $e^{-h(x)} \approx e - e \cdot h(x) + \frac{e}{2}h(x)^2$. Esto resulta en una función objetivo QUBO modificada que contiene términos lineales y cuadráticos para las restricciones de subtour, gobernados por hiperparámetros $\lambda_1$ y $\lambda_2$, junto con el multiplicador de Lagrange estándar $\lambda$ para otras restricciones.

Contribuciones Clave

• Inicialización Novedosa: Una estrategia de inicialización de parámetros que mejora la probabilidad de convergencia y limita el efecto de las mesetas estériles bajo la inicialización aleatoria, demostrando ser efectiva incluso a medida que aumentan el número de cúbits.
• Integración Directa de Subtours: Un método de codificación que incorpora las restricciones de eliminación de subtours directamente en el bucle de optimización de QAOA. Esto elimina la necesidad de variables de holgura adicionales y la sobrecarga exponencial en el recuento de cúbits, permitiendo una solución cuántica de "extremo a extremo".
• Ajuste de Hiperparámetros: El uso de Optuna para identificar las configuraciones óptimas de hiperparámetros ($\lambda, \lambda_1, \lambda_2$) que dan forma a la codificación QUBO, asegurando que el estado fundamental del Hamiltoniano corresponda a la solución factible óptima.

Resultados
Los autores validaron su enfoque en simuladores sin ruido para instancias de VRP con $N$ nodos que van desde 3 a 5 y un número variable de vehículos ($K$).

• Rendimiento de la Inicialización: Las comparaciones contra la inicialización aleatoria mostraron que la estrategia de inicialización inteligente mantiene probabilidades de éxito consistentes a través de diferentes clases de problemas, mientras que la inicialización aleatoria sufre significativamente a medida que $N$ aumenta debido a las mesetas estériles.
• Satisfacción de Restricciones: La codificación propuesta resolvió con éxito instancias hasta $N=5$ con alta probabilidad. Para $N=3$, la restricción de subtour se satisface naturalmente mediante otras restricciones, pero la codificación sigue siendo válida. Para $N=4$ y $N=5$, las probabilidades de salida de QAOA se concentraron nítidamente en las soluciones teóricamente correctas, aislando eficazmente las rutas óptimas de las configuraciones infactibles o subóptimas.
• Eficiencia de Cúbits: La codificación propuesta reduce el tamaño del registro de cúbits en $O(2^N)$ en comparación con las formulaciones estándar de variables de holgura, ya que evita el crecimiento exponencial de variables necesarias para las restricciones de desigualdad.

Significancia y Reivindicaciones
El artículo afirma ser el primero en lograr una inicialización de parámetros de QAOA efectiva e independiente del tamaño del problema específicamente para el contexto de VRP. Además, sostiene ser el primero en adoptar la codificación directa de desigualdades de subtour en la rutina de optimización de QAOA sin cúbits auxiliares ni procesamiento posterior clásico.

Los autores posicionan estas contribuciones como un camino para resolver eficazmente instancias de VRP utilizando soluciones basadas en computación cuántica. Argumentan que, al aprovechar una codificación de problemas eficiente en espacio y una mejor inicialización, la optimización cuántica puede convertirse en una alternativa o complemento viable a los métodos de rutas clásicos, particularmente a medida que los computadores cuánticos tolerantes a fallos estén disponibles. Sin embargo, los autores mantienen la modestia respecto a las limitaciones actuales: los experimentos se restringieron a instancias pequeñas ($N \leq 5$) en simuladores sin ruido, y la conversión a QUBO sigue siendo altamente sensible a la selección de hiperparámetros, lo que actualmente requiere un proceso de búsqueda. Sugieren que el trabajo futuro debería centrarse en determinar configuraciones de hiperparámetros generales basadas en invariantes del problema (por ejemplo, funciones de $N$ y $K$) para agilizar aún más el enfoque.