Traffic and smart cities

Traffic optimisation: the most-cited quantum application, measured

Volkswagen's Lisbon traffic pilot is quoted in more quantum computing decks than any other industrial result. The formulation is standard and the problem is real. The classical number is almost never published beside it. This page is that number, together with a property of the standard encoding that changes what the comparison measures.

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 affect the verdict. Embeddable or not, the encoding is 150 qubits at fifty vehicles and exhaustive search returns the exact optimum at ten.

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 nobody quoting the Lisbon pilot states where it sits.

The verdict

Traffic optimisation is not a viable quantum application today, and the limit is not hardware immaturity. Three measured facts settle it.

• 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?

Not yet at any useful size, and the reason is arithmetic rather than pessimism. Route assignment for ten vehicles is thirty qubits and classical exhaustive search finds the exact optimum in 0.18 seconds, so there is nothing for a quantum computer to improve. 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 quantum half of this comparison is not finished. We have the classical baseline and the formulation finding; the QAOA run against these same instances is not yet measured, and this page will say so until it is. The instances are seeded so anyone can generate them and get the identical graphs.

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 job returns a documented accuracy statement, and simulation costs $0.001. See how we benchmark for the rules these numbers follow, including that results are published whichever side wins.

Related: route optimisation, the honest answer and maximum independent set, measured on hardware