Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

Resumen Técnico: Pipeline Híbrido Cuántico-Clásico de Extremo a Extremo para la Resolución de MILP

Planteamiento del Problema
Los problemas de Programación Lineal con Variables Enteras Mixtas (MILP) son fundamentales para la toma de decisiones de alto impacto en industrias como la logística y la gestión de la cadena de suministro, pero son computacionalmente desafiantes debido a su naturaleza combinatoria. Aunque las técnicas de descomposición como la Descomposición de Benders (BD) se utilizan ampliamente para resolver MILP de gran escala al separar el problema en un problema maestro (MP) y subproblemas (SP), estas suelen sufrir de una convergencia lenta. Esta convergencia depende críticamente de la selección de "cortes" (restricciones) informativos para añadir al problema maestro. Un trabajo previo por Paterakis [1] propuso utilizar el recocido cuántico (quantum annealing) para resolver el paso de selección de cortes —formulado como un problema de Cobertura de Conjuntos Mínima— para acelerar este proceso. Sin embargo, el recocido cuántico requiere procedimientos de minor-embedding costosos que introducen una sobrecarga significativa al escalar.

Metodología
Este artículo presenta un marco de optimización híbrido cuántico-clásico de extremo a extremo que extiende el enfoque de descomposición de Benders de Múltiples Cortes mediante Múltiples Soluciones (MCMS). La innovación central es reemplazar el paso de recocido cuántico por implementaciones del Algoritmo de Optimización Aproximada Cuántica (QAOA) basadas en puertas.

El marco opera de la siguiente manera:

1. Descomposición de Benders MCMS: El algoritmo genera múltiples soluciones candidatas por iteración, resolviendo múltiples subproblemas en paralelo para producir un grupo de cortes candidatos.
2. Selección de Cortes como QUBO: Para evitar que el problema maestro se vuelva computacionalmente costoso debido a un número excesivo de cortes, se selecciona un subconjunto de cortes informativos. Esto se formula como un problema de Cobertura de Conjuntos Mínima, el cual se mapea posteriormente a una instancia de Optimización Binaria Cuadrática sin Restricciones (QUBO).
3. Integración de QAOA: A diferencia del enfoque anterior basado en recocido, este marco resuelve el QUBO utilizando QAOA. El pipeline se conecta con tres solvers distintos:
   • Ava de Fermioniq: Un emulador de circuitos de redes de tensores.
   • MPS-JuliQAOA: Un emulador de Estado de Producto de Matriz (MPS) de código abierto construido en Julia.
   • IBM Quantum: Ejecución directa en hardware cuántico superconductor (procesador IBM Eagle).
4. Caso de Estudio: El marco se evalúa en el Problema de Rutas de Vehículos (VRP), un problema de optimización logística canónico. El estudio utiliza un benchmark estandarizado de QOptLib (20 clientes, 4 vehículos) e instancias de juguete aleatorias (5 clientes) para probar la viabilidad del pipeline.

Contribuciones Clave

• Extensión Basada en Puertas: El artículo extiende el marco HQC-MCMS existente del recocido cuántico a la computación cuántica basada en puertas, permitiendo la ejecución tanto en emuladores de redes de tensores como en procesadores cuánticos superconductores.
• Implementación de Extremo a Extremo: Los autores demuestran con éxito un pipeline totalmente funcional que integra subrutinas de QAOA dentro de un bucle de descomposición de Benders clásico.
• Benchmarking Empírico: El estudio proporciona un análisis comparativo del rendimiento del pipeline a través de diferentes backends de solver (Cbc clásico, MPS-JuliQAOA, Fermioniq e IBM Quantum) en instancias de VRP.

Resultados
Los resultados experimentales arrojan varias perspectivas críticas respecto a la viabilidad actual de la ventaja cuántica en este contexto específico:

• Rendimiento Clásico: En el entorno totalmente clásico (usando Cbc para la selección de cortes), el pipeline logra encontrar soluciones factibles para la instancia de VRP de 20 clientes, con la brecha de optimalidad disminuyendo a lo largo de las iteraciones. El enfoque de Multi-Corte (usando más subproblemas) conduce a soluciones factibles en menos iteraciones.
• Cuellos de Botella de Tiempo de Ejecución: El análisis del pipeline clásico revela que el paso de selección de cortes consume solo una pequeña fracción del tiempo total de la iteración. La mayor parte del tiempo computacional se gasta resolviendo el Problema Maestro.
• Rendimiento Cuántico: Cuando el paso de selección de cortes es reemplazado por QAOA (usando MPS-JuliQAOA) en un problema de juguete, el tiempo de ejecución total aumenta significativamente en comparación con el enfoque clásico. El estudio señala que MPS-JuliQAOA es mucho menos eficiente que el solver clásico Cbc para el problema de cobertura de conjuntos mínimos a esta escala.
• Salida de QAOA: Los experimentos en hardware cuántico y emuladores muestran que, para las configuraciones probadas, la mayoría de las muestras de QAOA resultan en soluciones infactibles (es decir, no forman una cobertura de conjunto válida). Si bien los circuitos más profundos ($p=3$) produjeron muestras de costo más óptimas que los más superficiales ($p=1$), el rendimiento general no superó a los métodos clásicos.

Significancia y Reivindicaciones
El artículo concluye con una evaluación modesta del estado actual del marco. Los autores declaran explícitamente que, para los tamaños de problema y configuraciones probadas, la ventaja cuántica es improbable. La razón principal es doble:

1. El paso de selección de cortes, que es el objetivo de la aceleración cuántica, no es un cuello de botella computacional en el actual pipeline MCMS clásico; la resolución del Problema Maestro domina el tiempo de ejecución.
2. El solver clásico (Cbc) supera ampliamente a las implementaciones de QAOA para las instancias específicas de Cobertura de Conjuntos Mínimos generadas a esta escala.

Los autores enfatizan que, si bien el pipeline es técnicamente funcional y demuestra un paso reproducible hacia la optimización potenciada por la computación cuántica, la traducción del problema de cobertura de conjuntos a QUBO introduce una sobrecarga sustancial. Argumentan que la investigación futura debe centrarse en benchmarking a mayor escala donde el paso de selección de cortes pueda convertirse en un cuello de botella más significativo, y donde las Unidades de Procesamiento Cuántico (QPUs) más potentes puedan potencialmente ofrecer valor. El estudio sirve como un análisis empírico de advertencia, resaltando que los métodos cuánticos actuales aún no proporcionan una aceleración para este paso de descomposición específico en instancias prácticas de pequeña a mediana escala.