Quantum Algorithms Database
Random Circuit Sampling
A computational task used to demonstrate 'quantum supremacy' — sampling outputs from a deliberately complex, randomly generated quantum circuit.
Year
2019 (Google demonstration)
Inventor(s)
Google Quantum AI team
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
The Problem
Generating samples from the probability distribution produced by a large random quantum circuit — a task believed exponentially hard to simulate classically.
How It Works
Runs a circuit of random quantum gates across many qubits, then measures the output, repeating many times to build a statistical sample of the underlying probability distribution.
Real-World Impact
Has no direct practical application — its significance was purely as a benchmark demonstrating quantum hardware capability, and the 'supremacy' claim was later contested by improved classical simulations.