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

Resumo Técnico: Pipeline Híbrido Quântico-Clássico de Ponta a Ponta para Resolução de MILPs

Definição do Problema
Problemas de Programação Linear Inteira Mista (MILP) são centrais para tomadas de decisão de alto impacto em setores como logística e gestão de cadeia de suprimentos, mas são computacionalmente desafiadores devido à sua natureza combinatória. Embora técnicas de decomposição como a Decomposição de Benders (BD) sejam amplamente utilizadas para resolver MILPs de grande escala, separando-os em um problema mestre (MP) e subproblemas (SP), elas frequentemente sofrem com uma convergência lenta. Esta convergência depende criticamente da seleção de "cortes" (restrições) informativos a serem adicionados ao problema mestre. Um trabalho anterior por Paterakis [1] propôs o uso de quantum annealing para resolver a etapa de seleção de cortes — formulada como um problema de Cobertura Mínima de Conjuntos (Minimum Set Cover) — para acelerar este processo. No entanto, o quantum annealing exige procedimentos de minor-embedding dispendiosos, que introduzem um overhead significativo ao escalar.

Metodologia
Este artigo apresenta um framework de otimização híbrido quântico-clássico de ponta a ponta que estende a abordagem de decomposição de Benders Multiple Cuts via Multiple Solutions (MCMS). A inovação central é a substituição da etapa de quantum annealing por implementações do Algoritmo de Otimização Aproximada Quântica (QAOA) baseadas em portas lógicas.

O framework opera da seguinte forma:

1. Decomposição de Benders MCMS: O algoritmo gera múltiplas soluções candidatas por iteração, resolvendo múltiplos subproblemas em paralelo para produzir um conjunto de cortes candidatos.
2. Seleção de Cortes como QUBO: Para evitar que o problema mestre se torne computacionalmente caro devido a um número excessivo de cortes, um subconjunto de cortes informativos é selecionado. Isso é formulado como um problema de Cobertura Mínima de Conjuntos, que é então mapeado para uma instância de Otimização Binária Não Restrita Quadrática (QUBO).
3. Integração do QAOA: Diferente da abordagem anterior baseada em annealing, este framework resolve o QUBO usando QAOA. O pipeline faz interface com três solvers distintos:
   • Ava da Fermioniq: Um emulador de circuitos de rede de tensores.
   • MPS-JuliQAOA: Um emulador de Estado de Produto de Matriz (MPS) de código aberto construído em Julia.
   • IBM Quantum: Execução direta em hardware quântico supercondutor (processador IBM Eagle).
4. Estudo de Caso: O framework é avaliado no Problema de Roteamento de Veículos (VRP), um problema canônico de otimização logística. O estudo utiliza um benchmark padronizado do QOptLib (20 clientes, 4 veículos) e instâncias de teste aleatórias (5 clientes) para testar a viabilidade do pipeline.

Principais Contribuições

• Extensão Baseada em Portas: O artigo estende o framework HQC-MCMS existente do quantum annealing para a computação quântica baseada em portas, permitindo a execução tanto em emuladores de rede de tensores quanto em processadores quânticos supercondutores.
• Implementação de Ponta a Ponta: Os autores demonstram com sucesso um pipeline totalmente funcional que integra sub-rotinas QAOA em um loop de decomposição de Benders clássico.
• Benchmarking Empírico: O estudo fornece uma análise comparativa do desempenho do pipeline através de diferentes backends de solver (Cbc clássico, MPS-JuliQAOA, Fermioniq e IBM Quantum) em instâncias de VRP.

Resultados
Os resultados experimentais geram vários insights críticos sobre a viabilidade atual da vantagem quântica neste contexto específico:

• Desempenho Clássico: No cenário totalmente clássico (usando Cbc para seleção de cortes), o pipeline encontra soluções viáveis para a instância de VRP de 20 clientes, com o gap de otimalidade diminuindo ao longo das iterações. A abordagem Multi-Cut (usando mais subproblemas) leva a soluções viáveis em menos iterações.
• Gargalos de Tempo de Execução: A análise do pipeline clássico revela que a etapa de seleção de cortes consome apenas uma pequena fração do tempo total da iteração. A maior parte do tempo computacional é gasto resolvendo o Problema Mestre.
• Desempenho Quântico: Quando a etapa de seleção de cortes é substituída pelo QAOA (usando MPS-JuliQAOA) em um problema de teste, o tempo de execução total aumenta significavelmente em comparação com a abordagem clássica. O estudo observa que o MPS-JuliQAOA é muito menos eficiente que o solver clássico Cbc para o problema de cobertura mínima de conjuntos nesta escala.
• Saída do QAOA: Experimentos em hardware quântico e emuladores mostram que, para as configurações testadas, a maioria das amostras do QAOA resulta em soluções inviáveis (ou seja, elas não formam uma cobertura de conjunto válida). Embora circuitos mais profundos ($p=3$) tenham gerado amostras de custo mais ótimas do que os mais rasos ($p=1$), o desempenho geral não superou os métodos clássicos.

Significância e Alegações
O artigo conclui com uma avaliação modesta do estado atual do framework. Os autores afirmam explicitamente que, para os tamanhos de problema e configurações testados, a vantagem quântica é improvável. A razão principal é dupla:

1. A etapa de seleção de cortes, que é o alvo da aceleração quântica, não é um gargalo computacional no atual pipeline MCMS clássico; a resolução do Problema Mestre domina o tempo de execução.
2. O solver clássico (Cbc) supera vastamente as implementações de QAOA para as instâncias específicas de Cobertura Mínima de Conjuntos geradas nesta escala.

Os autores enfatizam que, embora o pipeline seja tecnicamente funcional e demonstre um passo reproduzível em direção à otimização potencial por meio de computação quântica, a tradução do problema de cobertura de conjuntos para QUBO introduz um overhead substancial. Eles argumentam que pesquisas futuras devem focar em benchmarks de maior escala, onde a etapa de seleção de cortes possa se tornar um gargalo mais significativo, e onde Unidades de Processamento Quântico (QPUs) mais poderosas possam potencialmente oferecer valor. O estudo serve como uma análise empírica cautelarosa, destacando que os métodos quânticos atuais ainda não proporcionam um ganho de velocidade para esta etapa de decomposição específica em instâncias práticas de pequena a média escala.