Quantum Approaches to the Traveling Salesman Problem

Overview

The traveling salesman problem asks for the shortest route that visits each of N cities exactly once and returns to the start. It is one of the most studied problems in optimization, with applications in logistics, circuit board drilling, and genome assembly. It is NP-hard, so no efficient exact algorithm is known, though practical solvers handle enormous instances.

Quantum approaches come in three forms. Heuristic methods encode the problem as an energy minimization and use quantum annealing or QAOA. Provable algorithms use quantum search and dynamic programming to improve the exponential running time of the best exact classical algorithms. And hybrid methods split large problems between classical and quantum solvers. None has beaten the best classical solvers on practical instances.

The problem it solves

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.

History and background

The Ising formulation of the traveling salesman problem was laid out by Andrew Lucas in 2014 in his paper on Ising formulations of many NP problems, which became a standard reference for quantum annealing and QAOA studies. D-Wave and other groups used it in the following years for small instances, and the QAOA community adopted it from 2017 onward, including implementations on IBM devices with a handful of cities.

On the theory side, Moylett, Linden, and Montanaro showed in 2017 that quantum search gives a quadratic speedup over classical algorithms of backtracking type for bounded-degree graphs. In 2019 Ambainis, Balodis, Iraids, Kokainis, Prūsis, and Vihrovs gave quantum algorithms that speed up exponential-time dynamic programming, with a reported running time of about 1.73 to the power n for the traveling salesman problem, against the roughly 2 to the power n of the classical Held-Karp algorithm. Meanwhile classical solvers such as Concorde have found provably optimal tours for instances with tens of thousands of cities.

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.

To use a quantum optimizer, you first convert the route into binary variables. Let x sub v t equal 1 if city v is visited at step t. That needs N squared binary variables. A cost function adds the distances between consecutive cities, and penalty terms enforce that each city appears exactly once and each step visits exactly one city.

The resulting quadratic function of binary variables is an Ising energy. Valid tours have low energy, and the shortest tour has the lowest. Quantum annealing and QAOA try to find that minimum, the first by slowly evolving a physical system and the second by alternating cost and mixing layers with tuned angles.

The weakness is size and structure. The encoding uses N squared qubits, most of which are wasted on invalid configurations that the penalties must suppress, so small instances already need many qubits and the penalty weights are hard to tune. Better encodings use permutation-preserving mixers that keep the state within valid tours, which reduces the search space at the price of deeper circuits.

Step by step

1. Define binary variables x sub v t for city v at step t, and fix the first city to break symmetry.
2. Write the cost function: the sum over steps of distances between the city at step t and the city at step t plus 1, plus penalty terms forcing each row and column of x to have exactly one 1.
3. Convert the quadratic function to an Ising Hamiltonian, and choose penalty weights large enough to forbid invalid tours but not so large that they swamp the distance terms.
4. Run quantum annealing, or QAOA with p layers and a classical optimizer for the angles, to find low-energy bit strings.
5. Decode the best sample into a tour, check its validity, and compute its length. Repair or discard invalid samples.
6. Optionally refine the result with classical local search such as 2-opt, and compare with a classical solver.

A worked example

Take four cities, which need 16 binary variables, or 9 after fixing the first city. A valid assignment, such as city A at step 1, B at step 2, C at step 3, and D at step 4, has one 1 in each row and column, and the cost is the sum of the four edge lengths. There are only 3 distinct tours for four cities up to direction and rotation, so brute force is trivial.

For 10 cities, the direct encoding needs about 81 qubits after fixing the start, and there are 181,440 distinct tours. Current gate-based devices and annealers can handle only a handful of cities in this way, and the results are usually no better than random sampling plus local search. For 85,900 cities, Concorde found the optimal tour using classical methods, a scale far beyond any quantum device.

Complexity and resources

What hardware it needs

• For heuristics, hundreds to thousands of well-connected qubits for even modest instances, which current devices lack.
• For the exact quantum algorithms, a fault-tolerant machine and quantum random access memory.
• A classical computer for encoding, post-processing, and comparison.

Applications

• Benchmarking quantum optimization hardware on a standard hard problem.
• Logistics and routing pilot studies, usually with hybrid solvers that handle subproblems.
• Exploring constraint-preserving mixers and encodings for permutation problems.

Limitations and caveats

• The problem uses many qubits for a small number of cities, and invalid configurations waste the search space.
• Penalty tuning is difficult and results are sensitive to it.
• Classical solvers are vastly better for all practical instance sizes.
• The provable quantum speedups are modest compared with the exponential cost of the problem.

Common misconceptions

• A quantum computer cannot solve the traveling salesman problem in polynomial time. It is NP-hard, and no quantum algorithm is known to do that.
• A quantum solution on a five-city problem does not indicate advantage.
• Hybrid solver results on large instances come mostly from the classical components.

How it compares

• Classical solvers such as Concorde and Lin-Kernighan-based heuristics solve very large instances.
• Quantum annealing and QAOA use the same Ising encoding with different dynamics.
• Grover-based and dynamic-programming-based quantum algorithms offer provable but modest speedups for exact solutions.

Real-world impact

Frequently used as a benchmark problem for testing near-term quantum optimization hardware and algorithms, including in logistics industry pilot studies.

Why it matters

The traveling salesman problem is the standard example in discussions of quantum optimization, so it is the problem that many readers will test against. Understanding why direct quantum approaches struggle with it teaches how encoding overhead and classical competition shape any claim of advantage.

It also reflects the field's progress from heuristics to provable results, where careful algorithms such as the exponential-time dynamic programming speedups show what a clear quantum advantage could look like.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Approximate Optimization Algorithm (QAOA)
• Related algorithm: Quantum Annealing
• Related algorithm: Max-Cut with Quantum Algorithms (QAOA and Quantum Max-Cut)
• Related algorithm: Grover's Algorithm

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database