A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Quantum supremacy (or quantum advantage) refers to a quantum computer performing a computational task that no classical computer can perform in a feasible amount of time. Google's 2019 Sycamore experiment claimed supremacy via random circuit sampling — a 53-qubit processor completed a sampling task in 200 seconds that was estimated to take 10,000 years classically. The demonstration is significant because it provides experimental evidence that quantum computational power exceeds classical, but the sampled task has no practical application. The distinction between supremacy (any task, even artificial) and practical advantage (useful tasks) remains an active frontier.
The question "can a quantum computer do something a classical computer cannot?" moved from theory to experiment in 2019, when Google's Sycamore processor performed a computation that its team estimated would take the world's most powerful supercomputer thousands of years. This event, termed quantum supremacy, was a milestone analogous to the first heavier-than-air powered flight — a proof of principle that quantum computational power is real, even though the task performed (random circuit sampling) has no practical use.
The experiment worked as follows. A 53-qubit superconducting processor executed random quantum circuits — sequences of randomly chosen one- and two-qubit gates — of depth 20. The circuit's output is a probability distribution over 253 bit strings. Because quantum interference creates complex correlations in this distribution, the output cannot be efficiently sampled by a classical computer (under plausible complexity-theoretic assumptions related to the non-collapse of the polynomial hierarchy). Google verified the quality of the quantum samples using cross-entropy benchmarking (XEB): compare the measured bit-string frequencies to the ideal probabilities (computed classically for smaller circuits) and check that the correlation exceeds what a random or trivially simulated sampler would achieve.
The supremacy claim was immediately contested. IBM argued that with 10,000 PB of disk storage, a classical supercomputer could complete the simulation in days rather than millennia. Subsequent work by classical simulation researchers has further narrowed the gap, and Chinese experiments with 60+ qubits raised the bar. The lesson is that supremacy is not a binary threshold but a moving frontier: classical algorithms improve, quantum hardware improves, and the boundary shifts. What remains robust is the asymptotic argument — classical simulation cost scales exponentially with qubit count and circuit depth, while quantum execution cost scales polynomially. At some width and depth, the crossover is inevitable.
The broader challenge is moving from supremacy to practical quantum advantage — using a quantum computer to solve a problem that matters, faster or better than the best classical approach. Candidates include quantum chemistry simulation (molecular ground states), optimization (logistics, finance), and machine learning. None have achieved unambiguous advantage on current hardware. The obstacles are noise (limiting circuit depth and fidelity), qubit count (limiting problem size), and classical competition (classical algorithms for the same problems keep improving). The NISQ era (noisy intermediate-scale quantum) is characterized by this gap between demonstrated quantum computational power and demonstrated practical utility. Bridging this gap — through better hardware, better error mitigation, or better algorithms — is the defining challenge of quantum computing in the 2020s.