Algorithm Zoo · Sampling
Random Circuit Sampling
Also known as: RCS, Quantum supremacy benchmark
First described: Boixo et al. (theory); Google Quantum AI (Sycamore experiment), 2019
The problem
Sample from the output distribution of a random quantum circuit.
Run a depth-D random Clifford+T-like circuit on n qubits, sample the output bitstring distribution. Classical simulation conjectured to require time exponential in n at fixed depth, supporting a complexity-theoretic argument for quantum advantage on this task.
Best classical
Tensor-network simulation, with several efficient variants developed since 2019.
Quantum complexity
O(1) per sample on hardware (a single circuit run).
Our verdict
The benchmark that gave us 'quantum supremacy' headlines and the years-long classical chase to invalidate them. Useful as a hardware diagnostic (XEB) and as a complexity-theory exercise; useless as an application. Every claim should be read with a sunset-by-2026 expectation.
When to use it
- Benchmarking quantum hardware — cross-entropy benchmarking (XEB) is a standard fidelity metric.
- Complexity-theory work — the task is the cleanest known candidate for asymptotic separation in NISQ.
When not to use it
- Anything you'd actually want a sampler for. The output distribution has no known use.
- Practical advantage claims — every 'supremacy' headline (Sycamore 2019, USTC 2021, Sycamore 2024) has been challenged by improved classical simulations within ~1 year.
Classical baseline
Pan & Zhang (2022) simulated the 2019 Sycamore experiment in 15 hours on a Sunway supercomputer. Liu et al. (2021) Jiuzhang photonic claims similarly dented by classical tensor-network methods (Oh et al. 2023). The arms race is ongoing.
Hardware cost
n qubits, depth ~20 for the 2024 Sycamore experiment at 67 qubits. XEB fidelity drops exponentially with circuit volume — careful calibration mandatory.
Key papers
- Quantum supremacy using a programmable superconducting processor ↗
Arute et al. (Google AI) · 2019 · Nature
- Solving the sampling problem of the Sycamore quantum supremacy circuits ↗
Pan, Zhang · 2022 · Phys. Rev. Lett.
Last verified: 2026-05-24