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

IEEE International Conference on Quantum Computing and Engineering (QCE)

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

Rei Sato, Kazuhiro Saito, Tetsuro Nikuni, Shohei Watabe

Published Sep 17, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.1109/qce57702.2023.10238

Related papers

Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems

Rei Sato, Cui Gordon, Kazuhiro Saito +3 more

Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the problem's constraints—is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher order unconstrained binary optimization representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.

arXiv:2405.07129•IEEE Transactions on Quantum Engineering•Jan 1, 2025•6 citations

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

Tackling Traveling Salesman Problems with a Cluster-Based Quantum-Classical Optimization

Saweed Hussain, Lutfiana Sausan, Abdur Rahman +2 more

A hybrid quantum-classical framework is exploited to solve the Traveling Salesman Problem (TSP) based on a Quantum Approximate Optimization Algorithm (QAOA). To overcome the computational limitation of the Grover’s Search Algorithm (GSA) stemming from path encoding and arithmetic subroutines, a clustering-based strategy is employed to decompose a 16-city TSP into four 4-city subproblems, each of which can be solved with a 16-qubit budget. Intra-cluster solutions are optimized with QAOA, and are classically stitched to construct the global tour. Our results clearly validate the effectiveness of the hierarchical design of the algorithm, highlighting its feasibility for mid-scale quantum optimizations.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 14, 2025•0 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

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

Xujun Bai, Yun Shang, Honghong Lin

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.

quant-pharXiv:2606.07322•Jun 8, 2026•0 citations

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 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.
Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the problem's constraints—is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher order unconstrained binary optimization representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.
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.
A hybrid quantum-classical framework is exploited to solve the Traveling Salesman Problem (TSP) based on a Quantum Approximate Optimization Algorithm (QAOA). To overcome the computational limitation of the Grover’s Search Algorithm (GSA) stemming from path encoding and arithmetic subroutines, a clustering-based strategy is employed to decompose a 16-city TSP into four 4-city subproblems, each of which can be solved with a 16-qubit budget. Intra-cluster solutions are optimized with QAOA, and are classically stitched to construct the global tour. Our results clearly validate the effectiveness of the hierarchical design of the algorithm, highlighting its feasibility for mid-scale quantum optimizations.
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.
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.
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.