A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation Oracle
- URL: http://arxiv.org/abs/2603.21283v2
- Date: Thu, 26 Mar 2026 10:04:09 GMT
- Title: A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation Oracle
- Abstract summary: We present a compact quantum encoding of the Traveling Salesperson Problem (TSP) based on a time-register representation of tours.<n>We describe three ingredients of the construction: uniform route generation over the route register, a reversible oracle for marking valid tours, and a phase oracle that encodes the total tour cost.
- Score: 45.88028371034407
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a compact quantum encoding of the Traveling Salesperson Problem (TSP) based on a time-register representation of tours. A candidate route is represented as a sequence of $n$ 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 oracle for marking valid tours, and a phase oracle that encodes the total tour cost. The validity oracle distinguishes permutations of the non-start cities from invalid assignments, while the cost oracle accumulates the contribution of the start edge, intermediate transitions, and return edge into a tour-dependent phase. This yields a coherent superposition of candidate routes with feasibility and tour-length information embedded directly in the quantum state. The number of qubits required is $\Order{n\log_2(n)}$ and the circuit depth scales quadratically in $n$. The encoding is compatible with amplitude amplification or spectral filtering techniques such as the quantum singular value transform (QSVT) 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.
Related papers
- The Gain-Engineered Transmon [68.89136228609398]
We introduce and experimentally realize a noise-biased qubit in a standard transmon-readout resonator circuit.<n>Our results open a path towards using this system as a simple building-block for hardware-efficient quantum error detection and correction schemes.
arXiv Detail & Related papers (2026-08-26T17:00:42Z) - Quantum Circuits for Quantum Spatial Search on $d$-Dimensional Lattices [2.2336243882030025]
We propose an explicit quantum circuit for quantum spatial search based on discrete-time quantum walks on $d$-dimensional lattices.<n>We verify that the proposed circuits reproduce the theoretical dynamics on two- and three-dimensional periodic lattices.
arXiv Detail & Related papers (2026-07-21T14:51:25Z) - Efficient Quantum Circuits for Coherent Conversion Between General First- and Second-Quantized Many-Body Representations [1.6089851562703383]
We construct an explicit $Q$, with inverse $Qdagger$, that maps a first-quantized state to its fixed-$N$ occupation-number form.<n>The conversion is symmetry-agnostic at the input yet fully resolved at the output, and it applies uniformly to bosonic, fermionic, and parastatistical sectors.
arXiv Detail & Related papers (2026-06-23T18:00:04Z) - Multi-Qubit Dyadic Phase Fixing for Fault-Tolerant Quantum Compilation [1.729914033210882]
We present Dyadic Phase Fixing (DPF), a general multi-qubit synthesis tool that extends phase kickback to general quantum circuits.<n>DPF uses numerical unitary synthesis to greedily extract dyadic angle rotations from any input circuit.<n>Our end-to-end workflow up to 70% reduction in $T$-count compared to textttgridsynth and up to 60% compared to Repeat-Until-Success synthesis on a diverse set of benchmarks.
arXiv Detail & Related papers (2026-06-03T20:07:30Z) - Barriers to Universal Reasoning With Transformers (And How to Overcome Them) [46.59247939156339]
Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness.<n>We use recent theoretical frameworks for Transformer length generalization and find that -- under standard positional encodings and a finite alphabet -- Transformers with CoT cannot solve problems beyond $TC0$.<n>We attain a length-generalizable simulation of Turing machines where the CoT trace length is linear in the simulated runtime up to a constant.
arXiv Detail & Related papers (2026-04-28T16:10:37Z) - Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce $T$-count [1.6195650245658724]
Local synthesis approaches are commonly used to compile large circuits by decomposing them into substructures.<n>We propose textscQ-PreSyn, a strategy that, given a set of local edits preserving circuit equivalence, uses a RL agent to identify effective sequences.<n> Experimental results show up to a $20%$ reduction in $T$-count on circuits with up to 25 qubits.
arXiv Detail & Related papers (2026-01-27T15:58:05Z) - Quantum-Inspired Algorithms beyond Unitary Circuits: the Laplace Transform [0.0]
Quantum-inspired algorithms can deliver substantial speedups over classical state-of-the-art methods.<n>We introduce a tensor-network approach to compute the discrete Laplace transform, a non-unitary, aperiodic transform.<n>We demonstrate simulations up to $N=230$ input data points, with up to $260$ output data points, and quantify how bond dimension controls runtime and accuracy.
arXiv Detail & Related papers (2026-01-25T07:19:56Z) - Accelerating Transpilation in Quantum Machine Learning with Haiqu's Rivet-transpiler [45.88028371034407]
We develop the Rivet transpiler, which accelerates transpilation by reusing previously transpiled circuits.<n>We demonstrate up to 600% improvement in transpilation time for quantum layerwise learning.
arXiv Detail & Related papers (2025-08-29T06:00:29Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
arXiv Detail & Related papers (2024-08-15T17:09:08Z) - Complexity for one-dimensional discrete time quantum walk circuits [0.0]
We compute the complexity for the mixed state density operator derived from a one-dimensional discrete-time quantum walk (DTQW)<n>The complexity is computed using a two-qubit quantum circuit obtained from canonically purifying the mixed state.
arXiv Detail & Related papers (2023-07-25T12:25:03Z) - Universal qudit gate synthesis for transmons [44.22241766275732]
We design a superconducting qudit-based quantum processor.
We propose a universal gate set featuring a two-qudit cross-resonance entangling gate.
We numerically demonstrate the synthesis of $rm SU(16)$ gates for noisy quantum hardware.
arXiv Detail & Related papers (2022-12-08T18:59:53Z) - Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum
Compilation [0.0]
We propose the algorithm PermRowCol for routing CNOTs in a quantum circuit.
It dynamically remaps logical qubits during the computation, and thus results in fewer output CNOTs than the algorithms Steiner-Gauss and RowCol.
arXiv Detail & Related papers (2022-05-02T08:20:13Z) - Efficient multi-qubit subspace rotations via topological quantum walks [1.0486921990935787]
The rotation of subspaces by a chosen angle is a fundamental quantum computing operation.
We propose a fast, high-fidelity way to implement such operations via topological quantum walks.
This procedure can be implemented in superconducting qubits, ion-traps and Rydberg atoms with star-type connectivity.
arXiv Detail & Related papers (2021-11-12T02:10:56Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.