Quantum supremacy

Quantum supremacy is the demonstration that a quantum computer can perform a computational task that no classical computer can perform in a feasible amount of time. The term was coined by John Preskill in 2012 and achieved experimentally by Google in 2019 with their Sycamore processor, which performed random circuit sampling on 53 qubits in 200 seconds — a task they claimed would take a classical supercomputer thousands of years. The achievement is not about solving a useful problem; random circuit sampling has no practical application. It is about establishing a computational phase transition: the point at which quantum systems become large enough and coherent enough that classical simulation is not merely slow but exponentially infeasible. The debate over whether this milestone has truly been reached is ongoing: IBM argued that classical simulation with better memory management could reduce the classical time, and the definition of supremacy itself is contested. The deeper question is whether supremacy is a meaningful category or merely a publicity milestone on the path to quantum advantage — the demonstration of a quantum computer solving a commercially or scientifically relevant problem better than classical alternatives. The field is currently in the awkward interregnum between supremacy and advantage, with no clear path from one to the other.

See also: Quantum Computing, Quantum Information Theory, Computational Complexity Theory, Random Circuit Sampling, Boson Sampling, Quantum Advantage == The Phase Transition Reading ==

The term "supremacy" is misleading. It suggests a permanent dominance, a crossing of a threshold after which quantum computers are always faster. This is not what the experimental demonstrations show. What they show is a computational phase transition in a specific regime: a narrow window of problem size, circuit depth, and error rate where quantum hardware outperforms the best known classical algorithms. The window is not stable. Classical algorithms improve. Quantum hardware scales. The boundary moves.

This is the systems insight: quantum supremacy is not a state but a dynamic boundary, a moving frontier in the space of computational problems, hardware capabilities, and algorithmic knowledge. The 2019 Google claim was a snapshot of this frontier at a specific moment. IBM's rebuttal was a push on the classical side. The 2020 Chinese photonic demonstration was a push on the quantum side. Neither was a final answer. Both were data points in a race that has no finish line because the race itself changes the terrain.

The phase transition framing is not merely metaphorical. The transition from classically simulable to classically intractable is a genuine phase transition in the computational complexity of quantum circuit simulation, analogous to the transition from ferromagnetic to paramagnetic behavior in the Ising model. Below a critical circuit depth (relative to qubit count), tensor network contraction methods can simulate the circuit efficiently. Above that depth, the entanglement structure becomes too complex for any known classical method. The critical depth is not a universal constant; it depends on the architecture, the gate set, and the connectivity. The transition is therefore a function of the system's parameters, not a property of quantum mechanics itself.

The Interregnum Problem

The field's current state — the "awkward interregnum between supremacy and advantage" — is not a temporary embarrassment. It is a structural condition. The gap between supremacy and advantage is the gap between demonstrating that quantum systems can do something classical systems cannot and demonstrating that quantum systems can do something useful better than classical alternatives. The first is a physics problem. The second is an engineering problem with economic constraints.

The physics problem is nearly solved. We have multiple experimental demonstrations that quantum devices can perform classically intractable sampling tasks. The engineering problem is unsolved and may remain so for decades. The useful problems — quantum chemistry, optimization, cryptanalysis — require error correction, which requires millions of physical qubits for thousands of logical qubits. Current devices have hundreds of physical qubits. The gap is not a matter of incremental improvement. It is a matter of orders of magnitude.

The interregnum is therefore not a transition period between two stable states. It is a protracted regime where the field must justify its funding without delivering its promises. The danger is that the hype around supremacy will collapse into disillusionment before the engineering for advantage is complete. The history of technology is full of such collapses: the AI winters of the 1970s and 1980s, the nanotechnology bubble of the 2000s, the blockchain hype of the 2010s. Quantum computing is vulnerable to the same pattern. The supremacy demonstrations are real but narrow. The advantage demonstrations are distant but necessary. The interregnum is the period where the gap between them is most dangerous.

The Terminology Debate

John Preskill, who coined the term, has expressed regret. "Supremacy" carries unfortunate racial and political connotations, and it overstates the achievement. The alternative terms — "quantum advantage," "quantum primacy," "quantum milestone" — are attempts to find language that is both accurate and unproblematic. "Advantage" is already used for the practical demonstration. "Primacy" sounds like a temporal claim. "Milestone" is too vague.

The terminology problem is not merely semantic. It reflects the field's uncertainty about what it has actually achieved. A supremacy claim is a claim about classical intractability, which is a statement about computational complexity theory. But complexity theory deals with asymptotic limits, not finite experiments. The claim that a 53-qubit random circuit is classically intractable is not a theorem. It is a conjecture based on the best available algorithms and hardware. The terminology debate is therefore a debate about epistemic status: is the field making scientific claims or engineering claims? The answer is both, and the confusion between them is the source of much controversy.

The debate over quantum supremacy is not a scientific dispute with a correct answer. It is a boundary dispute in a shifting landscape. The boundary between classical and quantum computation is not a line in the sand but a tide that moves with the moon of algorithmic progress and hardware scaling. The 2019 and 2020 demonstrations are not proof of permanent quantum dominance. They are proof that the tide has moved, and that the beach is smaller than it was before. Whether the tide will continue to rise or whether a storm of classical innovation will push it back is the open question that defines the field.