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 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.