Traffic optimisation: the most-cited quantum application, measured

The problem, stated exactly

Each vehicle has a small set of candidate routes. Choosing one route per vehicle, minimise congestion, where congestion is the number of vehicles sharing a road segment beyond the first. That is a quadratic unconstrained binary optimisation problem with one binary variable per vehicle-route pair, so ten cars with three routes each is thirty variables and therefore thirty qubits.

The classical baseline, measured

Instances generated from published seed 20260910, three routes per vehicle. Exhaustive search is the exact optimum, not an approximation. Minimum-congestion greedy is the cheap classical answer.

Read the last column first. Ten cars, the size at which a quantum machine starts to be interesting, is settled exactly in 0.18 seconds by brute force. Not heuristically, not approximately: every one of the 59,049 assignments was enumerated.

There is no room for a quantum computer to be useful at this size, because there is nothing left to be useful about.

The greedy column is more interesting than it looks. It matches the optimum at 4, 6 and 10 cars and misses at 8, returning 10 against a true optimum of 8. So the cheap classical answer is usually right and occasionally not, which is exactly the regime where a better optimiser earns its keep.

That is the opening for a quantum method, and it is narrower than "exponentially many routes" implies.

The finding: the standard encoding answers a different question

Neutral-atom vendors map traffic onto maximum independent set, because independent set is what that hardware solves natively. Build the conflict graph: one vertex per vehicle-route pair, an edge between any two that cannot both be chosen, either because they belong to the same vehicle or because they share a road segment.

Each vehicle's routes therefore form a clique, so a maximum independent set contains at most one route per vehicle, and its size equals the number of vehicles precisely when a completely conflict-free assignment exists. That means maximum independent set answers "does a zero-congestion assignment exist?", a decision problem, and not "minimise congestion", which is what traffic actually asks. Those are different questions, and on any real network the first one answers no while the second one is the whole job.

Whether the graph fits neutral-atom hardware directly

Neutral-atom machines require a unit-disk graph: atoms placed so that the edges are exactly the pairs falling inside the blockade radius. An arbitrary graph has to be embedded into positions first, and the embedding is routinely more expensive than the problem it encodes.

A unit-disk graph cannot contain a vertex with six mutually non-adjacent neighbours, so the largest induced star is a cheap necessary test. On these instances it reaches 3 at four vehicles and 4 at six, both inside the limit of 5.

The test therefore does not rule out a direct embedding, and being a necessary rather than sufficient condition, it does not establish one. The question is open.

It also does not change the measurement. Embeddable or not, the encoding is 150 qubits at fifty vehicles and exhaustive search returns the exact optimum at ten.

QAOA on the same instances, measured

The same seeded instances, run as QAOA at depth p on an exact statevector simulator, so the distribution is the true one and the only error is the optimiser's. Lower congestion is better, and QAOA best is the answer a user would actually take: the most probable assignment that is valid, not the best state hiding anywhere in the distribution.

Across these instances QAOA matched greedy twice and trailed it once. At four cars it returned congestion 2 where greedy and the optimum are both 1. At six it matched at p=2 and trailed at p=1 and p=3. At eight it matched greedy at 10, with the optimum at 8.

The two trends matter more than any single row. The probability of landing on an optimal assignment falls by three orders of magnitude between four cars and eight, from 0.055 to 0.00015, so the answer becomes harder to find at exactly the rate the problem grows. Meanwhile one p=2 run went from 0.3 seconds to 36 minutes over the same range, against 0.18 seconds for exhaustive search at ten cars. Deeper circuits did not reliably help: p=3 was worse than p=2 at both four and six cars, which is the optimiser failing to converge rather than the algorithm degrading.

The rows above stop at eight cars because the exact-statevector harness that produced them tops out at twenty-four qubits on the machine it ran on. Ten cars, thirty qubits, was run separately and is below.

Ten cars, thirty qubits, on four kinds of compute

The ten-car instance does not fit the harness above, so it was run through the service instead, and those runs are the table at the top of this page. All three engines returned the same thing, and the agreement is the result.

All three agreed, and the agreement is the result. A real superconducting processor executed a thirty-qubit, depth-62 circuit and returned the same thing the simulators did. Where three different kinds of machine give the same answer, the limit belongs to the problem rather than to any of them.

The limit here is the encoding. One binary per vehicle-route pair means each vehicle must end with exactly one of its three bits set, which happens by chance with probability 3/8 per vehicle. Across ten vehicles that is (3/8)¹⁰, about one part in 18,000, so 500 shots of a circuit that has not been concentrated onto the feasible subspace is expected to return 0.027 valid assignments. Zero is what the arithmetic predicts.

Optimising the parameters is what normally fixes that, and on the eight-car instance it did: measured, it raised the valid fraction from 0.039 percent to 4.8 percent, a factor of 122. Applying the same factor at ten cars would still leave roughly three valid shots in 500.

The optimisation itself is the constraint at this width. This instance has 228 couplings out of a possible 435, so it is close to all-to-all: exact statevector needs 16 GB, and a tensor network did not finish a single evaluation in 180 seconds locally, because that coupling density is the case the low-entanglement assumption does not cover. A variational loop needs hundreds of such evaluations. For comparison, exhaustive classical search settles the same instance in 0.18 seconds.

Where the wall actually is

The squeeze is the whole story. Below about twenty vehicles classical search is exact and instant, so there is nothing to win. Above about fifty the encoding needs more qubits than any gate machine we can rent, and a real urban fleet is thousands of vehicles, not fifty.

The band where a quantum method could plausibly help is narrow, and the section below sets out where it sits.

What the measurements show

Three measured facts define where this problem currently sits. What they imply for a given programme depends on the sizes that programme cares about.

• At the sizes a quantum machine can hold, classical search is exact and immediate. Ten vehicles, thirty qubits, 0.18 seconds, every assignment enumerated
• At the sizes that matter operationally, the encoding does not fit. Fifty vehicles is 150 qubits, wider than any gate processor available to rent, and a city fleet is thousands
• The independent-set formulation the hardware vendors use answers the decision problem, not the optimisation problem. This one is a proof rather than a measurement

One band remains genuinely open, and it is the only one: roughly twenty to forty vehicles, where exhaustive search has become expensive and the encoding still fits on a real device. Greedy is optimal on three of our four instances and wrong on the fourth, so a better optimiser has something to win there. That is a narrow and specific claim, and it is the claim anyone selling quantum traffic optimisation should be asked to demonstrate.

Common questions

Can quantum computing optimise traffic?

At the sizes measured here, classical search is already exact and immediate: route assignment for ten vehicles is thirty qubits, and exhaustive search finds the proven optimum in 0.18 seconds. The open question is what happens above that, which is what the encoding table sets out.

Scale to fifty vehicles and the problem needs 150 qubits to encode, which is wider than any gate processor available to rent. A real city fleet is thousands of vehicles.

What did the Volkswagen Lisbon quantum traffic pilot actually show?

It showed that the routing problem can be expressed in a form quantum hardware accepts, and that a small fleet can be assigned routes that way. What such pilots characteristically do not publish is the classical baseline on the same instances, which is the only number that decides whether the quantum method helped. On our instances, brute force settles ten vehicles exactly in under a fifth of a second.

How many qubits does traffic optimisation need?

One qubit per vehicle-route pair. With three candidate routes each that is three qubits per vehicle: 30 for ten cars, 60 for twenty, 150 for fifty, and 300 for a hundred. Encoding is the binding constraint long before circuit depth or noise becomes the issue.

Run the instances yourself

The instances are seeded, so anyone can regenerate them and get the identical graphs, the identical optima and the identical greedy answers. One case is still open: ten cars at thirty qubits has a classical optimum of 11 and no QAOA run, because the exact-statevector harness behind the table above stops at twenty-four qubits.

pip install qsim-sdk

import qsim_sdk
client = qsim_sdk.Client(token="...")

# A free estimate before you spend anything
client.estimate(your_qaoa_circuit, shots=1000)

Every circuit returns a documented accuracy statement, and simulation costs $0.0001. See how we benchmark for the rules these numbers follow, including that results are published whichever side wins.

Related: route optimisation, and what 400 qubits buys and maximum independent set, measured on hardware