127
Part Three · B · Algorithms

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 nn qubits produces each of the N=2nN = 2^n bit strings with probability p(x)p(x). These probabilities are not uniform: they follow the Porter–Thomas distribution, first seen in nuclear physics, in which NpNp 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 Np=1Np = 1. 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 x1,…,xkx_1,\dots,x_k from the device, compute their ideal probabilities classically (possible only for circuits small enough, or by extrapolation), and form

FXEB=N ⟨p(xi)⟩−1F_\text{XEB} = N\,\langle p(x_i)\rangle - 1

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 1/k1/\sqrt k. 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.

What does F_XEB measure?tap
How strongly the device’s samples favour strings that are heavy in the ideal distribution: 1 ideal, 0 uniform noise.
Why are boson-sampling probabilities hard?tap
They are squared permanents, and computing permanents is #P-hard.
How did classical methods spoof the 2019 result?tap
Tensor-network contraction, aiming only at the low fidelity the device actually reached.

And one to work out. Over many samples, the average of N p(xi)N\,p(x_i) is 1.002. What is FXEBF_\text{XEB}?

F =

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.

Next · Chapter 128
BQP, BPP, QMA, and their relationships

Where do quantum computers sit among the problem classes? Two walls are proven. Everything else is open.

Turn the page