Quantum Divide-and-Conquer TSP Solver Achieves Improved Exponential Base Over Classical Held-Karp Algorithm
By
[Submitted on 5 Jun 2026]
Plain bagel done well. Pleasantly substantive.
Summary
This paper presents a quantum divide-and-conquer approach to the traveling salesman problem (TSP), a classic NP-hard optimization problem. The authors propose a parameterized spectrum that combines classical dynamic programming with quantum search, where the hybrid algorithm from prior work (Ambainis et al., 2019) is just one specific case. They prove optimal query complexity of O*(1.865666^n) using a 4-subset scheme, and correct a miscalculation in prior work showing the 8-subset scheme cannot surpass the classical Held-Karp bound. Crucially, the paper argues that quantum advantage comes not only from quadratic speedup of quantum search but also from structured quantum state preparation, and they design a practical method for preparing set partition states to make the solver executable.
Key quotes
· 5 pulledWe demonstrate that combining classical dynamic programming with quantum search can yield an achievable quantum advantage for TSP on the basis of excellent work by the authors of Ambainis et al. 2019.
Within our parameterized spectrum, we prove that the optimal query complexity is $O^*(1.865666\ldots^n)$, achieved with the 4-subset scheme.
The correct query complexity of their algorithm is $O^*(2.225880\ldots^n)$ at their chosen parameter ($\alpha\approx0.055362$), and cannot fall below $O^*(2^n)$ for any $\alpha$ - meaning their $8$-subset scheme, correctly analyzed, never surpasses the classical Held-Karp bound.
Our work, however, points out that the quantum advantage stems not only from the quadratic speedup of quantum search but also from the structured quantum state preparation.
We design an elegant method for preparing the set partition state, which makes our TSP solver practically executable.
You might also wanna read
Per-Instance TSP Solver Using PPO Achieves 1.66% Gap on d1291 Without Pre-training
A developer presents a novel approach to solving the Traveling Salesman Problem (TSP) using deep learning without pre-training. Instead of r
news.ycombinator.com·5mo ago
Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
journals.aps.org·11mo ago
New Algorithm Breaks Dijkstra's Time Complexity for Directed Shortest Paths
The article presents a deterministic algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weight
arxiv.org·10mo ago
Exploring Computational Complexity: A Ruliological Approach to the P vs. NP Problem
The article explores computational complexity theory and the P vs. NP problem through a 'ruliological' approach, examining why fundamental q
writings.stephenwolfram.com·4mo ago
New Quantum Algorithm Accelerates Timeline for Breaking Current Encryption Standards
Researchers at the Advanced Quantum Technologies Institute have developed a new quantum algorithm called JVG that dramatically accelerates t
briefglance.com·3mo ago