Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Imagine um motorista de entregas que deve visitar uma lista de cidades exatamente uma vez e retornar para casa, visando percorrer a menor distância possível. Este é o problema do caixeiro viajante, um enigma clássico que está no cerne da logística, do agendamento e do design de circuitos. Embora encontrar a rota perfeita para algumas cidades seja fácil, a dificuldade explode à medida que a lista cresce; para cada nova cidade adicionada, o número de rotas possíveis multiplica-se tão rapidamente que até os supercomputadores mais rápidos podem ficar travados tentando encontrar a melhor opção. Por décadas, cientistas têm recorrido a computadores quânticos, máquinas que utilizam as estranhas regras das partículas subatômicas para processar informações, para resolver esses enigmas. No entanto, um grande obstáculo permaneceu: como traduzir o problema para uma linguagem que o computador quântico entenda sem afogar o cálculo em erros e complexidade desnecessária.

Um pesquisador da QuantScape Inc. demonstrou agora uma nova maneira de guiar um computador quântico através deste labirinto, encontrando com sucesso a rota mais curta para mapas com até dez cidades. O trabalho, que se baseia em simulações de hardware quântico em vez de máquinas físicas, introduz um método que utiliza muito menos bits quânticos — as unidades básicas de informação em um computador quântico — do que abordagens anteriores. Mais importante, mostra que um único conjunto de instruções pode se adaptar a mudanças nas condições das estradas, como o tráfego que varia ao longo do dia, sem a necessidade de ser retreinado para cada novo cenário. Os resultados sugerem que, com a codificação e as técnicas de treinamento adequadas, os computadores quânticos poderiam em breve enfrentar problemas de otimização que atualmente estão fora de alcance, desde que o hardware continue a melhorar.

O cerne do desafio reside em como o problema é escrito para a máquina. Métodos tradicionais atribuem um bit quântico separado para cada combinação possível de uma cidade e uma posição na rota. Para um mapa de dez cidades, essa abordagem requer oitenta e um bits, e força o computador a verificar e descartar constantemente rotas inválidas, desperdiçando tempo e energia em penalidades. O novo estudo utiliza uma estratégia diferente, inspirada em um sistema matemático chamado código de Lehmer, que essencialmente classifica cada rota possível pelo seu índice em uma lista. Este método requer apenas dezenove bits para dez cidades, uma redução significativa. Ao usar este código compacto, cada estado do computador quântico representa uma rota válida, eliminando a necessidade de verificações de penalidade. Para tornar a busca eficiente, os pesquisadores organizaram esses estados de modo que a inversão de um único bit no código corresponda a uma mudança lógica pequena na rota, permitindo que o computador explore o espaço de soluções de forma suave.

Para guiar o computador quântico, os pesquisadores empregaram um sistema híbrido chamado rede de Kolmogorov–Arnold quântica variacional. Pense nisso como um controlador inteligente que observa o mapa e a hora do dia, e então ajusta os seletores do circuito quântico para as posições corretas. Em vez de codificar rigidamente as configurações para cada mapa específico, este controlador aprende uma regra geral: como ajustar o circuito com base nas distâncias entre as cidades e no horário atual. Isso permite que o sistema lide com grafos dependentes do tempo, onde os tempos de viagem mudam, como uma rede elétrica ou uma rede rodoviária com trânsito de hora de pico. O controlador foi treinado com um objetivo específico: minimizar o risco de escolher uma rota longa. Em vez de apenas buscar o comprimento médio absoluto, o treinamento focou nos cenários de pior caso dentro dos principais percentuais de resultados prováveis, garantindo que o resultado final seja robusto e confiável.

O processo de treinamento em si foi rigoroso, desenhado para evitar a armadilha comum de ficar preso em um mínimo local, onde o computador se contenta com uma resposta "boa o suficiente" em vez da melhor. Os pesquisadores utilizaram uma estratégia de múltiplamente etapas que começou com buscas amplas e gradualmente estreitou o foco, combinada com uma técnica que deliberadamente sacudiu as configurações para escapar de becos sem saída. Eles também usaram um método chamado basin hopping, que atua como um leve tremor para ajudar o sistema a saltar para fora de vales rasos no cenário de busca. Ao serem testados em mapas de quatro a dez cidades, incluindo formas simétricas e redes aleatórias e irregulares, esta abordagem encontrou a rota perfeita em todos os casos para os mapas menores. Para os mapas de dez cidades, que são significamente mais difíceis, o método encontrou a rota ótima em 112 de 120 tentativas, sendo que as falhas restantes ficaram a apenas um por cento da distância perfeita.

Crucialmente, o estudo descartou várias ideias alternativas que poderiam parecer promissoras. Os pesquisadores testaram uma abordagem mais simples que usa apenas dez bits, um para cada cidade, para rastrear a posição do motorista passo a passo. Este método falhou completamente para mapas com seis ou mais cidades porque não conseguia representar as relações complexas entre as paradas sucessivas. Eles também compararam seus resultados contra um algoritmo clássico padrão conhecido como 2-opt, que melhora uma rota trocando dois segmentos. Embora o 2-opt seja eficaz, o circuito quântico forneceu um ponto de partida muito melhor, e a combinação dos dois superou qualquer um dos métodos isoladamente. O estudo confirmou que o sucesso veio da forma específica como o problema foi codificado e do treinamento sofisticado do controlador, e não apenas do poder do próprio circuito quântico.

As descobertas também destacam a eficiência do método em relação à medição. Em um computador quântico real, ler a resposta exige repetir o processo muitas vezes para obter um sinal claro. As simulações mostraram que, mesmo com apenas cem leituras, o sistema poderia identificar a melhor rota de forma confiável. Isso sugere que, quando computadores quânticos físicos com bits suficientes estiverem disponíveis, este método poderá entregar resultados rapidamente sem precisar de milhões de repetições. Os pesquisadores observaram que, embora o trabalho atual tenha sido realizado em um computador clássico simulando comportamento quântico, as técnicas foram desenhadas para funcionar em hardware real. Os próximos passos envolvem testar o sistema sob as condições ruidosas de máquinas reais e escalá-lo para mapas maiores, onde o número de rotas possíveis é vasto demais para ser verificado manualmente.

Este trabalho representa um passo significativo para tornar a otimização quântica prática. Ao resolver o problema da codificação e criar um controlador que se generaliza através de diferentes mapas e tempos, os pesquisadores mostraram um caminho para que máquinas possam resolver problemas complexos de roteamento de forma eficiente. A capacidade de lidar com mudanças dependentes do tempo com um único conjunto de parâmetros é particularmente promissora para aplicações do mundo real, onde as condições nunca são estáticas. Embora a jornada para um otimizador quântico totalmente funcional ainda esteja em curso, este estudo fornece um plano claro de como treinar essas máquinas para encontrar o caminho mais curto através de um mundo complexo.