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

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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.