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:2606.07322

Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the $2^n$ Barrier

Xujun Bai, Yun Shang, Honghong Lin

quant-phcs.CCSubmitted Jun 5, 2026• Announced Jun 8, 2026• 0 citations• Revised Jul 5, 2026 (v2)
v1 · Jun 5, 2026v2 · Jul 5, 2026
arXivHTMLPDF

Abstract

The traveling salesman problem (TSP) is a classic NP-hard problem. Held--Karp dynamic programming~\cite{held1962dynamic, bellman1962dynamic} solves it exactly in $O(n^2 2^n)$ time, a barrier that has stood for over six decades. Whether quantum computing can surpass $O^*(2^n)$ is a central open question. The authors of~\cite{ambainis2019quantum}\ (SODA~2019) claimed a query complexity of $O^*(1.727^n)$, but we identify a structural counting error: when corrected, their scheme requires $Ω^*(2^n)$ queries and offers no advantage over classical Held--Karp. We design a quantum divide-and-conquer framework: partition $n$-vertex set into $k$ subsets, classically precompute shortest paths within each, then search over all $k$-partitions via quantum minimum finding. We prove $k=3$ achieves $O^*(1.890^n)$, and $k=4$ attains the global optimum $O^*(1.866^n)$, the first quantum algorithm to surpass $O^*(2^n)$ for general TSP. To convert the query bound into a time-complexity advantage, we overcome the oracle-construction bottleneck by preparing a set partition state, requiring $O(n^2)$ gates and $O(n)$ depth. Leveraging structured state preparation, we achieve a total time complexity of $O^*(1.866^n)$. Qiskit simulations on $n=6,7$ achieve $98.9\%$ and $100\%$ accuracy.

Related papers

Embedding All Feasible Solutions of Traveling Salesman Problem by Divide-and-Conquer Quantum Search

Rei Sato, Kazuhiro Saito, Tetsuro Nikuni +1 more

Quantum search algorithms, such as the Grover algorithm, are investigated as one of the ways to solve a traveling salesman problem (TSP). In TSP, the quantum search starts from an equal superposition of all feasible solutions. The embedding cost of all feasible solutions is up to exponential, i.e.,$\mathcal{O}(n!)$with$n$cities, and makes it difficult to solve large-scale TSP. Hence, preparing the initial state of TSP at a lower embedding cost is an important issue. Here, we propose a quantum search algorithm based on the divide-and-conquer approach, which divides each constraint term of the TSP into subproblems and applies the quantum search to each subproblem. We investigate the embedding quality of all feasible solutions by comparing our proposed method with the Grover algorithm regarding optimal iterations and success probability. The results show that our quantum divide-and-conquer approach can significantly reduce the embedding cost while the success probability decreases.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•3 citations

A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits

Bai Xujun, Yun, Shang

The Traveling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation. Our work provides a meaningful research case on how to fully utilize the structures of specific problems to unleash the acceleration capability of the quantum search algorithms.

arXiv:2502.08853•Feb 12, 2025•0 citations

Travelling Salesman Problem in the Classical to Quantum Era: A Comparative Review of Algorithms and Computational Complexity

Istiyak Amin Santo, Siow Chun Lim, Md Serajun Nabi +3 more

The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.

•Nov 12, 2025•1 citation

A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits

Xujun Bai, Yun Shang

The Travelling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation.

Theoretical Computer Science•Jun 23, 2025•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 quantum algorithm for solving travelling salesman problem: An IBM quantum experience

Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera +1 more

The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.

arXiv:1805.10928•May 28, 2018•62 citations
Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the 2n2^n2n Barrier
The traveling salesman problem (TSP) is a classic NP-hard problem. Held--Karp dynamic programming~\cite{held1962dynamic, bellman1962dynamic} solves it exactly in O(n22n)O(n^2 2^n)O(n22n) time, a barrier that has stood for over six decades. Whether quantum computing can surpass O∗(2n)O^*(2^n)O∗(2n) is a central open question. The authors of~\cite{ambainis2019quantum}\ (SODA~2019) claimed a query complexity of O∗(1.727n)O^*(1.727^n)O∗(1.727n), but we identify a structural counting error: when corrected, their scheme requires Ω∗(2n)Ω^*(2^n)Ω∗(2n) queries and offers no advantage over classical Held--Karp. We design a quantum divide-and-conquer framework: partition nnn-vertex set into kkk subsets, classically precompute shortest paths within each, then search over all kkk-partitions via quantum minimum finding. We prove k=3k=3k=3 achieves O∗(1.890n)O^*(1.890^n)O∗(1.890n), and k=4k=4k=4 attains the global optimum O∗(1.866n)O^*(1.866^n)O∗(1.866n), the first quantum algorithm to surpass O∗(2n)O^*(2^n)O∗(2n) for general TSP. To convert the query bound into a time-complexity advantage, we overcome the oracle-construction bottleneck by preparing a set partition state, requiring O(n2)O(n^2)O(n2) gates and O(n)O(n)O(n) depth. Leveraging structured state preparation, we achieve a total time complexity of O∗(1.866n)O^*(1.866^n)O∗(1.866n). Qiskit simulations on n=6,7n=6,7n=6,7 achieve 98.9%98.9\%98.9% and 100%100\%100% accuracy.
Quantum search algorithms, such as the Grover algorithm, are investigated as one of the ways to solve a traveling salesman problem (TSP). In TSP, the quantum search starts from an equal superposition of all feasible solutions. The embedding cost of all feasible solutions is up to exponential, i.e.,O(n!)\mathcal{O}(n!)O(n!)withnnncities, and makes it difficult to solve large-scale TSP. Hence, preparing the initial state of TSP at a lower embedding cost is an important issue. Here, we propose a quantum search algorithm based on the divide-and-conquer approach, which divides each constraint term of the TSP into subproblems and applies the quantum search to each subproblem. We investigate the embedding quality of all feasible solutions by comparing our proposed method with the Grover algorithm regarding optimal iterations and success probability. The results show that our quantum divide-and-conquer approach can significantly reduce the embedding cost while the success probability decreases.
The Traveling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation. Our work provides a meaningful research case on how to fully utilize the structures of specific problems to unleash the acceleration capability of the quantum search algorithms.
The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.
The Travelling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation.
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.
The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.