Quantum Supremacy

Definition: The point at which a quantum computer performs a specific computation faster than any classical computer could in a practical amount of time, not necessarily a useful computation, just a demonstrably faster one.

How It Works

Requires choosing a problem specifically suited to quantum hardware’s strengths and verifiably out of reach for classical supercomputers within a reasonable time budget, usually a sampling task tied closely to the physics of the quantum device itself.
Google claimed the first demonstration in 2019 with its Sycamore processor, running a random circuit sampling problem in about 200 seconds that the team estimated would take a classical supercomputer roughly 10,000 years.
That specific 2019 claim was later disputed and narrowed: IBM argued a classical supercomputer could do it in days rather than millennia using smarter simulation techniques, and subsequent classical algorithm improvements narrowed the gap further still.
Distinct from “quantum advantage,” which specifically means outperforming classical computers on a genuinely useful, real-world problem, quantum supremacy demonstrations are deliberately engineered benchmarks, not practical applications.
The benchmark task is usually random circuit sampling: run a random but fixed sequence of gates on many qubits, then sample from the resulting probability distribution over outputs, a task that’s easy for the quantum device but requires simulating an exponentially large state vector classically.
Verifying a quantum supremacy claim classically is itself hard, since if classical verification of the full result were easy, the classical computer could arguably have solved the whole problem in comparable time, so researchers rely on statistical cross-entropy benchmarking instead.
Google’s Sycamore result was followed by other claims: China’s Jiuzhang photonic processor (2020) using Gaussian boson sampling, and University of Science and Technology of China’s Zuchongzhi superconducting processor (2021), each pushing the classical-simulation goalpost further.
The term itself, coined by physicist John Preskill in 2012, was intended narrowly and technically, but has since been criticized for implying broader dominance than any single demonstration actually shows, some researchers now prefer “quantum computational advantage” to avoid the connotation.
A supremacy claim needs three things to be credible: a task hard for known classical methods, a quantum device that can actually run it with acceptable fidelity, and some way to verify the quantum output is correct without a full classical simulation.
The classical-hardness argument typically rests on complexity-theoretic conjectures, not proofs, researchers argue that if a classical computer could efficiently simulate the sampling task, well-established complexity class assumptions would collapse in ways considered very unlikely.

Under the Hood

The core asymmetry is state-space size versus native execution:

Classical simulation cost  ~ O(2^n)   for n qubits
Quantum execution cost     ~ O(circuit depth), independent of 2^n

Given: a 53-qubit random circuit sampling task, like Google’s 2019 Sycamore experiment. Step: estimate the classical state vector’s memory footprint. Answer: 2^53 complex amplitudes, each needing 16 bytes (double-precision complex number), is roughly 1.4×10^17 bytes ≈ 140 petabytes, far beyond what any single classical supercomputer holds in memory, forcing approximate or distributed simulation techniques instead.

Given: Google’s original claim of 10,000 classical years versus IBM’s counter-estimate of a few days using disk-based classical simulation. Step: compare what changed between the two estimates. Answer: the gap wasn’t a factual dispute about the quantum hardware’s speed, it was about how cleverly the classical simulation could be engineered, using massive disk storage instead of RAM alone. This illustrates why supremacy claims are always relative to the best known classical method at the time, not a permanent, provable ceiling.

Given: a hypothetical future classical algorithm that reduces the simulation cost for a specific supremacy benchmark from O(2^n) to O(2^(n/2)). Step: apply this to the 53-qubit case. Answer: the classical cost drops from roughly 2^53 to 2^26.5 ≈ 9×10^7, suddenly tractable on an ordinary computer, this is exactly the pattern that has repeatedly narrowed or overturned specific supremacy claims after the fact.

Given: Jiuzhang’s Gaussian boson sampling task, reported at roughly 76 detected photons. Step: compare the nature of this task to Sycamore’s qubit-based random circuit sampling. Answer: both are sampling problems chosen because classical simulation scales badly, but they use entirely different physical substrates (photons versus superconducting circuits) and different classical hardness arguments (permanent-of-a-matrix computation versus state-vector simulation), showing supremacy has been pursued through multiple independent hardware paths, not just one.

Given: IBM’s 2023 “quantum utility” claim on a 127-qubit Eagle processor simulating a quantum magnetism model. Step: compare its framing to a pure supremacy claim. Answer: IBM emphasized that classical approximation methods (tensor networks) struggled to match the accuracy of the quantum result on this specific physics problem, a “utility” argument grounded in scientific value, rather than a “supremacy” argument grounded purely in classical infeasibility of an artificial benchmark.

Why It Matters

A major milestone marker for the field, though achieving it on a narrow, engineered benchmark problem is very different from quantum computers being broadly useful yet.
It’s proof-of-concept evidence that quantum hardware really does behave according to quantum mechanics at scale, rather than just being an elaborate probabilistic classical simulator in disguise.
Supremacy claims drive public and investor attention, and funding, toward the field, even though the demonstrated problems have no direct commercial application on their own.
The ongoing back-and-forth between supremacy claims and classical algorithm rebuttals has itself produced valuable classical algorithm research, better tensor network simulation methods, as a side effect.
It gives the field concrete, falsifiable milestones to argue about, rather than only vague promises, every claim invites independent verification attempts, which is a healthier scientific dynamic than unfalsifiable hype.
Supremacy debates force precise language about what “hard” and “faster” actually mean, distinguishing wall-clock time from algorithmic complexity, resource assumptions from provable limits, useful discipline for evaluating any future claim in the field.

Common Pitfalls

Interpreting a quantum supremacy claim as meaning quantum computers are now broadly better than classical ones. The demonstrated problems are usually deliberately chosen to favor quantum hardware, not representative of general-purpose computing tasks.
Assuming supremacy claims are permanent. Classical algorithms have repeatedly been improved after the fact to narrow or challenge specific claims, supremacy is a moving target relative to the best known classical method, not an absolute, timeless result.
Confusing quantum supremacy with quantum advantage. Supremacy is about beating classical computers at any task, useful or not, advantage specifically means beating classical computers at something economically or scientifically valuable.
Believing supremacy means the quantum computer solved a “hard problem” in the everyday sense, like factoring a huge number. Most supremacy benchmarks solve a problem that’s only hard because it’s specifically shaped around what quantum hardware happens to do naturally.
Treating a single supremacy demonstration as evidence that error correction or fault tolerance has been solved. Supremacy experiments run on noisy, uncorrected qubits, they demonstrate a speed advantage on a narrow task, not the broader reliability needed for general algorithms.
Assuming the classical side of a supremacy claim was run on ordinary hardware. Rebuttal estimates typically assume access to the world’s largest supercomputers, not a laptop, the comparison is always “best known quantum” versus “best known classical at similar resource scale.”
Forgetting that verification itself is a research problem. For genuinely large supremacy claims, no one, quantum or classical, can fully verify the output distribution is correct, researchers instead rely on statistical proxies like linear cross-entropy benchmarking.
Assuming the term is universally agreed upon within the field. Some researchers avoid “supremacy” entirely due to its connotations and prefer “quantum computational advantage,” the underlying technical concept is the same regardless of the label used.

Comparison

	Quantum Supremacy	Quantum Advantage	Quantum Utility
Goal	Beat classical at any task	Beat classical at a useful task	Produce results competitive with, or better than, best classical methods on real problems
Problem chosen for	Maximum classical difficulty	Real-world economic or scientific value	Practical accuracy plus speed tradeoffs
First demonstrated	2019 (Google Sycamore, disputed)	Not yet broadly achieved	Actively claimed by IBM (2023) for certain simulation tasks
Error tolerance	Uses noisy qubits directly	Likely needs lower error rates	Needs error mitigation at minimum

Notable Claims Timeline

Year	Team / hardware	Task	Status
2019	Google Sycamore, 53 superconducting qubits	Random circuit sampling	Disputed and narrowed by IBM’s classical rebuttal
2020	USTC Jiuzhang, photonic	Gaussian boson sampling	Later partially matched by improved classical algorithms
2021	USTC Zuchongzhi, 56-66 superconducting qubits	Random circuit sampling	Extended the classical simulation gap further
2023	IBM Eagle, 127 superconducting qubits	Quantum magnetism simulation	Framed as “quantum utility” rather than strict supremacy
2024	Google Willow, 105 superconducting qubits	Random circuit sampling with error correction demo	Emphasized error-rate scaling alongside speed

Why Random Circuit Sampling Was Chosen

Requirement	Why it fits random circuit sampling
Classically hard	Requires simulating an exponentially large state vector
Quantum-native	The task is literally “run this circuit and sample,” no translation overhead
Statistically verifiable	Cross-entropy benchmarking checks output quality without full classical simulation
Scalable	Circuit size and depth can be tuned to stay just past the classical frontier

Example

Google’s 2019 Sycamore processor claim is the most widely cited quantum supremacy demonstration, running random circuit sampling on 53 superconducting qubits, its practical significance remains debated, but it stands as the field’s first credible experimental claim of the milestone.

China’s University of Science and Technology built Jiuzhang, a photonic processor, and reported a Gaussian boson sampling result in December 2020 claimed to be even harder for classical computers to replicate than Sycamore’s task, using an entirely different quantum computing architecture.

IBM has pushed back on strict “supremacy” framing in favor of “quantum utility,” publishing 2023 results where its Eagle processor produced accurate simulations of certain quantum magnetism problems that classical approximation methods struggled to match, an argument for usefulness over raw classical-infeasibility bragging rights.

Google’s 2024 Willow chip revisited the same random-circuit-sampling benchmark used in 2019, but paired the speed claim with an error-correction demonstration, positioning the result as evidence toward practical fault tolerance rather than just another isolated speed record.

Referenced by

Dig deeper

Spot an error in this note?