Key facts
- Quantum advantage (earlier called quantum supremacy) means a programmable quantum computer solving a problem that no classical computer can solve in feasible time, whether or not the problem is useful.
- John Preskill introduced the term in a 2011 talk, published as an arXiv paper in 2012.
- Candidate tasks are random circuit sampling and boson sampling; their hardness rests on complexity theory, not on a proof.
- Google's 2019 Sycamore experiment claimed 200 seconds versus 10,000 years, and IBM answered that a classical machine could do it in days.
- Any claim can be temporary, because classical algorithms keep improving.
Quantum advantage is the demonstration that a programmable quantum computer can solve a problem that no classical computer can solve in feasible time, whether or not the problem is useful. The older name is quantum supremacy. Several experiments since 2019 have claimed it, and several of those claims have been challenged by faster classical simulations. This note defines the term, explains the tasks used to test it and the complexity-theory argument behind them, and sets out why such a claim is hard to settle. The experiments themselves are examined in part 2, considering the evidence. It belongs to the science notes.
The definition
English Wikipedia describes quantum supremacy as the goal of showing that a programmable quantum computer solves a problem which no classical computer can solve in feasible time, irrespective of the usefulness of the problem. It is a scientific goal, not a commercial one. The experiment can be done with near-term devices, because it needs no error correction, only a circuit large and clean enough that classical simulation becomes impractical.
The term comes from John Preskill. His arXiv paper 1203.5813, Quantum computing and the entanglement frontier, was a rapporteur talk at the 25th Solvay Conference, held from 19 to 22 October 2011, and was posted in March 2012. Its abstract uses the phrase “quantum supremacy”, in quotation marks, for the point at which a quantum computer can run an algorithm that solves a problem with a super-polynomial speedup relative to classical computers. Preskill later wrote the remembrance of a colleague that is cited in the note on Mark Wise.
The phrase “quantum advantage” is now widely used for the same milestone. This note treats the two terms as synonyms.
Which tasks can show it
A test task has to satisfy three conditions: a quantum device can run it, a classical computer should find it hard, and the result should be checkable. The tasks proposed so far favor the first two conditions.
| Task | Idea | Where the hardness comes from |
|---|---|---|
| Random circuit sampling | Run a random sequence of quantum gates on many qubits and sample the output bitstrings | Simulating the full quantum state of n qubits needs memory and time that grow exponentially with n |
| Boson sampling | Send identical photons through a network of beam splitters and record where they emerge | The output probabilities involve permanents of complex matrices, which are #P-hard to compute |
| IQP sampling | Sample from a restricted family of quantum circuits | Complexity-theory arguments similar to those above |
Boson sampling was introduced by Aaronson and Arkhipov, after earlier work by Troyansky and Tishby. It is a non-universal model: it needs only single-photon sources, a linear interferometer and detectors, not a full quantum computer. Wikipedia notes that boson sampling with enough loss and noise can be simulated efficiently, which is why experiments aim for high photon numbers and low loss. The Gaussian variant used by later experiments is covered in part 2.
The complexity argument
Why should these tasks be hard for classical machines? Wikipedia summarizes the main argument. If a classical algorithm could efficiently sample the output of arbitrary quantum circuits, the polynomial hierarchy, a tower of complexity classes, would collapse to its third level. Most complexity theorists consider that collapse unlikely, so efficient classical sampling is taken to be unlikely too.
This is evidence, not proof. The argument covers exact or near-exact sampling, while real devices are noisy and produce approximate samples. For random circuit sampling, Bouland, Fefferman, Nirkhe and Vazirani gave additional evidence of hardness in 2018. Wikipedia also notes that factoring with Shor’s algorithm has the opposite problem: the answer is easy to verify classically, but running it for large numbers is beyond today’s machines.
The verification problem
A sampling experiment returns a long list of random-looking bitstrings. Checking it is itself costly. In the Google experiment, the team could not simulate the full circuit in reasonable time, so it relied on a benchmark that compares measured samples with the ideal distribution. Wikipedia describes random circuit sampling as being used as a system-level benchmark of a quantum device.
This creates an uncomfortable asymmetry. The harder the task, the harder it is to confirm that the device did it correctly. Part 2 describes how the benchmark was later used by classical simulators as a target to beat.
The 2019 experiment as a first case
In 2019, a Google team published in Nature an experiment on a 53-qubit superconducting processor, Sycamore. The paper’s title uses the word supremacy. It reports that the state space of the processor is about 2 to the power 53, roughly 10 to the power 16, that a million samples took about 200 seconds, and that the team estimated the same task would take about 10,000 years on the best classical supercomputer.
IBM disputed the estimate. Its counter-claim, in the Wikipedia summary, was that the circuit could be simulated on the Summit supercomputer in about 2.5 days by using disk storage. Whether 2.5 days counts as “feasible” is part of the disagreement. If it does, the claim fails on the strict wording of the definition. If it does not, it holds, but with a much smaller margin than 10,000 years. The later history, including a 2022 classical simulation, is covered in part 2.
Why a claim can be temporary
Wikipedia states that quantum supremacy may be temporary, because classical algorithms improve. A claim compares one quantum device with the best classical method known on the day. When a better classical method appears, the margin shrinks, and in some cases it disappears. Wikipedia gives a recent example: a 2024 claim by D-Wave of supremacy for dynamics of spin systems was questioned by later tensor network studies.
A claim should therefore be read with five questions:
- What exactly was the task, and was the output verified?
- How was the classical cost estimated, and by whom?
- Has any classical simulation since reduced that cost?
- Does the task have any use beyond the benchmark?
- Does the hardware have enough noise that the output is nearly classical anyway?
The difference from usefulness
None of this says that a quantum computer solves a practical problem faster. A demonstration of advantage on sampling shows that the machine does something hard to imitate, which is a precondition for useful quantum computing, not a delivery of it. Quantum technology also includes sensors that already work in the field, covered in quantum cartography. The statistical physics behind noise and information is the subject of entropy and the arrow of time.
About the image
The image shows an IBM Quantum System One at the ThinkLab of IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York. IBM’s group is the one that disputed the 2019 classical-time estimate for Sycamore, as described above, and the photograph illustrates the kind of superconducting machine involved in these debates.
Frequently asked questions
What is quantum advantage?
It is the demonstration that a quantum computer can perform a task that no classical computer can perform in a feasible amount of time. The task need not be useful. The older name for the same milestone is quantum supremacy.
Who coined the term quantum supremacy?
John Preskill, in a 2011 rapporteur talk at the 25th Solvay Conference, published on arXiv in 2012 as Quantum computing and the entanglement frontier. He used it for the point at which a quantum computer solves a problem with a super-polynomial speedup over classical computers.
Does quantum advantage mean quantum computers are useful now?
No. The tasks used so far, such as random circuit sampling, were chosen because they are hard for classical machines and fit a near-term device, not because the output solves a practical problem.
Why is quantum advantage hard to prove?
Sampling tasks are hard to verify, since the answer is a list of random-looking outcomes. Also, a claim about what classical computers cannot do is always open to a better classical algorithm, so a result can be weakened after publication.
Sources and open data
- Quantum computing and the entanglement frontier, arXiv
- Quantum supremacy using a programmable superconducting processor, Nature
- Quantum supremacy, English Wikipedia
- Boson sampling, English Wikipedia
- Sycamore processor, English Wikipedia