⚛️ quantum physics

Solving The Travelling Salesman Problem Using A Single Qubit

Este artigo apresenta um algoritmo quântico eficiente em recursos que resolve o Problema do Caixeiro Viajante para até nove cidades usando um único qubit ao alavancar o paralelismo quântico e métodos de controle ótimo baseados em uma abordagem de Braquistócrona quântica, demonstrando precisão superior e potencial aceleração polinomial sobre os métodos quânticos e clássicos existentes.

Autores originais: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Publicado 2026-01-28

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Grande Problema: O Viajante Cansado

Imagine que você é um vendedor ambulante com um mapa de cidades. Seu trabalho é visitar cada cidade exatamente uma vez e retornar para casa, mas você quer fazer isso usando a menor distância possível.

Este é o famoso Problema do Caixeiro Viajante (TSP). É um enigma clássico que se torna incrivelmente difícil muito rapidamente. Se você tem 4 cidades, é fácil. Se tem 10, é gerenciável. Mas se tiver 20, o número de rotas possíveis é tão enorme que mesmo os supercomputadores mais rápidos do mundo levariam mais tempo do que a idade do universo para verificar todas elas, uma por uma.

A Velha Forma Quântica: A Abordagem das "Muitas Chaves"

Normalmente, quando os cientistas tentam resolver isso em um computador quântico, eles tratam o problema como uma fechadura gigante com muitos pinos. Eles precisam de um "pino" separado (um qubit) para cada cidade e cada conexão possível.

O Problema: Para resolver um problema com apenas 9 ou 10 cidades, os métodos quânticos existentes precisam de centenas ou até milhares de qubits.
A Realidade: Os computadores quânticos atuais são ruidosos e frágeis. Eles têm dificuldade em manter tantos qubits trabalhando juntos e, muitas vezes, falham em encontrar a resposta perfeita, mesmo para mapas pequenos.

A Nova Ideia: O Qubit "Único e Maravilhoso"

Este artigo propõe uma nova maneira radical de resolver o TSP usando apenas um único qubit (a unidade básica de informação quântica). Pense neste único qubit não como um pequeno interruptor, mas como um pião mágico que pode apontar para qualquer direção no espaço 3D.

Aqui está como eles fazem isso funcionar, passo a passo:

1. O Mapa é um Globo (A Esfera de Bloch)

Em vez de desenhar as cidades em um pedaço de papel plano, os autores as mapeiam na superfície de uma esfera (como um globo terrestre).

As Cidades: As cidades "reais" são colocadas ao longo da linha do equador deste globo.
As Distâncias: A distância entre duas cidades não é medida em milhas, mas pelo quanto você precisa girar o pião para ir de um ponto de cidade a outro.
O Objetivo: O vendedor precisa girar o pião de cidade em cidade, visitando cada ponto do equador uma vez e retornando para casa, enquanto minimiza o "esforço de giro" total.

2. A Superestrada da Superposição

Na forma antiga, você verifica a Rota A, depois a Rota B, depois a Rota C, uma por uma.
Neste novo método, os autores usam a superposição quântica. Imagine que o pião é um viajante mágico que pode estar em vários lugares ao mesmo tempo.

Em vez de percorrer um caminho, o "pião" explora simultaneamente todas as rotas possíveis ao mesmo tempo.
É como enviar mil exploradores por mil estradas diferentes simultaneamente, mas todos são o mesmo explorador, apenas existindo em uma "superposição" de todos os caminhos.

3. O Atalho "Brachistochrone"

O artigo utiliza um conceito da física chamado problema da Brachistochrone. Historicamente, este problema pergunta: "Qual é o caminho mais rápido para uma bola rolar entre dois pontos?"

Os autores transformaram o TSP em uma versão deste problema. Eles tratam a busca pela rota como uma corrida contra o tempo.
Eles utilizam uma técnica chamada Controle Ótimo (pense nisso como um piloto automático muito inteligente) para empurrar e rotacionar suavemente o qubit único.
O piloto automático ajusta o "giro" para que os caminhos que são longos demais se cancelem mutuamente (como fones de ouvido com cancelamento de ruído), enquanto o caminho mais curto é amplificado e se destaca.

4. A Verificação Final

Depois que o qubit "viajou" por todas as rotas ao mesmo tempo, os cientistas medem a posição final do pião.

Eles não olham para cada caminho individualmente. Eles olham para o exato fim da jornada.
Ao analisar o estado final, eles conseguem trabalhar de trás para frente para reconstruir a rota vencedora.
É como observar um mágico realizar um truque onde ele embaralha um baralho de cartas e, ao olhar para a última carta, ele consegue dizer qual era a ordem exata de todo o baralho.

Os Resultados: O Que Eles Descobriram?

A equipe executou simulações de computador para testar este método de "Um Único Qubit".

O Teste: Eles resolveram enigmas de TSP com 4 a 9 cidades.
O Sucesso: Para mais de 90% dos problemas, o método deles encontrou a rota perfeita e mais curta.
A Margem de Segurança: Nos raros casos em que não obtiveram a resposta perfeita, eles ainda conseguiram uma aproximação muito boa (cerca de 90% tão boa quanto a melhor possível).
A Eficiência: Eles fizeram tudo isso usando apenas um qubit, enquanto outros métodos precisariam de dezenas ou centenas.

A Conclusão

Este artigo não afirma que resolverá o TSP para um milhão de cidades amanhã. Em vez disso, ele prova um conceito poderoso: Você não precisa de um computador quântico massivo para resolver problemas complexos de roteamento.

Ao tratar o problema como um enigma de geometria em uma única esfera giratória e usar o poder de "estar em muitos lugares ao mesmo tempo", eles mostraram que um único qubit pode navegar eficientemente por labirintos complexos. É uma nova forma de otimização quântica com baixo uso de recursos que poderia, eventualmente, ser construída em qualquer plataforma quântica capaz de girar um qubit com precisão.

Resumo Técnico: Resolvendo o Problema do Caixeiro Viajante Usando um Único Qubit

Enunciado do Problema
O Problema do Caixeiro Viajante (TSP - Travelling Salesman Problem) é um problema fundamental de otimização combinatória NP-difícil que requer a identificação da rota mais curta possível que visite um conjunto de cidades exatamente uma vez e retorne à origem. Embora existam algoritmos clássicos, as soluções exatas escalam exponencialmente com o número de cidades, e métodos heurísticos não garantem a otimalidade. As abordagens quânticas existentes, como as que utilizam Otimização Binária Não Restrita Quadrática (QUBO) mapeada para Hamiltonianos de Ising ou circuitos de estimativa de fase, são intensivas em recursos. Elas tipicamente exigem um grande número de qubits (por exemplo, milhares de qubits físicos para um problema de 1 de 10 cidades) e frequentemente sofrem com baixas probabilidades de sucesso em hardware ruidoso atual.

Metodologia
Os autores propõem um algoritmo que mapeia um TSP arbitrário em um único qubit, aproveitando o princípio do paralelismo quântico em vez do emaranhamento. A metodologia central envolve três estágios principais:

Mapeamento para um Problema de Brachistócrona Discreta:
O TSP é primeiro reformulado como um problema de Brachistócrona discreta finita. Nesta analogia clássica, as cidades são representadas como pontos em um plano 2D, e as rotas são funções lineares por partes. O objetivo é minimizar um funcional de tempo $Q$ , que corresponde à distância total de viagem. O problema é restrito de modo que o caminho deve retornar à cidade inicial, codificado por um segmento linear adicional para um ponto final $F$ .
Codificação na Esfera de Bloch:
O problema da Brachistócrona discreta é mapeado na geometria da esfera de Bloch de um único qubit.

Representação de Estado: As cidades ( $c_i$ ) são representadas por estados quânticos $|P_{ii}\rangle$ localizados no equador da esfera de Bloch.
Codificação de Distância: As distâncias relativas entre as cidades são codificadas como distâncias geométricas (geodésicas) na esfera. Estados intermediários $|P_{ij}\rangle$ são colocados em curvas geodésicas conectando os estados equatoriais a um polo $P_0$ . A distância angular entre os estados corresponde à distância euclidiana entre as cidades.
Trajetória: O movimento entre as cidades é realizado via operadores de rotação ( $U^u$ e $U^d$ ). Um "passo" de uma cidade $i$ para uma cidade $j$ envolve uma rotação "para cima" do equador para um estado intermediário $|P_{ij}\rangle$ (mais próximo do polo) seguido por uma rotação "para baixo" para o estado equatorial $|P_{jj}\rangle$ .

Otimização Quântica via Superposição:
Ao contrário de uma abordagem de força bruta que percorre caminhos sequencialmente, o algoritmo proposto utiliza a superposição quântica para percorrer múltiplos caminhos simultaneamente.

Criação de Superposição: O sistema é inicializado em um estado correspondente à cidade de partida. Uma série de operadores de rotação ajustáveis cria um estado de superposição em cada camada do gráfico de roteamento, efetivamente explorando todos os camheres válidos e inválidos de uma só vez.
Otimização: O algoritmo emprega métodos de controle ótimo, especificamente a Aproximação Estocástica de Perturbação Simultânea (SPSA), para ajustar os operadores de rotação.
Função Objetivo: Enquanto uma abordagem quântica de força bruta poderia minimizar um funcional de tempo $T$ , a abordagem baseada em superposição minimiza a função de custo clássica $D$ (distância total). Isso é necessário porque a superposição inclui caminhos "classicamente proibidos" que não formam ciclos hamiltonianos válidos. A otimização busca maximizar a população do ciclo hamiltoniano válido no estado final.
Medição e Pós-processamento: O algoritmo conclui com uma medição projetiva do estado penúltimo. Através da tomografia de estado quântico, a distribuição de população é analisada para identificar o caminho dominante, que corresponde à rota ótima do TSP.

Resultos Principais
Os autores apresentam simulações numéricas resolvendo instâncias de TSP com 4 a 9 cidades usando um único qubit.

Precisão: Para os tamanhos de problema testados, o algoritmo obteve soluções exatas (razão de aproximação $\sim 1$ ) para mais de 90% das instâncias do problema.
Aproximação: Nos casos em que soluções exatas não foram encontradas, o algoritmo alcançou altas razões de aproximação ( $\sim 0,90$ ).
Eficiência de Recursos: O método requer apenas um único qubit, um contraste gritante com os algoritmos quânticos existentes que exigem centenas ou milhares de qubits para problemas semelhantes.
Agnosticismo de Plataforma: O algoritmo foi projetado para ser implementável em qualquer plataforma quântica capaz de rotações de qubit arbitrárias de alta fidelidade e tomografia de estado, incluindo qubits supercondutores, íons aprisionados, centros de vacância de nitrogênio e átomos de Rydberg.

Significância e Alegações
O artigo afirma que esta abordagem oferece uma alternativa mais eficiente em recursos e precisa em relação aos algoritmos quânticos existentes para instâncias de pequeno a médio porte do TSP. Ao utilizar o princípio da superposição em um único qubit, o método evita a necessidade de emaranhamento em larga escala e contagens extensas de qubits, abordando um gargalo primário no hardware quântico atual.

Os autores discutem um potencial aumento de velocidade polinomial sobre os algoritmos clássicos, sugerindo que o paralelismo quântico inerente à superposição de caminhos pode fornecer uma vantagem prática tanto em tempo quanto em precisão. O trabalho posiciona o TSP não apenas como um problema de roteamento, mas como um caso específico de um problema de Brachistócrona restrito solúvel via controle quântico, abrindo um caminho para a otimização quântica escalável em dispositivos de curto prazo (near-term).