A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle

For a traveling salesperson problem of n cities, we present a compact quantum encoding based on a time-register representation of tours. A candidate route is represented as a sequence of n − 1 city labels over discrete time steps, with one fixed start city and the remaining cities encoded in binary registers. We describe three ingredients of the construction: uniform route generation over the route register, a reversible validity oracle, and a phase oracle that encodes the total tour cost. The validity oracle checks both that the non-start city labels form a permutation and, for incomplete graphs, that every directed edge used by the route exists. The cost oracle then accumulates the start-edge, intermediate-transition, and return-edge costs into a tour-dependent phase for valid routes. This yields a coherent superposition of candidate routes with feasibility and tour-length information embedded directly in the quantum state. The complete construction uses O(n⁡log⁡n) qubits, while a naive implementation requires O(n3⁡log2n) CX gates and On3[log2n+log2(1/ϵ)]T gates, where ϵ denotes the target approximation precision. The encoding is compatible with amplitude amplification or spectral filtering techniques, such as the quantum singular value transform or Grover’s algorithm. However, due to the exponentially small fraction of valid tours, the overall complexity remains exponential even when combined with amplitude amplification.

Authors

Institutions

Publication Details

Journal
APL Quantum
Published
2026-11-18
DOI
https://doi.org/10.1063/5.0335410
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle

A. Stasik, Franz Georg Fuchs
2 links
APL Quantum
Quantum Computing Algorithms and Architecture
article

A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle

A. Stasik, Franz Georg Fuchs
article en

Abstract

For a traveling salesperson problem of n cities, we present a compact quantum encoding based on a time-register representation of tours. A candidate route is represented as a sequence of n − 1 city labels over discrete time steps, with one fixed start city and the remaining cities encoded in binary registers. We describe three ingredients of the construction: uniform route generation over the route register, a reversible validity oracle, and a phase oracle that encodes the total tour cost. The validity oracle checks both that the non-start city labels form a permutation and, for incomplete graphs, that every directed edge used by the route exists. The cost oracle then accumulates the start-edge, intermediate-transition, and return-edge costs into a tour-dependent phase for valid routes. This yields a coherent superposition of candidate routes with feasibility and tour-length information embedded directly in the quantum state. The complete construction uses O(n⁡log⁡n) qubits, while a naive implementation requires O(n3⁡log2n) CX gates and On3[log2n+log2(1/ϵ)]T gates, where ϵ denotes the target approximation precision. The encoding is compatible with amplitude amplification or spectral filtering techniques, such as the quantum singular value transform or Grover’s algorithm. However, due to the exponentially small fraction of valid tours, the overall complexity remains exponential even when combined with amplitude amplification.

APL QuantumVol. 3(4)
SINTEF (NO), University of Oslo (NO), SINTEF Digital (NO), Norwegian University of Life Sciences (NO)
Norges Forskningsråd
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon