A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

Este artigo apresenta uma codificação quântica compacta do Problema do Caixeiro Viajante que utiliza um registro de tempo para gerar rotas e oráculos reversíveis para marcar permutações válidas e codificar custos em fases, permitindo uma superposição coerente de candidatos com complexidade de qubits polinomial, embora a complexidade geral permaneça exponencial devido à escassez de soluções válidas.

O essencial

Imagine que você é um carteiro em uma cidade grande e precisa entregar cartas em todas as casas, começando e terminando na sua própria casa, mas querendo fazer o caminho mais curto possível. Esse é o famoso Problema do Caixeiro Viajante.

O desafio é que, à medida que a cidade cresce, o número de rotas possíveis explode de forma assustadora. Para 100 casas, o número de combinações é maior do que o número de átomos no universo. Computadores comuns demorariam bilhões de anos para testar todas as opções.

Os autores deste artigo propuseram uma nova maneira de usar computadores quânticos para lidar com esse problema. Em vez de tentar "adivinhar" a resposta, eles criaram um sistema de triagem quântica. Vamos explicar como funciona usando analogias do dia a dia:

1. A "Fita de Vídeo" de Todas as Rotas (Codificação)

Imagine que você tem uma fita de vídeo com várias faixas de tempo. Em cada faixa, você coloca o nome de uma casa que o carteiro deve visitar.

• O Truque Quântico: Em vez de gravar uma única rota, o computador quântico usa um superpoder chamado "superposição". Ele grava todas as rotas possíveis ao mesmo tempo, como se estivesse assistindo a milhões de filmes diferentes simultaneamente.
• A Economia de Espaço: Para fazer isso de forma eficiente, eles usam um sistema de endereçamento inteligente (como um código de barras) que ocupa pouco espaço na memória do computador (qubits), mesmo para cidades grandes.

2. O "Fiscal de Trânsito" (Oráculo de Validade)

Agora que temos todas as rotas gravadas, a maioria delas é um caos: o carteiro vai para a mesma casa duas vezes ou esquece de visitar uma.

• O Fiscal: O artigo descreve um "robô fiscal" quântico (chamado de Oráculo de Permutação Válida). Ele passa por todas as rotas ao mesmo tempo e dá um "selo de aprovação" apenas para aquelas que visitam cada casa exatamente uma vez.
• O Problema: A maioria das rotas (quase 99,999...%) é rejeitada. É como tentar encontrar uma agulha em um palheiro, mas o palheiro é o tamanho de um planeta.

3. O "Medidor de Distância" (Oráculo de Custo)

Para as rotas que passaram no teste do fiscal, o computador precisa saber qual é a mais curta.

• O Medidor: Outro robô (o Oráculo de Custo) calcula a distância total de cada rota aprovada. Em vez de escrever o número, ele muda a "cor" ou o "ritmo" (fase) da rota na fita de vídeo.
  • Rotas longas ficam com um ritmo lento.
  • Rotas curtas ficam com um ritmo rápido.
• Isso cria uma "sinfonia" onde as melhores rotas têm um som distinto.

4. O Grande Desafio: Encontrar a Agulha

Aqui está a parte honesta e importante do artigo:
Embora os computadores quânticos sejam ótimos para criar essa "sinfonia" de todas as rotas, encontrar a rota perfeita ainda é muito difícil.

• Como a quantidade de rotas válidas (que visitam todas as casas uma vez) é infinitamente menor do que o total de tentativas, mesmo usando técnicas avançadas de "amplificação" (que tentam aumentar o volume das rotas boas), o computador ainda precisa de um tempo exponencial para encontrar a resposta.
• A Analogia: É como tentar achar a única pessoa que sabe cantar a nota perfeita em um estádio lotado de 1 bilhão de pessoas. O computador quântico consegue ouvir a voz de todos ao mesmo tempo, mas como a pessoa certa é tão rara, ainda leva muito tempo para isolá-la.

Por que isso é importante?

O objetivo deste artigo não é dizer que temos uma máquina mágica que resolve o problema do Caixeiro Viajante em segundos. O objetivo é:

1. Criar um "Rascunho" Claro: Eles mostraram uma maneira compacta e organizada de representar o problema no computador quântico.
2. Preparar o Terreno: Essa estrutura serve como uma base sólida para que, no futuro, cientistas possam adicionar "turbo" (algoritmos mais inteligentes) para filtrar as respostas.
3. Transparência: Eles admitiram que, com a tecnologia atual, o problema ainda é exponencialmente difícil, mas a "moldura" que criaram é eficiente e pode ser usada em simulações pequenas hoje.

Em resumo: Os autores construíram uma "máquina de triagem" quântica muito elegante que consegue ver todas as rotas de uma vez e marcar as válidas e as curtas. No entanto, como as rotas válidas são extremamente raras, a máquina ainda precisa de muito tempo para encontrar a campeã. É um passo importante na construção de futuros computadores quânticos mais poderosos, mesmo que não resolva o problema mágicamente agora.

Resumo técnico

Título: Uma Codificação Quântica de Rotas do Problema do Caixeiro Viajante via Geração de Rotas, Fases de Custo e um Oráculo de Permutação Válida

Autores: Alexander Johannes Stasik e Franz Georg Fuchs
Data: 24 de março de 2026

---

1. O Problema

O Problema do Caixeiro Viajante (TSP) é um problema clássico de otimização combinatória onde o objetivo é encontrar o ciclo hamiltoniano de menor custo em um grafo ponderado com $n$ cidades, visitando cada cidade exatamente uma vez e retornando à cidade de partida.

• Desafio: A complexidade do problema reside no crescimento fatorial do número de rotas válidas em relação ao número de cidades ($n!$).
• Abordagens Existentes: Métodos baseados em codificações de arestas (variáveis binárias para arestas do grafo) são comuns em modelos QUBO e annealing quântico. No entanto, o artigo propõe uma abordagem baseada em rotas (sequências temporais de cidades) dentro de um modelo de circuito quântico.

2. Metodologia e Construção do Circuito

Os autores propõem uma codificação compacta que representa uma rota candidata como uma sequência ordenada de rótulos de cidades ao longo de passos de tempo discretos.

A. Representação do Estado (Codificação)

• Registro de Rota: Utiliza um registro quântico dividido em $T = n-1$ passos de tempo (já que a cidade inicial e final, $n-1$, é fixa).
• Qubits Necessários: Cada passo de tempo armazena um rótulo de cidade de $\{0, \dots, n-2\}$. O número de qubits por passo é $b = \lceil \log_2(n-1) \rceil$.
• Total de Qubits: A codificação requer $O(n \log_2 n)$ qubits.
• Superposição Inicial: Aplica-se portas Hadamard a todos os qubits do registro de rota para criar uma superposição uniforme de todas as possíveis sequências de rótulos (incluindo rotas inválidas).

B. Oráculo de Validade (Valid-Permutation Oracle)

Este componente distingue permutações válidas das atribuições inválidas.

• Lógica: Uma rota é válida se o multiconjunto dos rótulos nas posições de tempo for exatamente $\{0, \dots, n-2\}$ (cada cidade não-inicial aparece exatamente uma vez).
• Implementação:
  1. Introduz-se um qubit ancilla para cada rótulo de cidade não-inicial.
  2. Para cada rótulo $i$, calcula-se a paridade de sua ocorrência em toda a rota usando comparações de igualdade e portas controladas.
  3. Se a paridade for ímpar (ocorrência única) para todos os rótulos, um qubit de bandeira final é marcado como "válido".
• Complexidade: Utiliza portas MCX (Multi-Controlled X) e requer $O(n^2 \log n)$ portas CX e T.

C. Oráculo de Custo (Cost Oracle)

Este componente codifica o custo total da rota na fase do estado quântico.

• Função de Custo: $L(x) = C_{0,x_1} + \sum C_{x_t, x_{t+1}} + C_{x_T, 0}$.
• Mecanismo: Aplica uma rotação de fase $e^{iL(x)/\Lambda}$ ao estado, onde $\Lambda$ é um limite superior do custo máximo.
• Implementação: Decomposto em três partes: aresta inicial, transições intermediárias e aresta de retorno.
• Complexidade: A implementação "ingênua" (naive) requer $O(n^3)$ operações controladas, resultando em $O(n^3 \log n)$ portas CX e $O(n^3(\log n + \log(1/\epsilon)))$ portas T. A profundidade do circuito é $O(n^2 \log n)$ devido à execução paralela de passos de tempo disjuntos.

3. Resultados Principais

• Codificação Compacta: O método consegue representar o espaço de busca do TSP usando $O(n \log n)$ qubits, o que é eficiente em termos de espaço.
• Superposição Coerente: O estado final é uma superposição coerente de todas as rotas candidatas, onde a viabilidade (válida/inválida) e o custo (fase) estão embutidos diretamente no estado quântico.
• Limitação de Complexidade:
  • A fração de rotas válidas em relação ao espaço total de superposição é extremamente pequena: $\frac{(n-1)!}{(n-1)^{n-1}} \approx \sqrt{2\pi(n-1)} e^{-(n-1)}$.
  • Devido a essa fração exponencialmente pequena, mesmo o uso de Amplificação de Amplitude (como o algoritmo de Grover) para filtrar as rotas válidas resulta em uma complexidade total ainda exponencial em $n$.
  • O oráculo de custo ingênuo tem alta complexidade de portas ($O(n^3)$), o que limita a viabilidade prática em hardware atual.

4. Contribuições Chave

1. Abordagem Baseada em Tempo: Propõe uma codificação direta de rotas como sequências temporais, tornando a estrutura de permutação explícita, em contraste com as codificações baseadas em arestas comuns em annealing quântico.
2. Construção de Oráculos Reversíveis: Detalha a construção de um oráculo de validade que marca permutações e um oráculo de custo que acumula fases, permitindo a integração com técnicas de filtragem espectral.
3. Análise de Recursos: Fornece uma análise rigorosa do número de qubits, profundidade do circuito e contagem de portas (CX e T), servindo como uma linha de base clara para simulações em pequena escala.
4. Compatibilidade: O estado preparado é compatível com técnicas avançadas como QSVT (Quantum Singular Value Transform) e filtragem espectral, embora a barreira da fração de sucesso válida permaneça.

5. Significado e Conclusão

O artigo não reivindica uma aceleração quântica polinomial prática para o TSP. Pelo contrário, seu objetivo é representacional e pedagógico:

• Fornece uma "linha de base" clara para codificar o TSP em circuitos quânticos reversíveis.
• Demonstra que, embora a representação quântica seja compacta em qubits, a escassez exponencial de soluções válidas no espaço de Hilbert impede que algoritmos de amplificação padrão superem a complexidade exponencial clássica neste esquema específico.
• Trabalho Futuro: Os autores sugerem que o foco deve ser o desenvolvimento de oráculos de custo mais eficientes (usando aritmética reversível ou técnicas de block-encoding) e a busca por codificações alternativas que aumentem a fração de estados válidos no espaço de busca, ou o uso de métodos espectrais para enviesar o estado para rotas de baixo custo sem projeção explícita de viabilidade.

Em resumo, o trabalho oferece uma ferramenta fundamental para entender como mapear problemas de permutação complexos em hardware quântico, destacando tanto o potencial de compactação de informação quanto os desafios fundamentais de escalabilidade impostos pela natureza combinatória do problema.