Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing

Título: Mejora de la Viabilidad en el Algoritmo Cuántico Aproximado de Optimización (QAOA) para la Ruta de Vehículos mediante Inicialización Consciente de Restricciones y Mezcla Híbrida XY-X

1. Planteamiento del Problema

El Problema de Enrutamiento de Vehículos (VRP) es un problema central en logística y transporte, conocido por ser NP-duro. Aunque el Algoritmo Cuántico Aproximado de Optimización (QAOA) es un marco prometedor para la optimización combinatoria cuántica, su aplicación al VRP enfrenta un desafío crítico de viabilidad (feasibility):

• Espacio de búsqueda ineficiente: En las formulaciones estándar de QAOA, el estado inicial es una superposición uniforme sobre todos los $2^n$ estados de la base computacional. Para el VRP, la fracción de soluciones factibles dentro de este espacio es extremadamente pequeña (a menudo insignificante).
• Destrucción de estructura: El mezclador estándar (basado en el operador Pauli-X) permite inversiones de bits independientes. Esto puede destruir estructuras parciales que ya satisfacen restricciones locales importantes (como el equilibrio de grados en los nodos), transfiriendo masa de probabilidad desde estados factibles a infeasibles durante la evolución del algoritmo.
• Limitaciones de los mezcladores existentes: Alternativas como el mezclador XY preservan el peso de Hamming (número de unos), lo que mantiene ciertas restricciones, pero impide la exploración hacia sectores de peso de Hamming diferentes, atrapando al algoritmo en subespacios donde no residen las soluciones óptimas.

2. Metodología Propuesta

Los autores proponen un marco de QAOA consciente de las restricciones que aborda el cuello de botella de la viabilidad desde dos ángulos complementarios:

A. Inicialización Consciente de Restricciones (Constraint-Aware Initialization)

• En lugar de iniciar con una superposición uniforme sobre todo el espacio de búsqueda, se construye un estado inicial restringido.
• Se identifican un subconjunto de restricciones locales simples y estructuralmente informativas (principalmente restricciones de "uno-caliente" o de equilibrio de grado en nodos específicos).
• El estado inicial se prepara como una superposición uniforme solo sobre los estados de base que satisfacen estas restricciones locales.
• Objetivo: No es preparar una superposición sobre soluciones totalmente factibles (lo cual sería costoso de computar), sino reducir drásticamente el tamaño del espacio de superposición inicial y aumentar la masa de probabilidad en estados que ya cumplen con la estructura local clave.

B. Mezclador Híbrido XY-X (Hybrid XY-X Mixer)

• Se introduce un Hamiltoniano de mezclador híbrido que combina dos componentes:
  1. Término XY: Actúa sobre pares de qubits asociados a las restricciones locales incorporadas en la inicialización. Este término preserva la estructura de restricción (ej. mantiene el peso de Hamming en esos pares), evitando destruir la información útil ya codificada.
  2. Término X (Pauli-X): Actúa sobre los qubits no restringidos o grados de libertad globales. Este término permite cambios en el peso de Hamming total y explora configuraciones fuera de los subespacios de peso fijo.
• Fórmula: $H_{M}^{hyb} = \sum (X_i X_j + Y_i Y_j) + \lambda \sum_{k \in K} X_k$, donde $\lambda$ es un parámetro de ponderación que controla el equilibrio entre la preservación de la estructura y la exploración.

3. Contribuciones Clave

1. Marco de Viabilidad: Desarrollo de una estrategia que prioriza la viabilidad estructural en lugar de depender únicamente de penalizaciones en la función de costo para guiar al algoritmo hacia soluciones factibles.
2. Diseño de Mezclador Híbrido: Propuesta de un mezclador que equilibra la preservación de restricciones locales (vía XY) con la flexibilidad de exploración global (vía X), superando las limitaciones de los mezcladores puros (X o XY).
3. Evaluación Exhaustiva: Validación del método bajo tres regímenes experimentales progresivamente realistas:
   • Simulación ideal de vector de estado (sin ruido).
   • Muestreo finito (con ruido estadístico de medición).
   • Muestreo finito ruidoso (incorporando modelos de error de puertas y lectura inspirados en hardware real).

4. Resultados

Los experimentos se realizaron en una instancia pequeña de VRP (3 nodos, 2 vehículos) comparando el método propuesto contra el QAOA estándar:

• Regímenes Ideal y de Muestreo Finito:

  • El método propuesto logró consistentemente una mayor probabilidad de estado óptimo (hasta un 61.76% frente al 50.86% del estándar en el régimen ideal).
  • Se observó una menor brecha de energía esperada (expected energy gap), indicando que la distribución de muestreo final se concentra más en soluciones de bajo costo, no solo en el óptimo exacto.
  • El parámetro $\lambda$ mostró un comportamiento no monótono: valores intermedios (alrededor de 0.7 u 0.8) ofrecieron el mejor equilibrio entre preservación de estructura y exploración.

• Regímenes Ruidosos:

  • La ventaja relativa disminuyó en presencia de ruido de puertas y lectura (modelado con fidelidades de nivel de laboratorio óptimo), pero el método propuesto siguió superando al QAOA estándar.
  • Esto sugiere que, aunque la complejidad del circuito híbrido lo hace más susceptible al ruido, la mejora algorítmica en la inicialización y el mezclado sigue siendo beneficiosa incluso en condiciones de hardware actuales optimistas.

5. Significado y Conclusión

• Viabilidad como Prioridad Algorítmica: El trabajo demuestra que para problemas de enrutamiento, tratar la viabilidad como un detalle secundario de modelado (solo mediante penalizaciones) es insuficiente. La estructura de las restricciones debe integrarse directamente en la arquitectura del algoritmo (inicialización y mezclador).
• Compromiso entre Complejidad y Rendimiento: Existe un compromiso (trade-off) entre la sofisticación del diseño del ansatz (que mejora la viabilidad teórica) y la vulnerabilidad al ruido del hardware.
• Perspectiva Futura: La mejora significativa observada en simulaciones ideales y la ventaja persistente (aunque atenuada) en entornos ruidosos indican que, a medida que la fidelidad de los qubits mejore, los beneficios de estos mezcladores estructurados serán aún más pronunciados.
• Aplicabilidad: Este enfoque sienta las bases para escalar QAOA a problemas de transporte más grandes y realistas, donde la densidad de soluciones factibles es extremadamente baja, requiriendo una guía más inteligente del espacio de búsqueda que la exploración aleatoria uniforme.

En resumen, el artículo presenta una mejora sustancial en la eficiencia del QAOA para VRP al reducir el espacio de búsqueda ineficiente desde el inicio y proteger la estructura de la solución durante la evolución cuántica, ofreciendo una ruta viable hacia aplicaciones prácticas en logística con hardware cuántico de escala intermedia ruidosa (NISQ).