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 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) 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.
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(ε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 Traveling Salesman Problem (TSP) serves as a standard benchmark for assessing potential quantum advantage in combinatorial optimization. This paper provides a critical comparative analysis of quantum annealing, gate-based approaches based on quantum phase estimation, and hybrid quantum–classical dynamic programming methods within a unified complexity and implementation framework. While theoretical results indicate reductions of the classical O ( 2 n ) scaling to approximately O ( 1.728 n ) for general instances and to O ( 1.110 n ) for structured cases, these improvements remain largely asymptotic. In practice, all current quantum approaches are strongly constrained by hardware limitations. Quantum annealing suffers from embedding overhead and noise, hybrid methods rely extensively on classical decomposition without guaranteed optimality, and gate-based implementations are limited by circuit depth and error accumulation. As a result, no clear quantum advantage over classical algorithms has been demonstrated at practically relevant problem scales. By systematically separating intrinsic algorithmic scaling from hardware-induced resource constraints, this work clarifies the origin of the gap between theoretical quantum speedups and experimental performance, providing a critical assessment of the current status and realistic prospects of quantum TSP methods.
Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the 2n 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) time, a barrier that has stood for over six decades. Whether quantum computing can surpass O∗(2n) is a central open question. The authors of~\cite{ambainis2019quantum}\ (SODA~2019) claimed a query complexity of O∗(1.727n), but we identify a structural counting error: when corrected, their scheme requires Ω∗(2n) 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.890n), and k=4 attains the global optimum O∗(1.866n), the first quantum algorithm to surpass 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) gates and O(n) depth. Leveraging structured state preparation, we achieve a total time complexity of O∗(1.866n). Qiskit simulations on n=6,7 achieve 98.9% and 100% accuracy.
The paper proposes a quantum algorithm for the traveling salesman problem (TSP) based on the Grover Adaptive Search (GAS), which can be successfully executed on IBM's Qiskit library. Under the GAS framework, there are at least two fundamental difficulties that limit the application of quantum algorithms for combinatorial optimization problems. One difficulty is that the solutions given by the quantum algorithms may not be feasible. The other difficulty is that the number of qubits of current quantum computers is still very limited, and it cannot meet the minimum requirements for the number of qubits required by the algorithm. In response to the above difficulties, we designed and improved the Hamiltonian Cycle Detection (HCD) oracle based on mathematical theorems. It can automatically eliminate infeasible solutions during the execution of the algorithm. On the other hand, we design an anchor register strategy to save the usage of qubits. The strategy fully considers the reversibility requirement of quantum computing, overcoming the difficulty that the used qubits cannot be simply overwritten or released. As a result, we successfully implemented the numerical solution to TSP on IBM's Qiskit. For the seven-node TSP, we only need 31 qubits, and the success rate in obtaining the optimal solution is 86.71%.