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

Resumo Técnico: Roteamento de Veículos Assistido por Computação Quântica via QAOA em Hardware Baseado em Portas

Definição do Problema
O Problema de Roteamento de Veículos (VRP) é um desafio fundamental de otimização combinatória NP-difícil, central para a logística e o transporte, que visa minimizar custos (distância, tempo, combustível) enquanto satisfaz restrições como a visitação de clientes, capacidade do veículo e continuidade da rota. Algoritmos clássicos têm dificuldade em encontrar soluções ótimas mesmo para instâncias de tamanho modesto devido à escala exponencial. Este trabalho aborda o desafio de mapear o VRP para computadores quânticos baseados em portas dentro do regime de Escala Intermediária com Ruído Quântico (NISQ), focando especificamente nas limitações impostas pela profundidade do circuito, conectividade de qubits e ruído de hardware.

Metodologia
Os autores propõem uma estrutura fundamentada em hardware que integra o Algoritmo de Otimização Aproximada Quântica (QAOA) com uma formulação baseada em links do VRP. A metodologia procede através das seguintes etapas:

1. Formulação do Problema: O VRP é modelado usando variáveis de aresta direcionais ($x_{i,j}$) que representam se um veículo percorre um link entre os nós $i$ e $j$. Diferente das formulações de expansão temporal ou de ordem de rota, esta abordagem evita variáveis de sequenciamento explícitas.
2. Codificação de Restrições: Restrições críticas — conservação de fluxo (cada cliente visitado exatamente uma vez), contagens de entrada/saída no depósito e eliminação de subtours — são codificadas diretamente no Hamiltoniano de custo ($H_C$) via termos de penalidade. Isso transforma o problema restrito em um problema de Otimização Binária Quadrática Não Restrita (QUBO).
3. Mapeamento de Hamiltoniano: O QUBO é mapeado para um Hamiltoniano de Ising adequado para o QAOA. O Hamiltoniano de custo consiste em termos de Pauli-Z ($Z_i$) para custos lineares e interações de Pauli-Z ($Z_i Z_j$) para penalidades quadráticas. Um Hamiltoniano de mistura padrão ($H_M = \sum X_i$) é usado para explorar o espaço de soluções.
4. Implementação do Circuito: O algoritmo é implementado no IBM Quantum System One (Eagle r3, 127 qubits). O fluxo de trabalho inclui:
   • Transpilação: Mapeamento de qubits lógicos para a topologia de rede heavy-hex física, introduzindo as portas swap necessárias.
   • Mitigação de Erros: Aplicação de desacoplamento dinâmico (para preservar a coerência em qubits ociosos) e Pauli twirling (para converter canais de ruído em assinaturas específicas).
   • Otimização Híbrida: Um otimizador clássico (COBYQA) ajusta iterativamente os parâmetros variacionais ($\gamma, \beta$) para minimizar o custo esperado $\langle \psi | H_C | \psi \rangle$.
5. Parâmetros Experimentais: O estudo investiga o impacto do escalonamento de penalidade (especificamente definindo coeficientes de penalidade como duas vezes a soma dos pesos das arestas) e da normalização de coeficientes (limitando as magnitudes dos termos de Pauli a um) na viabilidade da solução.

Principais Contribuições

• Formulação Baseada em Arestas Direcionais: Os autores desenvolvem uma formulação que incorpora a conservação de fluxo e a eliminação de subtours diretamente no Hamiltoniano de custo. Esta abordagem evita o alto overhead de qubits das formulações de expansão temporal e a complexidade fatorial das formulações de ordem de rota, tornando-a mais adequada para dispositivos de curto prazo.
• Pipeline Completo de Hardware: O trabalho executa todo o pipeline — desde a codificação do problema e mapeamento de Ising até a síntese do circuito, transpilação e execução — em hardware quântico real, em vez de depender apenas de simulações idealizadas.
• Análise Empírica de Gargalos: O estudo avalia quantitativamente como as formulações de VRP impactam a contagem de qubits e a profundidade de portas de dois qubits após a transpilação, identificando a profundidade do circuito como o principal gargalo para o roteamento restrito em arquiteturas supercondutoras atuais.
• Insights de Sensibilidade de Parâmetros: A pesquisa demonstra que a viabilidade da solução depende criticamente da seleção do parâmetro de penalidade e da normalização do coeficiente do Hamiltoniano. Especificamente, a normalização melhora significativamente a amostragem de soluções viáveis para instâncias maiores (4 e 5 nós) onde abordagens não normalizadas falham.

Resultados

• Sucesso em Pequena Escala: Para uma instância de 3 nós e 2 veículos, o QAOA identificou com sucesso a solução ótima (bit-string 111010) com alta probabilidade, satisfazendo todas as restrições, incluindo a eliminação de subtours.
• Desafios de Escalabilidade: À medida que o tamanho do problema aumentava (ex: instâncias de 4 e 5 nós), o número de portas necessárias crescia exponencialmente. Um problema de 4 nós exigiu um circuito de 14 qubits com mais de 3.000 portas, levando mais de duas horas para rodar, mas gerou soluções inviáveis. Um problema de 5 nós exigiu um circuito de 30 qubits com ~30.000 portas.
• Impacto da Normalização: Sem a normalização de coeficientes, o algoritmo falhou em identificar consistentemente rotas ótimas na região de alta probabilidade para as instâncias de 4 e 5 nós. Com a normalização e um multiplicador de penalidade de 1,5–2,0, a razão de viabilidade das 1.000 bitstrings amostradas melhorou significativamente.
• Limitações de Hardware: O estudo confirma que o ruído atual do hardware e os tempos de coerência limitados impedem a execução dos circuitos profundos de QAOA necessários para instâncias de VRP maiores. Os 10 estados amostrados no topo para o problema de 4 nós foram todos inviáveis sem um ajuste cuidadoso de parâmetros.

Significância e Alegações
O artigo reivindica significância não como uma demonstração de vantagem quântica sobre solvers clássicos para VRP de larga escala, mas como uma avaliação prática executada em hardware que esclarece as limitações atuais na era NISQ. Os autores argumentam que, embora o QAOA possa teoricamente resolver o VRP, o crescimento rápido na complexidade do circuito (especificamente na profundidade de portas de dois qubits) e o acúmulo de ruído restringem atualmente sua aplicação a instâncias muito pequenas.

O valor primário do estudo reside em fornecer insights de design concretos para a otimização quântica futura:

1. Escolha de Formulação: Formulações baseadas em arestas são atualmente mais viáveis do que codificações de expansão temporal ou de ordem de rota devido aos menores requisitos de qubits e portas.
2. Heurísticas de Parâmetros: A normalização de coeficientes e o escalonamento de penalidade específico (aprox. 2x a soma dos pesos das arestas) são essenciais para recuperar soluções viáveis em instâncias maiores.
3. Direção Metodológica: O trabalho delineia que o avanço da otimização quântica para VRP requer não apenas melhorias algorítmicas, mas também avanços de hardware (maior contagem de qubits, taxas de erro menores) e estratégias híbridas (ex: transferência de aprendizado de parâmetros, circuitos dinâmicos) para mitigar o ruído e as restrições de profundidade.

Os autores concluem que, embora a escalabilidade permaneça restrita, este trabalho estabelece um caminho prático para implementar o VRP em hardware quântico e identifica direções metodológicas específicas necessárias para o progresso futuro na otimização quântica de curto prazo.