Random Circuit Sampling (Quantum Supremacy Experiments)

Overview

Random circuit sampling, or RCS, is a task designed to be hard for classical computers and feasible for a noisy quantum computer. The quantum chip applies a long sequence of randomly chosen gates to its qubits and then measures all of them, producing a bit string. Repeating this many times gives samples from a probability distribution that classical computers can reproduce only with enormous effort.

RCS has no known practical use. Its purpose is to test whether a device can do something beyond the reach of classical simulation, which is why it is the basis of the quantum supremacy and quantum advantage claims made by Google in 2019 and 2024, and by Chinese groups in 2021 and 2025.

The problem it solves

Generating samples from the probability distribution produced by a large random quantum circuit — a task believed exponentially hard to simulate classically.

History and background

The theory was developed by Sergio Boixo, Sergei Isakov, Vadim Smelyanskiy, Ryan Babbush, Hartmut Neven, John Martinis, and colleagues, who described in a 2018 Nature Physics paper how random circuits on a two-dimensional qubit grid could demonstrate supremacy and how to verify the result using cross-entropy benchmarking. In October 2019 Google published the first experiment on its 53-qubit Sycamore processor, claiming 200 seconds of quantum sampling versus an estimated 10,000 years classically. IBM and others disputed the classical estimate.

In 2021 and 2022 the University of Science and Technology of China reported experiments on its Zuchongzhi processors with up to 66 qubits, and in 2025 a 105-qubit Zuchongzhi 3.0 result. Google's 2024 Willow experiment used 103 qubits with circuits of depth 40 and reported a computation time under five minutes against a classical estimate of 10 to the 25 years. Meanwhile, tensor network simulations and a 2022 theoretical result by Aharonov and colleagues showed that noisy RCS becomes easy classically in the large-system limit if the noise per gate stays constant, which shaped later experimental design.

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.

A random quantum circuit scrambles the initial state so thoroughly that the output probabilities look like those of a random state. The probability of each bit string follows the Porter-Thomas distribution, with a few very likely outcomes and many unlikely ones. Predicting those probabilities for a large circuit is believed to require resources that grow exponentially with the number of qubits, because the entanglement spreads through the whole chip.

The quantum chip, by contrast, produces samples directly. The difficulty is verification: a classical computer cannot check that the samples follow the ideal distribution. Google's method is linear cross-entropy benchmarking, which asks how often the experiment's samples land on bit strings that the ideal circuit says are likely. This is evaluated on smaller circuits where classical simulation is possible and extrapolated to the largest ones.

The fidelity is low. In the 2019 experiment the overall signal was about 0.2%, which means the output was mostly noise with a small quantum component, but enough samples revealed it statistically. The claim of hardness rests on the idea that even this noisy signal cannot be reproduced efficiently by classical means.

Step by step

1. Choose a layout of qubits on the chip and a circuit depth, in cycles.
2. For each cycle, apply a random single-qubit gate from a small set to each qubit, followed by a fixed two-qubit gate on pairs in a pattern that covers the grid.
3. Measure all qubits to obtain a bit string, and repeat the same circuit millions of times to collect samples.
4. Simulate the same circuit classically for smaller sizes or with simplified versions to compute the ideal probability of each observed bit string.
5. Compute the linear cross-entropy benchmark by comparing the average ideal probability of the observed bit strings to the uniform value.
6. Extrapolate the classical cost of verifying and simulating the full circuit, and compare with the quantum run time to state the advantage.

A worked example

On a chip with 53 qubits and 20 cycles, each qubit receives about 20 random single-qubit gates and the chip applies roughly 430 two-qubit gates. The measured cross-entropy benchmark fidelity was about 0.002, meaning the output is correlated with the ideal distribution at about two parts per thousand. With a million samples, that small correlation is clear above statistical noise.

The cost of classical simulation for exactly this circuit was originally estimated at about 10,000 years, but IBM suggested 2.5 days using disk storage, and later tensor-network methods reported hours or less on large GPU clusters. This back-and-forth illustrates how the classical baseline shapes the claim.

Complexity and resources

What hardware it needs

• A 2D array of 50 to 100+ qubits with high-fidelity single- and two-qubit gates and fast readout.
• Very uniform performance across all qubits, since average fidelity determines the signal.
• Large-scale classical simulation resources for benchmarking and validation.

Applications

• Demonstrating computational advantage and benchmarking hardware progress.
• Generating certified random numbers, in protocols proposed by Aaronson and demonstrated with Quantinuum hardware in 2025.
• Testing quantum complexity theory, such as conjectures about the hardness of sampling.

Limitations and caveats

• The task has no known practical application, and the output is noise-dominated.
• Classical algorithms keep improving, so claims are revised.
• Theory suggests that at constant noise rates, RCS becomes classically tractable for large enough systems, so devices need improving error rates as they grow.

Common misconceptions

• RCS does not show that a quantum computer can solve useful problems faster. It shows a beyond-classical computation on an artificial task.
• Quantum supremacy does not mean the quantum computer can break encryption.
• The 10,000 years and 10 to the 25 years figures are estimates for specific algorithms and can change.

How it compares

• Boson sampling is a similar sampling-based advantage test with photons.
• Quantum Echoes and other verifiable-advantage experiments aim for tasks with checkable and physically meaningful answers.
• Shor's algorithm shows an advantage on a useful problem but needs fault-tolerant hardware.

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.

Why it matters

RCS marks the transition from the claim that quantum computers might be faster to experiments that test it. It has driven improvements in qubit quality and in classical simulation, and the arguments about it have clarified what counts as evidence of advantage.

It is also a reminder to read advantage claims carefully: what is the task, what is the classical baseline, how was the result verified, and what happens as classical algorithms improve.

Frequently asked questions

Keep learning

• Related algorithm: Boson Sampling
• Related algorithm: Quantum Error-Correcting Codes (Shor Code, Surface Code)
• Related algorithm: Quantum Error Mitigation Techniques
• Related algorithm: Shor's Algorithm

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database