Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2603.21283

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

Alexander Johannes Stasik, Franz Georg Fuchs

quant-phmath.COSubmitted Mar 22, 2026• Announced Mar 24, 2026• 0 citations• Revised Sep 3, 2026 (v4)
v1 · Mar 22, 2026v2 · Mar 26, 2026v3 · Jun 18, 2026v4 · Sep 3, 2026
arXivHTMLPDF

Abstract

For a traveling salesperson problem (TSP) 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 $\mathcal{O}(n\log n)$ qubits, while a naive implementation requires $\mathcal{O}(n^3\log_2 n)$ CX gates and $\mathcal{O}\!\left(n^3[\log_2 n+\log_2(1/ε)]\right)$ $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 (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

Quantum Algorithm for the Traveling Salesperson Problem

Andrew Haverly, M. A. Novotny, Shahram Rahimi

The traveling salesperson problem (TSP) is “if a traveling salesman wishes to visit exactly once each of a list of$m$cities (where the cost of traveling from city$i$to city$j$is$c_{ij}$) and then return to the home city, what is the least costly route the traveling salesman can take [1]?” The TSP is an NP-Complete problem. This paper introduces a solution to the TSP using Grover's quantum algorithm. This paper also introduces a quantum algorithm to the minimum (and maximum) spanning tree problem. The full circuit implementation is presented using the open-source Qiskit environment [2]. This paper provides the number of qubits required, the quantum depth, and the quantum volume of the algorithm for the TSP. This paper also shows how to solve the minimum (and maximum) spanning tree using Grover's algorithm.

IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)•Dec 4, 2023•1 citation

Travelling Salesperson Problem with Quantum Computing

Bhanu Lalith Aakash Medury, Vyoma Harshitha Podapati

Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.

International Journal of Engineering Research and•Mar 12, 2020•1 citation

Quantum iterative approach to the Traveling Salesman Problem

Arturo Rodríguez-Almazán, Guillermo Rivas, Ricardo S. Alonso +2 more

The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of $O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})$ which depends on the error tolerance parameter $ε$. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.

quant-pharXiv:2606.11843•Physica Scripta•Jun 11, 2026•0 citations

Efficient Encoding of the Traveling Salesperson Problem on a Quantum Computer

John Stenger, Sean Crowe, Joseph Diaz +3 more

We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function using a probability distribution obtained on a quantum computer. Our encoding requires a number of qubits that grows logarithmically with the number of cities. We propose to calculate the cost function using a nonlinear function of expectation values of quantum operators. This is in contrast to the typical method of evaluating the cost function by summing expectation values of quantum operators. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.

Quantum Reports•Jul 17, 2025•4 citations

Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables

Simon Garhofer, Oliver Bringmann

The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly.

arXiv:2412.07450•Dec 10, 2024•1 citation

Solving the travelling salesman problem using Bloch sphere encoding

Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher +1 more

Abstract The travelling salesman problem (TSP) is a popular NP-hard combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing methods of solving TSPs on quantum systems are either gate-based or binary variable-based encoding. Both approaches are resource-expensive in terms of the number of qubits, while performing worse compared to existing classical algorithms, even for small-sized problems. A novel encoding scheme is needed to map the TSP problem onto a quantum system, which is addressed in this work. We introduce a distinct geometric approach to encode the TSP on a single qubit and present a quantum-inspired algorithm to solve the problem by invoking the principle of quantum superposition . The cities are represented as quantum states on the Bloch sphere, while the preparation of superposition states allows us to traverse multiple paths at once. The underlying framework of our algorithm is a quantum-inspired version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements. For the TSP problem sizes considered in this work, our algorithm is more resource-efficient and accurate than existing quantum algorithms, with the potential for scalability.

arXiv:2407.17207•Quantum Science and Technology•Nov 12, 2025•14 citations
For a traveling salesperson problem (TSP) of nnn 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−1n-1n−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(nlog⁡n)\mathcal{O}(n\log n)O(nlogn) qubits, while a naive implementation requires O(n3log⁡2n)\mathcal{O}(n^3\log_2 n)O(n3log2​n) CX gates and O ⁣(n3[log⁡2n+log⁡2(1/ε)])\mathcal{O}\!\left(n^3[\log_2 n+\log_2(1/ε)]\right)O(n3[log2​n+log2​(1/ε)]) TTT 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 (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.
The traveling salesperson problem (TSP) is “if a traveling salesman wishes to visit exactly once each of a list ofmmmcities (where the cost of traveling from cityiiito cityjjjiscijc_{ij}cij​) and then return to the home city, what is the least costly route the traveling salesman can take [1]?” The TSP is an NP-Complete problem. This paper introduces a solution to the TSP using Grover's quantum algorithm. This paper also introduces a quantum algorithm to the minimum (and maximum) spanning tree problem. The full circuit implementation is presented using the open-source Qiskit environment [2]. This paper provides the number of qubits required, the quantum depth, and the quantum volume of the algorithm for the TSP. This paper also shows how to solve the minimum (and maximum) spanning tree using Grover's algorithm.
Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.
The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of O(m2log⁡2(m)log⁡2(1/ε)ε)O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})O(ε​m2log2​(m)log2​(1/ε)​) which depends on the error tolerance parameter εεε. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function using a probability distribution obtained on a quantum computer. Our encoding requires a number of qubits that grows logarithmically with the number of cities. We propose to calculate the cost function using a nonlinear function of expectation values of quantum operators. This is in contrast to the typical method of evaluating the cost function by summing expectation values of quantum operators. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.
The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly.
Abstract The travelling salesman problem (TSP) is a popular NP-hard combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing methods of solving TSPs on quantum systems are either gate-based or binary variable-based encoding. Both approaches are resource-expensive in terms of the number of qubits, while performing worse compared to existing classical algorithms, even for small-sized problems. A novel encoding scheme is needed to map the TSP problem onto a quantum system, which is addressed in this work. We introduce a distinct geometric approach to encode the TSP on a single qubit and present a quantum-inspired algorithm to solve the problem by invoking the principle of quantum superposition . The cities are represented as quantum states on the Bloch sphere, while the preparation of superposition states allows us to traverse multiple paths at once. The underlying framework of our algorithm is a quantum-inspired version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements. For the TSP problem sizes considered in this work, our algorithm is more resource-efficient and accurate than existing quantum algorithms, with the potential for scalability.