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

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^{\ast }(2^n)$ is a central open question. The authors of~\cite{ambainis2019quantum}\ (SODA~2019) claimed a query complexity of $O^{\ast }({1.727}^n)$, but we identify a structural counting error: when corrected, their scheme requires ${\mathrm{\Omega }}^{\ast }(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^{\ast }({1.890}^n)$, and $k=4$ attains the global optimum $O^{\ast }({1.866}^n)$, the first quantum algorithm to surpass $O^{\ast }(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^{\ast }({1.866}^n)$. Qiskit simulations on $n=6,7$ achieve $98.9\mathrm{\%}$ and $100\mathrm{\%}$ accuracy.