Quantum Advantage

In October 2019 Google announced that its 53-qubit Sycamore chip had finished, in about 200 seconds, a computation it estimated would take the world's fastest supercomputer roughly 10,000 years. Headlines declared "quantum supremacy." And yet — nobody actually wanted the answer. The task was a deliberately contrived one, chosen not because it was useful but because it was hard to fake classically. This page is about that curious milestone: quantum advantage, the moment a quantum computer does something no classical computer feasibly can — and about the large, honest asterisk that hangs over what it really proves.

What "quantum advantage" means

Quantum advantage (the older, more triumphant term is quantum supremacy) is a precise claim: a programmable quantum device performs a well-defined task that is infeasible for any classical computer in a reasonable time. Not "faster by a constant factor" — infeasible, meaning the best classical method would need centuries, or more energy than exists, to keep up.

Crucially, this is a statement about time to complete a task, and it leans on the same machinery as the class BQP: we believe the task sits in what a quantum machine can do efficiently but outside what a classical machine can. "Believe" is the operative word — as we'll see, quantum advantage rests on complexity-theoretic assumptions, not proofs.

Two very different kinds of advantage

The single most important distinction on this page — and the one most headlines blur — is between two completely different claims that share the word "advantage."

(1) Computational-complexity advantage on a contrived task. The quantum machine wins a race on a problem designed to be quantum-friendly and classically hard. The task itself is useless — it computes nothing anyone needs. This is what has (contestedly) been demonstrated.
(2) Practical advantage on a useful problem. The quantum machine solves a problem people actually care about — simulating a molecule for drug design, optimising a supply chain — better, faster, or cheaper than any classical method. This is the real prize, and it is still largely open.

The demonstrations so far are firmly of type (1). Conflating them with type (2) is the central misreading of the whole field: a stopwatch victory on a made-up task is not a useful computation.

Why sampling? The task that fits quantum hardware

If you wanted to prove a noisy NISQ-era machine can outrun a supercomputer, you would not pick factoring (too deep for today's hardware). You would pick a task that is natural for the hardware to run but believed brutal to simulate. That task is sampling: not "compute a number," but "produce random samples from a particular probability distribution."

The two landmark families are:

Random Circuit Sampling (RCS) — apply a fixed, random sequence of gates to your qubits and measure. The output bit-strings follow a complicated distribution (with speckle-like quantum interference). This is exactly what Google's Sycamore did.
Boson Sampling — send identical photons through a large optical network of beam-splitters and record where they emerge. USTC's Jiuzhang photonic machines are the headline demonstrations. The output statistics are governed by the permanent of a matrix — a quantity famously hard to compute.

Both are "just let the physics run" for the quantum device, yet both are tied to counting problems (the permanent, and the amplitudes of a random circuit) that are #P-hard — the class of hard counting problems believed far beyond efficient classical reach.

Worked example 1: why a sampling task is a good supremacy candidate

A good quantum-advantage task must clear three bars at once. Watch how random circuit sampling clears each:

Easy for the quantum machine. Running a depth-20 random circuit on 53 qubits and measuring is well within a NISQ device's budget — it is a shallow circuit, exactly the kind NISQ hardware can attempt. To draw one sample you literally run the chip once.
Believed hard for a classical machine. To sample the same distribution classically, the natural route is to track the quantum state — a vector of 2^{53} \approx 9 \times 10^{15} complex amplitudes. Storing that alone is petabytes; evolving it through the circuit is the crushing cost.
Tied to a #P-hard quantity. Each output probability is essentially the squared magnitude of one amplitude, and computing such amplitudes exactly is #P-hard. Theory shows that if a fast classical algorithm could sample this distribution well, a chain of plausible complexity assumptions (the non-collapse of the polynomial hierarchy) would break. So classical simulation is believed super-polynomial.

Notice the shape of the argument: the task is trivial to run and, under standard assumptions, infeasible to fake. That asymmetry — cheap for quantum, believed impossible for classical — is the whole game. It is exactly the BQP-vs-classical gap, made concrete on real hardware.

The demonstrations, and the gap that keeps shrinking

The bars below place three runtimes on a logarithmic time axis (each step right is another factor of ten). Step through them: first Sycamore's ~200 seconds, then the original claim that a classical machine would need ~10,000 years, and finally what happened next — improved classical algorithms clawed that estimate down from millennia to mere days.

The bar for the quantum device barely moves. What moves — dramatically — is the classical estimate, and that instability is the heart of the controversy.

Worked example 2: "200 seconds vs 10,000 years" — and the pushback

Google's 2019 estimate compared Sycamore's \approx 200 seconds against a projected classical runtime of \approx 10{,}000 years on the Summit supercomputer. As a raw ratio that is staggering:

\frac{10{,}000\ \text{years}}{200\ \text{s}} \;=\; \frac{10{,}000 \times 3.15\times10^{7}\ \text{s}}{200\ \text{s}} \;\approx\; 1.6 \times 10^{9}.

A billion-fold gap — if the classical estimate holds. But it did not hold. Within days IBM argued that by using Summit's enormous disk storage cleverly the task could be done in about 2.5 days, not 10,000 years. Over the following years, better tensor-network methods and "spoofing" algorithms cut the classical cost much further — some later work claimed the Sycamore distribution could be matched in hours on ordinary clusters. Redo the ratio with the 2.5-day figure:

\frac{2.5\ \text{days}}{200\ \text{s}} \;=\; \frac{2.5 \times 86{,}400\ \text{s}}{200\ \text{s}} \;\approx\; 1080.

The "billion-fold" advantage becomes a "thousand-fold" advantage — still real, but a very different headline. This is the pattern across every advantage claim: the quantum runtime is fixed, but the classical baseline is a moving target that clever algorithms keep pushing down. An advantage claim is only ever "the best classical method we currently know is much slower" — which is why these results are provisional, not permanent.

Summary

Quantum advantage (a.k.a. quantum supremacy) means a quantum device performs a well-defined task that is infeasible for any classical computer in reasonable time;
the demonstrations use sampling tasks — random circuit sampling (Google Sycamore, 2019) and boson sampling (USTC Jiuzhang) — chosen because they are easy for the hardware to run but tied to #P-hard counting quantities, so classical simulation is believed super-polynomial (the BQP-vs-classical gap made concrete);
this is computational-complexity advantage on a contrived task — the task computes nothing useful; practical advantage on a useful problem (chemistry, optimisation) remains largely open;
the results rest on complexity assumptions, not proofs, and the classical baseline keeps improving (tensor networks, spoofing shrank Sycamore's "10,000 years" toward days), so every advantage claim is provisional and hard to verify;
honest status: sampling-based advantage has contested demonstrations; useful quantum advantage awaits better, error-corrected hardware.

Picture a runner who trains for years to sprint a course laid out in a locked warehouse: they win in record time, but the course leads nowhere and no one else wanted to run it. That is quantum advantage as demonstrated. The victory is genuine — the machine really did something a classical computer could not easily match — and it is a real scientific landmark, the first hardware evidence that the theoretical quantum/classical separation shows up in practice. But the course was chosen to be winnable, not to be worth running. Random circuit sampling and boson sampling were engineered to be classically hard, not to answer any question. The open, harder race is the one with a finish line people care about: a molecule too big to simulate classically, an optimisation no classical heuristic cracks. Nobody has won that race yet. Quantum advantage proved the runner is fast; it did not prove the race matters. Related work on quantum lower bounds studies where quantum speed-ups are provably limited — a reminder that "fast here" never means "fast everywhere."

Two traps, and they are the reason this whole topic is so easily oversold. First, "quantum supremacy/advantage" as demonstrated means a contrived, useless task — a sampling problem picked precisely because it is hard to simulate, not because anyone needs its output. It is not proof that a quantum computer beats a classical one on any useful problem; that remains open. Second, the claim rests on complexity assumptions, and the classical baseline is a moving target: improved algorithms have repeatedly chipped away at the claimed gaps (Sycamore's "10,000 years" fell to days), and verifying that a sampler really produced the right distribution is itself hard. So treat every advantage headline as provisional: "the best classical method we currently know is much slower on this artificial task" — a genuine milestone, but a world away from "quantum computers now beat classical computers."