Quantum Algorithms Database
Quantum Approaches to the Traveling Salesman Problem
Adaptations of QAOA and related quantum optimization algorithms to the classic traveling salesman problem — finding the shortest route visiting a set of locations exactly once.
Year
2017 onward (various QAOA-based formulations)
Inventor(s)
Multiple contributors building on QAOA
Speedup Type
Heuristic (No Proven Speedup)
Difficulty
★★★★☆
The Problem
Finding the shortest possible route that visits every location in a given set exactly once and returns to the start — a famously hard combinatorial optimization problem.
How It Works
Encodes valid routes as quantum states using carefully designed cost functions, then applies QAOA-style alternating quantum and classical optimization steps to find low-cost (short) routes.
Real-World Impact
Frequently used as a benchmark problem for testing near-term quantum optimization hardware and algorithms, including in logistics industry pilot studies.