What Is Quantum Supremacy?

The Concept and Its Origins

Theoretical physicist John Preskill coined the term "quantum supremacy" in 2012 to describe the point at which a quantum device performs a computational task that is beyond the reach of any classical computer. The term was deliberately chosen to be striking, though Preskill has noted that "quantum advantage" may be more appropriate since "supremacy" implies a broader dominance that quantum computers do not have. Quantum computers are not better than classical computers at most tasks; they are dramatically better at a narrow set of specific computations.

The theoretical foundation for quantum supremacy rests on computational complexity theory. Certain sampling problems, where the goal is to generate random samples from a specific probability distribution, are believed to be exponentially hard for classical computers but efficiently solvable by quantum computers. The key insight is that simulating a random quantum circuit on a classical computer requires tracking 2^N complex amplitudes for an N-qubit circuit. For 50+ qubits, this exceeds the memory capacity of any existing supercomputer, and the time required grows exponentially with qubit count. A quantum computer performs this sampling naturally, because its qubits physically implement the quantum state evolution.

The critical word in the previous paragraph is "believed." No one has proven that classical computers cannot efficiently simulate random quantum circuits. The belief rests on the widely assumed conjecture that the polynomial hierarchy of complexity classes does not collapse, a foundational assumption in computer science that would have sweeping consequences if false. This means quantum supremacy claims are inherently conditional: they demonstrate that a quantum computer outperforms all known classical algorithms, not all possible classical algorithms. A breakthrough in classical simulation could, in principle, invalidate a supremacy claim, which is exactly what happened, partially, with Google's 2019 result.

Google's Sycamore Experiment

In October 2019, Google published a paper in Nature claiming quantum supremacy using their 53-qubit Sycamore processor (one of the chip's 54 qubits was defective). The experiment involved applying a random sequence of single-qubit and two-qubit gates to the qubits, creating a deeply entangled quantum state, and then measuring all qubits to produce a bit string. This process was repeated millions of times to collect a statistical sample of the output distribution. The quantum processor completed the sampling task in 200 seconds.

Google estimated that the world's most powerful classical supercomputer at the time, Summit at Oak Ridge National Laboratory, would require approximately 10,000 years to perform the same computation using the best known classical simulation algorithm. The classical simulation would need to store and manipulate 2^53 complex numbers (roughly 72 petabytes at full precision), far exceeding Summit's 250 petabytes of storage, and perform a number of floating-point operations that would take millennia at Summit's peak performance.

The result was validated by comparing the quantum processor's output distribution to theoretically predicted values. The metric used was the linear cross-entropy benchmark (XEB), which measures how well the observed bit string frequencies match the ideal (noiseless) output distribution. A fully random (classical) sample would achieve an XEB score of 0, while a perfect quantum computation would achieve 1. Sycamore achieved an XEB score of approximately 0.002 for the full 53-qubit circuits, indicating that while the output was very noisy, it was measurably closer to the ideal quantum distribution than random guessing could achieve.

The Classical Pushback

IBM challenged Google's supremacy claim within days of its publication. IBM researchers argued that Summit could actually perform the simulation in 2.5 days rather than 10,000 years by using a different classical algorithm that traded computational time for disk storage. By storing intermediate results on Summit's 250 petabytes of disk rather than holding the full state vector in memory, the simulation becomes feasible, though still enormously expensive. IBM did not actually run this simulation, but their analysis demonstrated that the gap between quantum and classical capability was narrower than Google initially claimed.

In subsequent years, multiple research groups developed improved classical simulation algorithms that further reduced the estimated classical time. A team from the Chinese Academy of Sciences proposed a tensor network contraction algorithm that could simulate the Sycamore experiment in about 15 hours on a large GPU cluster. Another group showed that by exploiting the noise in the quantum processor (which reduces the effective entanglement), approximate classical simulations become much easier. By 2022, multiple groups claimed to have reproduced Google's results with similar fidelity using classical computers, though the definitions of "same fidelity" and the fairness of the comparisons were debated.

This pattern of claim and counter-claim illustrates a fundamental challenge of quantum supremacy: the goalposts move. When a quantum experiment is performed, classical algorithm researchers have strong motivation to develop better simulation methods. Each improvement to classical simulation raises the bar for quantum supremacy, pushing the quantum community to build larger, more capable processors. The competition has been productive for both fields, driving advances in both quantum hardware and classical simulation algorithms.

Beyond Sycamore: Other Supremacy Experiments

The University of Science and Technology of China (USTC) performed a photonic quantum supremacy experiment in 2020 using their Jiuzhang processor. Instead of a gate-based circuit, Jiuzhang implemented Gaussian boson sampling, where photons pass through a network of beam splitters and are detected at the output. The team reported that Jiuzhang generated samples in 200 seconds that would take a classical supercomputer 2.5 billion years to produce. Boson sampling is believed to be classically hard under different complexity-theoretic assumptions than random circuit sampling, providing independent evidence for quantum computational advantage.

USTC followed up with Jiuzhang 2.0 in 2021 (113 detected photons) and Zuchongzhi 2.1, a 66-qubit superconducting processor that performed random circuit sampling with higher fidelity than Sycamore. IBM's Eagle processor (127 qubits, 2021) and subsequent Heron processors have demonstrated increasing qubit counts, though IBM has focused less on supremacy demonstrations and more on demonstrating useful quantum computations through their utility experiments.

Google's 2023 Willow processor (105 qubits) combined a supremacy demonstration with the first below-threshold error correction experiment. The random circuit sampling task performed by Willow was estimated to require 10^25 years of classical computation, a much larger gap than Sycamore achieved, because the larger qubit count and better gate fidelities made classical simulation exponentially harder. The error correction demonstration showed that increasing the surface code distance from 3 to 5 to 7 progressively reduced the logical error rate, validating the threshold theorem experimentally for the first time.

Supremacy vs Practical Advantage

All quantum supremacy experiments to date have demonstrated advantage on artificial problems designed to be hard for classical computers. Random circuit sampling has no practical application. Boson sampling computes a quantity (the permanent of a matrix) that is mathematically interesting but has limited real-world use. The pressing question for the field is when quantum computers will demonstrate advantage on problems that people actually need to solve.

Practical quantum advantage requires solving a useful problem faster, cheaper, or more accurately than the best available classical method. Candidates include simulating molecules for drug discovery, optimizing supply chains, training machine learning models, and breaking cryptographic codes. None of these have been demonstrated yet because they require either more qubits, better error rates, full error correction, or some combination. The gap between supremacy on artificial tasks (achieved) and advantage on practical tasks (not yet achieved) represents the central challenge for the quantum computing field in the current decade.

Some researchers distinguish between "quantum advantage" (outperforming classical methods on a useful task) and "quantum utility" (providing some tangible benefit from a quantum computation, even if a classical computer could eventually do the same). IBM has promoted the concept of quantum utility, demonstrating that their quantum processors can compute certain properties of condensed matter systems with accuracy that matches or approaches the best classical methods, even if the classical methods are still feasible. This framing acknowledges that the path from supremacy to practical advantage may involve a gradual transition where quantum and classical methods are competitive rather than a sudden moment when quantum clearly wins.