Sampling advantage: random circuit sampling and boson sampling
In October 2019 Google announced that its 53-qubit Sycamore processor had, in 200 seconds, sampled from a random quantum circuit, a task it estimated would take the world’s best supercomputer 10,000 years. IBM replied within days that 2.5 days would do. By 2022 a Chinese group had spoofed the result classically in hours. Then the quantum machines grew, and the bar moved again. This is the story of “quantum supremacy”, or quantum advantage: what was claimed, how it is measured, and why the scoreboard keeps changing.
On the plate: what the output of a random circuit looks like, and how to score it.
Porter–Thomas
A random circuit on qubits produces each of the bit strings with probability . These probabilities are not uniform: they follow the Porter–Thomas distribution, first seen in nuclear physics, in which is exponentially distributed. Some strings are several times likelier than average, most are less likely. A noisy device that outputs uniform random strings gives every string . The plate compares the two. The speckle-like structure is the fingerprint of quantum interference, and computing which strings are heavy appears to need exponential classical effort. Established
Cross-entropy benchmarking
Draw samples from the device, compute their ideal probabilities classically (possible only for circuits small enough, or by extrapolation), and form
A perfect device gives 1, because Porter–Thomas weighting doubles the mean; uniform noise gives 0. Mix in noise with fidelity 0.30 and draw 3.50 (log₁₀) samples from a 12-qubit Porter–Thomas distribution, then . The estimate tracks the fidelity, with statistical error about . Sycamore’s 2019 XEB was about 0.002: tiny, but detectable with millions of samples. Established
Boson sampling, and a moving scoreboard
Scott Aaronson and Alex Arkhipov proposed in 2011 sending photons through a random linear-optical network: output probabilities are permanents of matrices, which are #P-hard to compute, and approximate sampling is hard unless the polynomial hierarchy collapses, under plausible conjectures about anticoncentration. Jiuzhang, at USTC in China, did a Gaussian version with up to 76 detected photons in 2020.
The classical side keeps answering. Feng Pan, Keyang Chen and Pan Zhang spoofed Sycamore’s 2019 samples in 2022 with tensor-network contraction, exploiting its low fidelity. The quantum side moved: Google’s 105-qubit Willow chip did a harder random circuit sampling task in under five minutes in 2024, estimated at 10²⁵ classical years, and USTC’s Zuchongzhi 3.0 used 83 qubits over 32 cycles in 2025. Random circuit sampling has no known use; its role is to test whether quantum devices do something classical computers cannot. Each claim is a snapshot in a contest. Debated
What you now have
Random circuit sampling, the Porter–Thomas distribution, the cross-entropy benchmark, boson sampling and the hardness of permanents, and the history of claims and classical counter-claims.
· · ·
Three questions to carry with you.
And one to work out. Over many samples, the average of is 1.002. What is ?
Sources: F. Arute et al., Nature 574, 505 (2019). S. Aaronson and A. Arkhipov, Theory Comput. 9, 143 (2013) (STOC 2011). H.-S. Zhong et al., Science 370, 1460 (2020). F. Pan, K. Chen and P. Zhang, Phys. Rev. Lett. 129, 090502 (2022). Google Quantum AI, Willow announcement (December 2024). D. Gao et al., Phys. Rev. Lett. 134, 090601 (2025). Checked by code: 12-qubit Porter–Thomas sampling gives XEB 0.97 ideal and 0.30 at fidelity 0.3 with 20,000 samples.