Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Resumen Técnico: Enrutamiento de Vehículos Asistido por Computación Cuántica mediante QAOA en Hardware de Puertas Lógicas

Definición del Problema
El Problema de Enrutamiento de Vehículos (VRP) es un desafío fundamental de optimización combinatoria NP-duro, central en la logística y el transporte, que busca minimizar costos (distancia, tiempo, combustible) mientras se satisfacen restricciones como la visita a clientes, la capacidad de los vehículos y la continuidad de las rutas. Los algoritmos clásicos tienen dificultades para encontrar soluciones óptimas incluso para instancias de tamaño modesto debido al escalamiento exponencial. Este trabajo aborda el desafío de mapear el VRP en computadoras cuánticas de puertas lógicas dentro del régimen de la Tecnología Cuántica de Escala Intermedia con Ruido (NISQ), enfocándose específicamente en las limitaciones impuestas por la profundidad del circuito, la conectividad de los cúbits y el ruido del hardware.

Metodología
Los autores proponen un marco basado en el hardware que integra el Algoritmo de Optimización Aproximada Cuántica (QAOA) con una formulación basada en enlaces para el VRP. La metodología procede a través de las siguientes etapas:

1. Formulación del Problema: El VRP se modela utilizando variables de arco direccional ($x_{i,j}$) que representan si un vehículo atraviesa un enlace entre los nodos $i$ y $j$. A diferencia de las formulaciones de expansión temporal o de orden de ruta, este enfoque evita las variables de secuenciación explícitas.
2. Codificación de Restricciones: Las restricciones críticas —conservación de flujo (cada cliente es visitado exactamente una vez), conteos de entrada/salida del depósito y eliminación de subtours— se codifican directamente en el Hamiltoniano de costo ($H_C$) mediante términos de penalización. Esto transforma el problema restringido en un problema de Optimización Binaria Cuadrática Sin Restricciones (QUBO).
3. Mapeo del Hamiltoniano: El QUBO se mapea a un Hamiltoniano de Ising adecuado para QAOA. El Hamiltoniano de costo consiste en términos de Pauli-Z ($Z_i$) para costos lineales e interacciones de Pauli-Z ($Z_i Z_j$) para penalizaciones cuadráticas. Se utiliza un Hamiltoniano de mezcla estándar ($H_M = \sum X_i$) para explorar el espacio de soluciones.
4. Implementación del Circuito: El algoritmo se implementa en el IBM Quantum System One (Eagle r3, 127 cúbits). El flujo de trabajo incluye:
   • Transpilación: Mapeo de cúbits lógicos a la topología de red de hexágono pesado (heavy-hex lattice) física, introduciendo las puertas SWAP necesarias.
   • Mitigación de Errores: Aplicación de desacoplamiento dinámico (para preservar la coherencia en cúbits inactivos) y Pauli twirling (para convertir los canales de ruido en firmas específicas).
   • Optimización Híbrida: Un optimizador clásico (COBYLA) ajusta iterativamente los parámetros variacionales ($\gamma, \beta$) para minimizar el costo esperado $\langle \psi | H_C | \psi \rangle$.
5. Parámetros Experimentales: El estudio investiga el impacto del escalamiento de la penalización (específicamente estableciendo los coeficientes de penalización como el doble de la suma de los pesos de los arcos) y la normalización de coeficientes (limitando las magnitudes de los términos de Pauli a uno) sobre la factibilidad de la solución.

Contribuciones Clave

• Formulación Basada en Arcos Direccionales: Los autores desarrollan una formulación que incorpora la conservación de flujo y la eliminación de subtours directamente en el Hamiltoniano de costo. Este enfoque evita la alta sobrecarga de cúbits de las formulaciones de expansión temporal y la complejidad factorial de las formulaciones de orden de ruta, lo que lo hace más adecuado para dispositivos de corto plazo.
• Pipeline Completo de Hardware: El trabajo ejecuta todo el proceso —desde la codificación del problema y el mapeo de Ising hasta la síntesis del circuito, transpilación y ejecución— en hardware cuántico real, en lugar de depender únicamente de simulaciones idealizadas.
• Análisis Empírico de Cuellos de Botella: El estudio evalúa cuantitativamente cómo las formulaciones de VRP impactan el número de cúbits y la profundidad de las puertas de dos cúbits tras la transpilación, identificando la profundidad del circuito como el principal cuello de botella para el enrutamiento restringido en arquitecturas superconductoras actuales.
• Perspectivas de Sensibilidad de Parámetros: La investigación demuestra que la factibilidad de la solución depende críticamente de la selección de los parámetros de penalización y la normalización de los coeficientes del Hamiltoniano. Específicamente, la normalización mejora significativamente el muestreo de soluciones factibles para instancias más grandes (4 y 5 nodos) donde los enfoques no normalizados fallan.

Resultados

• Éxito a Pequeña Escala: Para una instancia de 3 nodos y 2 vehículos, el QAOA identificó con éxito la solución óptima (cadena de bits 111010) con alta probabilidad, satisfaciendo todas las restricciones, incluida la eliminación de subtours.
• Desafíos de Escalabilidad: A medida que el tamaño del problema aumentó (por ejemplo, instancias de 4 y 5 nodos), el número de puertas requeridas creció exponencialmente. Un problema de 4 nodos requirió un circuito de 14 cúbits con más de 3,000 puertas, tardando más de dos horas en ejecutarse, pero produjo soluciones infactibles. Un problema de 5 nodos requirió un circuito de 30 cúbits con aproximadamente 30,000 puertas.
• Impacto de la Normalización: Sin la normalización de coeficientes, el algoritmo no logró identificar consistentemente rutas óptimas en la región de alta probabilidad para las instancias de 4 y 5 nodos. Con la normalización y un multiplicador de penalización de 1.5–2.0, la ratio de factibilidad de las 1,000 cadenas de bits muestreadas mejoró significativamente.
• Limitaciones de Hardware: El estudio confirma que el ruido del hardware actual y los tiempos de coherencia limitados impiden la ejecución de circuitos QAOA profundos requeridos para instancias de VRP más grandes. Los 10 estados muestreados principales para el problema de 4 nodos fueron todos infactibles sin un ajuste cuidadoso de los parámetros.

Significancia y Reivindicaciones
El artículo reclama su significancia no como una demostración de ventaja cuántica sobre los resolvedores clásicos para VRP a gran escala, sino como una evaluación práctica ejecutada en hardware que clarifica las limitaciones actuales en la era NISQ. Los autores argumentan que, si bien el QAOA puede resolver teóricamente el VRP, el rápido crecimiento en la complejidad del circuito (específicamente la profundidad de las puertas de dos cúbits) y la acumulación de ruido restringen actualmente su aplicación a instancias muy pequeñas.

El valor principal del estudio radica en proporcionar perspectivas de diseño concretas para la optimización cuántica futura:

1. Elección de la Formulación: Las formulaciones basadas en arcos son actualmente más factibles que las codificaciones de expansión temporal o de orden de ruta debido a los menores requisitos de cúbits y puertas en el hardware disponible.
2. Heurísticas de Parámetros: La normalización de coeficientes y la escala de penalización específica (aproximadamente 2 veces la suma de los pesos de los arcos) son esenciales para recuperar soluciones factibles en instancias más grandes.
3. Dirección Metodológica: El trabajo establece que avanzar en la optimización cuántica para VRP requiere no solo mejoras algorítmicas, sino también avances en el hardware (mayor número de cúbits, menores tasas de error) y estrategias híbridas (por ejemplo, transferencia de aprendizaje de parámetros, circuitos dinámicos) para mitigar las restricciones de ruido y profundidad.

Los autores concluyen que, aunque la escalabilidad sigue siendo limitada, este trabajo establece una vía práctica para implementar VRP en hardware cuántico e identifica las direcciones metodológicas específicas necesarias para el progreso futuro en la optimización cuántica de corto plazo.