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,…