A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle
APL Quantum · 01.12.2026 · 3 (4)
DOI: 10.1063/5.0335410 ↗Kurz gefasst
Fachartikel in der Zeitschrift APL Quantum, online erschienen am 18.11.2026. Verfasst von Alexander Johannes Stasik und 1 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Research Council of Norway.
Abstract (Originalsprache)
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(nlogn) qubits, while a naive implementation requires O(n3log2n) 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.
Förderung
- Research Council of Norway
Zitieren
APA
Stasik, A. J., & Fuchs, F. G. (2026). A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle. APL Quantum, 3(4). https://doi.org/10.1063/5.0335410
Vancouver
Stasik AJ, Fuchs FG. A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle. APL Quantum. 2026;3(4). doi:10.1063/5.0335410
BibTeX
@article{Stasik2026,
author = {Stasik, Alexander Johannes and Fuchs, Franz Georg},
title = {A quantum encoding of traveling salesperson tours via route generation, cost phases, and a reversible valid-permutation oracle},
journal = {APL Quantum},
year = {2026},
volume = {3},
number = {4},
doi = {10.1063/5.0335410}
}
EUVIMED