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

Preprint · Xujun Bai, Yun Shang, Honghong Lin

- Archive id: arxiv:2606.07322
- Published: 2026-06-05
- arXiv: https://arxiv.org/abs/2606.07322
- Source URL: https://arxiv.org/abs/2606.07322
- PDF: https://arxiv.org/pdf/2606.07322
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.