Resumo Técnico: Um Algoritmo Híbrido de Annealing Clássico-Quântico para o Problema do Caixeiro Viajante

Declaração do Problema

O Problema do Caixeiro Viajante (TSP) é um problema fundamental de otimização NP-difícil que requer a identificação do ciclo hamiltoniano mais curto em um grafo completo ponderado. Embora solucionadores clássicos exatos (por exemplo, Concorde) possam lidar com instâncias grandes, eles frequentemente lutam com a escalabilidade em tempo polinomial. Por outro lado, abordagens quânticas, particularmente o Annealing Quântico (QA), oferecem um mecanismo alternativo promissor ao ruído térmico para escapar de mínimos locais. No entanto, os dispositivos atuais de Escala Intermediária Ruidosa (NISQ), como os annealers D-Wave, enfrentam limitações físicas severas relacionadas à contagem de qubits e conectividade topológica. Essas restrições impedem o mapeamento direto de instâncias de TSP em grande escala, que exigem conectividade densa, para Unidades de Processamento Quântico (QPUs) existentes.

Metodologia

Os autores propõem um algoritmo híbrido clássico-quântico que preenche a lacuna entre instâncias de TSP em grande escala e as capacidades atuais de hardware quântico. A abordagem sintetiza duas metodologias fundamentais: uma simulação de Annealing Quântico via Método de Monte Carlo de Integral de Caminho (PIMC) e uma estratégia de extração de subQUBO.

1. Contração de Grafos via Frequência de Arestas

A inovação central é uma técnica de contração de grafos que reduz a dimensionalidade do problema original.

• Geração de Pool: O algoritmo inicializa um pool de soluções candidatas ($P$) usando permutações aleatórias refinadas por Annealing Simulado (SA) com movimentos 2-opt.
• Identificação de Esqueleto Confiável: Em vez de analisar todo o pool, o algoritmo amostra um subconjunto ($S$) para calcular a frequência de arestas que aparecem nas soluções. Arestas que aparecem com uma frequência acima de um limiar de confiança ($\tau$) são identificadas como um "esqueleto confiável".
• Contração: Essas arestas de alta frequência são fixadas, e os nós conectados são mesclados em "super-nós". Isso transforma o grafo original $G$ em uma instância de sub-TSP significativamente menor ($G_{sub}$). A matriz de distâncias para o subproblema é recalculada para levar em conta a mesclagem lógica de caminhos (cabeça e cauda dos super-nós).

2. Loop de Otimização Híbrida

O algoritmo opera em um loop iterativo:

1. Refinamento: Heurísticas clássicas refinam o pool de soluções para melhorar a confiabilidade da frequência de arestas.
2. Amostragem e Contração: Um subconjunto de soluções é amostrado para determinar arestas fixas e contrair o grafo.
3. Resolução Quântica: O sub-TSP reduzido é resolvido usando um solucionador quântico. Nos experimentos do artigo, isso foi implementado via:
   • Simulação Clássica: Método de Monte Carlo de Integral de Caminho (PIMC) baseado no esquema de Martoňák et al., que mapeia o TSP para um sistema semelhante ao Ising com restrições, usando movimentos 2-opt como operadores de energia cinética.
   • Execução em Hardware: Execução direta em um QPU D-Wave Advantage_system 4.1.
4. Expansão e Atualização: A solução do subproblema é expandida de volta para o grafo original, re-inserindo as arestas fixas. A nova rota é adicionada ao pool, e o melhor global é atualizado se uma melhoria for encontrada.
5. Terminação: O processo se repete até que $K$ iterações consecutivas não produzam melhoria.

Contribuições Principais

• Framework Híbrido Escalável: O artigo introduz um método para contornar os limites de qubits e conectividade dos dispositivos NISQ, reduzindo instâncias grandes de TSP para tamanhos gerenciáveis pelo hardware atual (por exemplo, reduzindo uma instância de 1.002 cidades para ~185 nós).
• Integração de PIMC e SubQUBO: O trabalho combina a promessa teórica do tunelamento quântico via PIMC (efetivo para navegar em paisagens de energia complexas) com a necessidade prática de extração de subQUBO (particionamento iterativo do problema).
• Validação Empírica em Hardware: Os autores demonstraram com sucesso o algoritmo em um annealer quântico D-Wave, mostrando que a estratégia de contração permite a incorporação direta de subproblemas de TSP que, de outra forma, seriam intratáveis.

Resultados Experimentais

O algoritmo foi avaliado em instâncias do TSPLIB variando de 14 a 11.849 cidades.

• Sensibilidade aos Parâmetros:
  • Limiar ($\tau$): Reduzir $\tau$ aumenta a compressão (reduzindo o tamanho do problema), mas arrisca fixar arestas subótimas, aumentando a lacuna de otimalidade. Um limiar de $\tau=0,75$ ofereceu um equilíbrio favorável para instâncias médias.
  • Tamanho do Pool ($N_I$) e Tamanho da Amostra ($N_S$): Um tamanho de pool de 500 com um tamanho de amostra de 250 (50%) produziu os melhores resultados para instâncias médias a grandes, sugerindo que a amostragem estocástica impede que a seleção de arestas se torne excessivamente determinística.
• Desempenho vs. Baselines Clássicos:
  • Para instâncias pequenas (por exemplo, burma14, ulysses22), o algoritmo encontrou o ótimo global (0% de lacuna).
  • Para instâncias grandes (por exemplo, pr2392), o algoritmo manteve uma lacuna de otimalidade média abaixo de 4%, superando as OR-Tools do Google em vários casos (por exemplo, rl11849 alcançou uma lacuna de 7,36% versus 14,58% das OR-Tools).
• Resultados em Hardware D-Wave:
  • Quando executado no QPU D-Wave, a abordagem híbrida alcançou lacunas de otimalidade significativamente melhores do que o solucionador híbrido BQM nativo do D-Wave. Por exemplo, em ulysses22, o método proposto alcançou uma lacuna de 2,57% em comparação com 16,88% do solucionador híbrido, resolvendo subproblemas de apenas ~5 nós.
• Gargalos:
  • A fase de simulação PIMC foi identificada como o principal gargalo computacional na simulação clássica.
  • Para instâncias muito grandes (por exemplo, rl11849), a sobrecarga clássica (inicialização e refinamento do pool) tornou-se dominante, representando ~70% do tempo de execução, sugerindo que os benefícios da aceleração quântica são atualmente compensados pelos custos de pré-processamento clássico em escalas extremas.

Significado e Alegações

O artigo afirma que sua técnica híbrida mitiga efetivamente as limitações físicas dos dispositivos quânticos atuais. Ao alavancar a otimização clássica para contrair o grafo, os autores demonstram que:

1. Viabilidade: Instâncias grandes de TSP podem ser reduzidas a uma escala adequada para incorporação em annealers NISQ sem perder a integridade estrutural necessária para soluções de alta qualidade.
2. Potencial de Vantagem Quântica: Embora a simulação PIMC atual seja clássica, o framework foi projetado para ser diretamente adaptável ao hardware quântico. Os resultados sugerem que, se a etapa PIMC fosse executada em um annealer quântico, o custo computacional poderia ser drasticamente reduzido, potencialmente oferecendo acelerações exponenciais para a fase de otimização.
3. Robustez: O método é robusto em diferentes tamanhos de instância, alcançando soluções exatas para problemas pequenos e mantendo lacunas de otimalidade baixas para problemas em grande escala onde heurísticas clássicas lutam.

Os autores concluem que, embora a sobrecarga clássica permaneça um desafio para instâncias massivas, a estratégia de contração proposta traz com sucesso o TSP para o alcance da tecnologia atual de annealing quântico, validando a viabilidade de abordagens híbridas clássico-quânticas para otimização combinatória.