Route optimisation: the most oversold quantum application

This page has no quantum benchmark, and that is the result

On our other pages we run the quantum method and report how it did. Here we cannot, and the reason is the finding.

To put a travelling salesman problem on a quantum computer you encode it as a QUBO, which needs a binary variable for every combination of stop and position in the tour. That is N squared variables for N stops, and one qubit per variable. Ten stops needs 100 qubits. The largest processor we can run is 108, and the largest built anywhere is around 1,600. Neither helps much: a thousand qubits buys you a 31-stop route, and those are physical qubits with no error correction, where a routing circuit of that depth would return noise.

A ten-stop delivery round is not a logistics problem. It is a morning.

Read the two middle columns together

At 200 stops, a real distribution problem, the classical solver produces a route inside a three-second budget on an ordinary laptop. The quantum encoding of the same problem needs 40,000 qubits, with no error correction accounted for. Add fault tolerance at today's error rates and the physical requirement passes 60 million.

The gap is not a matter of waiting for the next hardware generation. It is four orders of magnitude on logical qubits alone, against a classical method that already answers the question faster than you can read the output.

Why the pitch decks say otherwise

Two moves, and both are technically true in isolation.

The first is to quote the size of the search space. A 200-stop tour has more orderings than there are atoms in the observable universe, which is correct and irrelevant, because no solver enumerates them. Branch and bound with good bounds never visits the vast majority of that space, which is exactly why OR-Tools finishes in seconds.

The second is to demonstrate on a tiny instance. A five or six stop route does fit on current hardware, and a demonstration at that size is real. It is also a problem you can solve by hand, and the encoding cost means it does not extend.

What would have to change

Not hardware, in the first instance. The encoding would have to change. Quadratic qubit scaling is a property of the standard QUBO formulation of routing, not a law, and better formulations exist in the literature for restricted variants. Until one of them reduces the cost by orders of magnitude, hardware progress does not help, because you cannot reach 40,000 logical qubits by improving fidelity.

The published roadmaps make this concrete. Quantinuum Sol targets roughly 100 logical qubits in 2027, and IBM Starling and Quantinuum Apollo target hundreds by 2029. Hundreds of logical qubits is a genuine achievement and it buys a delivery round of about fifteen stops. The encoding, not the roadmap, is the binding constraint here.

If someone offers you a quantum routing solution, the question worth asking is not how many qubits their machine has. It is how many binary variables their encoding needs for the instance size you actually run, and how that compares to what OR-Tools does with it on a laptop.

Where operations problems do fit

This is not a general verdict on operations research. Satellite observation tasking encodes as a maximum weighted independent set at one variable per request, which is linear rather than quadratic, and on that problem we do have a quantum benchmark and QAOA does sometimes find the optimum. The difference between the two pages is the encoding, not the industry.