Applications
Random Circuit Sampling
A computational task involving sampling outputs from a deliberately complex random quantum circuit, used to demonstrate quantum supremacy claims.
Definition
Random circuit sampling refers to the task of generating samples from the probability distribution produced by running a large, randomly generated quantum circuit, then measuring the result. This specific task was the basis of Google's 2019 quantum supremacy claim using its Sycamore processor.
In depth
Random circuit sampling is the benchmark behind the quantum supremacy experiments. A quantum processor runs a circuit made of randomly chosen gates and measures all of its qubits, producing a bit string. Repeating this many times gives samples from a probability distribution that is believed to be very hard for classical computers to reproduce. The task has no practical use, and that is by design: it is the simplest task a noisy quantum chip can do that a classical computer is expected to struggle with.
Verification is done by cross-entropy benchmarking. For circuits small enough to simulate, the ideal probabilities are computed classically and compared with the samples, and the fidelity is extrapolated to larger circuits. Google's 2019 Sycamore experiment used 53 qubits and 20 cycles, with a measured fidelity near 0.2 percent, and its 2024 Willow experiment used 103 qubits at depth 40, completing in under five minutes against a classical estimate of 10 to the 25 years. USTC's Zuchongzhi processors followed with 66 and later 105 qubits.
The classical side has not stood still. Tensor network contraction on GPU clusters and methods that exploit the noise in the experiments have reduced the estimated classical cost of earlier circuits by orders of magnitude, and Aharonov and coauthors showed in 2022 that noisy random circuit sampling becomes classically easy asymptotically if the noise per gate is constant. The debate shows that the claim of advantage is always relative to the best classical algorithm known, and that hardware needs both more qubits and lower error to stay ahead.
Technical Definition
The task is believed to be exponentially hard for classical computers to simulate as circuit size grows, though the precise boundary of this hardness has shifted as classical simulation algorithms have improved, leading to ongoing debate about specific supremacy claims.
Visual Explanation: An Analogy
Think of random circuit sampling like a complex, randomly shuffled deck of cards — predicting the exact resulting order (the equivalent of classically simulating the circuit) becomes harder as the deck size grows, even though dealing the cards (running the actual circuit) stays straightforward.
Key facts
| Item | Detail |
|---|---|
| Sycamore (2019) | 53 qubits, 20 cycles, about 200 s of sampling |
| Willow (2024) | 103 qubits, depth 40, under 5 minutes versus an estimated 10^25 years classically |
| USTC Zuchongzhi | 66 qubits in 2021 and 105 qubits in 2025 |
| Verification | Linear cross-entropy benchmarking with classical simulation of smaller circuits |
| Caveat | Noisy versions are asymptotically classically easy (Aharonov et al., 2022) |
Where the idea comes from
Boixo and coauthors proposed random circuit sampling as a supremacy experiment in 2018, and Google carried it out in 2019. Later experiments scaled it up and prompted work in classical simulation.
Real-World Use Cases
- The specific task underlying Google's 2019 and subsequent quantum supremacy demonstrations
- Used as a benchmark task in independent verification studies, like those covered in our Research Papers section
How it differs from related ideas
- Random circuit sampling is a sampling task, while Shor's algorithm solves a decision or search problem.
- Boson sampling is the photonic analogue.
- A useful advantage task would have a verifiable, meaningful output, which random circuits lack.
Frequently asked questions
What is random circuit sampling?
A benchmark in which a quantum chip runs random circuits and its output samples are compared with the ideal distribution, to show a beyond-classical computation.
Is it useful?
Not for practical applications. It is a test of hardware and of computational hardness.
Has it been spoofed classically?
Classical methods have reduced the cost estimates for earlier experiments, which is why claims are always compared with the latest classical algorithms.
Related Terms
Keep exploring
- Algorithm: Random Circuit Sampling (Quantum Supremacy Experiments)
- Algorithm: Boson Sampling
- Hardware: Google Sycamore
- Hardware: Google Willow