Random Circuit Sampling

RCS is the live proving ground of the quantum-advantage program, and it moves in both directions. On the hardware side, superconducting processors have pushed past Sycamore's 53 qubits: USTC's Zuchongzhi devices scaled deeper, Google's 2023 study mapped a phase transition in RCS at 70 qubits, and its 2024 Willow chip ran RCS on 105 qubits while demonstrating below-threshold error correction — the advantage and fault-tolerance frontiers converging on one device. On the classical side the counterattack is just as vigorous: Pan and Zhang's tensor-network contractions computed correlated Sycamore samples on GPU clusters, closing much of the original time gap, and Pauli-path algorithms exploit the very noise that limits hardware to spoof XEB — matching a low-fidelity device's score without simulating its full distribution. This cat-and-mouse has a constructive descendant: because XEB is unverifiable at very large $n$, researchers now pursue cryptographically verifiable quantum advantage and interactive proofs of quantumness, where a classical verifier certifies quantum behavior efficiently — RCS thus lives on as benchmark, stress test, and the seed of verifiable quantum computation.

Read one amplitude $\langle x|U|0\rangle$ as a coherent sum over every path through the depth-$d$ circuit — roughly $2^{n\cdot d}$ interfering complex terms. A classical algorithm that wants the value of that amplitude is stuck adding those terms with no shortcut, because the sum is as hard as counting solutions to a $\#\mathrm{P}$ problem. The quantum device never computes the sum; it lets the physical evolution perform the interference and reads off one sample. The first figure fixes the object.

Anticoncentration is the promise of "no cheap heavy bitstrings." If a handful of strings carried most of the probability, a classical adversary could enumerate them and score well without simulating anything. A scrambling circuit forbids that: the rescaled weights $y=Np(x)$ look like independent draws from $e^{-y}$, so about $1/e\approx0.37$ of all strings sit above the mean and no small heavy set exists to exploit. That statistical flatness is exactly what cross-entropy benchmarking measures. The second figure is the diagnostic an experimentalist plots: the Porter–Thomas law.

Underneath the statistics runs a fidelity ledger. Each two-qubit gate of error $\epsilon$ multiplies the surviving fidelity by roughly $(1-\epsilon)$, so after $g$ operations the coherent weight is $F\sim e^{-\epsilon g}$. The experiment must keep $F$ above the level where classical algorithms — whose cost scales with the fidelity they must match — become cheaper than the quantum sampler. Every gain in gate quality raises $F$; every classical advance lowers the bar. RCS is the scoreboard for that contest.

The definition is the Born rule applied to a random unitary: prepare $|0\rangle^{\otimes n}$, apply $U$, and the probability of reading $x$ is the squared amplitude. The difficulty is entirely in the word random and in the size $2^n$ of the outcome space.

where: $U$ — random circuit unitary on $n$ qubits; $x$ — measured bitstring in $\{0,1\}^n$; $|0^{\otimes n}\rangle$ — all-zero input; $p(x)$ — Born probability. Reading: the "answer" is not any one $x$ but the whole profile $\{p(x)\}$, which a classical rival must reproduce. For a scrambling ensemble, $|\psi\rangle=U|0\rangle$ behaves like a Haar-random state and the individual probabilities are exponentially distributed. This is the Porter–Thomas law, imported from mid-century nuclear physics, and it is the statistical backbone of everything downstream.

where: $N=2^n$ — Hilbert-space dimension; $\Pr(p)$ — density of probabilities over the ensemble; $p$ — one probability $p(x)$. Reading: rescaling to $y=Np$ gives the parameter-free law $\Pr(y)=e^{-y}$ with mean and variance both $1$. Because the full distribution is unverifiable, certification uses the linear cross-entropy benchmark. One draws device samples, evaluates the ideal probabilities on those strings, averages, and rescales.

where: $q$ — the distribution the device really samples; $p(x)$ — ideal probability computed classically; $\mathbb{E}_{x\sim q}$ — empirical average over samples; $\mathcal{F}_{\mathrm{XEB}}$ — $1$ ideal, $0$ uniform. Reading: a device that emits high-$p$ strings more often than chance scores above zero — it "knows" where the ideal mass sits. Real hardware samples not from $p$ but from a noisy mixture. A well-tested model treats accumulated noise as global depolarization: the ideal state survives with weight $F$, otherwise replaced by the uniform state.

where: $F$ — global circuit fidelity; $e_g$ — Pauli error of operation $g$ (gate, idle, or readout); $\mathbb{1}/2^n$ — uniform component. Reading: fidelity is multiplicative, decaying exponentially in circuit size. Substituting the depolarizing model into the benchmark gives the identity that makes XEB useful. Under this noise the benchmark reports the fidelity itself, so a few million samples buy a number otherwise inaccessible.

where: the coherent piece uses $\sum_x p(x)^2=2/2^n$ and the incoherent piece uses $\sum_x p(x)=1$. Reading: cross-entropy on a scrambling circuit is a near-direct readout of global fidelity. The hardness claim is conditional. An efficient classical sampler for $p$ would place a $\#\mathrm{P}$-hard quantity low in the polynomial hierarchy, which — by Toda's theorem — forces the whole hierarchy to collapse.

where: $\mathrm{PH}$ — polynomial hierarchy; $\Sigma_3^p$ — its third level. Reading: complexity theorists regard $\mathrm{PH}$ collapse as essentially impossible, so its contrapositive is the evidence for hardness. Finally, the leading classical attack is tensor-network contraction. Its cost is governed by the treewidth of the circuit's contraction graph, not by the qubit count $n$ alone.

where: $\mathrm{tw}(G)$ — treewidth of the contraction graph $G$; $C_{\mathrm{TN}}$ — contraction cost. Reading: shallow or thin circuits have small treewidth and are easy; hardness demands depth and 2D connectivity.

Whether RCS is hard or trivial depends sharply on depth, geometry, and noise. Each row is a regime where either the hardness argument or the classical-simulation cost changes character.

1 · The Sycamore fidelity budget (fully worked)

A superconducting processor runs a random circuit on $n=53$ qubits for 20 cycles, using about $1113$ single-qubit gates, $430$ two-qubit gates, and $53$ terminal readouts. With representative Pauli error rates $e_1=0.15\%$, $e_2=0.62\%$, and $e_r=3.6\%$, predict the global fidelity and the expected XEB.

Step 1. Fidelity is multiplicative, so work with the summed error budget $\sum_g e_g$. Single-qubit contribution: $1113\times0.0015=\mathbf{1.670}$.

Step 2. Two-qubit contribution: $430\times0.0062=\mathbf{2.666}$. Readout contribution: $53\times0.036=\mathbf{1.908}$. The entanglers and one-shot readout dominate — each an order of magnitude noisier than a single-qubit rotation, which is why they, not single-qubit control, set the scale.

Step 3. Total budget $\sum_g e_g=1.670+2.666+1.908=\mathbf{6.244}$. The predicted fidelity is $F\approx e^{-6.244}=\mathbf{1.9\times10^{-3}}$, about $\mathbf{0.19\%}$.

Step 4. By $\mathcal{F}_{\mathrm{XEB}}\approx F$, the device should score $\mathcal{F}_{\mathrm{XEB}}\approx0.2\%$ — small but resolvable, consistent with the measured Sycamore value of $\mathbf{0.224\%}$. A per-gate error near $0.6\%$ on the entanglers, compounded over hundreds of gates, pins the whole experiment at a fraction of a percent fidelity.

2 · How flat is Porter–Thomas, and how many samples to see it

For a scrambling circuit, what fraction of bitstrings are "heavy" (probability above the mean $2^{-n}$), how much probability do they carry, and roughly how many samples are needed to resolve an XEB of $0.2\%$ above zero?

Step 1. Heavy strings satisfy $y=Np>1$. Their fraction is $\int_1^\infty e^{-y}\,\mathrm{d}y=e^{-1}=\mathbf{0.368}$. About $37\%$ of all $2^n$ strings sit above average — heaviness is a bulk property, not a few spikes.

Step 2. The probability mass those heavy strings carry is $\int_1^\infty y\,e^{-y}\,\mathrm{d}y=2e^{-1}=\mathbf{0.736}$. Roughly $37\%$ of the strings hold $74\%$ of the mass — a mild, spread-out concentration nothing can enumerate.

Step 3. The single-sample estimator $2^n p(x_i)-1$ has variance of order unity, so the standard error after $N_s$ samples is $\sim1/\sqrt{N_s}$. Resolving $F\approx2\times10^{-3}$ needs $N_s\gtrsim1/F^2\approx\mathbf{2.5\times10^{5}}$ at minimum, and $\sim25/F^2\approx6\times10^{6}$ for a confident $5\sigma$ separation. Sycamore collected about $3\times10^{6}$ samples — squarely in this range — which is why a $0.2\%$ fidelity could be certified at all.

RCS is where three strands of twentieth-century thought converge: Feynman's intuition that quantum systems resist classical simulation, the complexity theory of counting, and the mid-century statistics of chaotic quantum spectra. The portrait is of the idea itself — quantum computational advantage — and the people who turned a slogan into a falsifiable experiment.

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniv. ed.), Ch. 4 (circuits) and Ch. 12 (complexity) · Preskill, Lecture Notes on Quantum Computation, Ch. 6 and the quantum-supremacy supplements · Watrous, The Theory of Quantum Information, Ch. 7 (distinguishability) · Wilde, Quantum Information Theory (2nd ed.), Ch. 3 (Haar measure, typicality) · Kitaev, Shen, Vyalyi, Classical and Quantum Computation, Ch. 8 (complexity classes) · Mermin, Quantum Computer Science (measurement and sampling).

Papers. Arute et al., "Quantum supremacy using a programmable superconducting processor," Nature 574, 505 (2019) · Aaronson & Chen, "Complexity-Theoretic Foundations of Quantum Supremacy Experiments," CCC (2017) · Bouland, Fefferman, Nirkhe, Vazirani, "On the complexity and verification of quantum random circuit sampling," Nature Physics 15, 159 (2019) · Bremner, Jozsa, Shepherd (2010) and Aaronson, Arkhipov (2011) for the sampling-hardness template. Three results underpin the article's core claims. First, the Porter–Thomas density $\Pr(y)=e^{-y}$ with $\langle y\rangle=1$, $\mathrm{Var}(y)=1$, and $\sum_x p(x)^2=2/2^n$ follows from the chi-squared(2) law of Haar-random amplitudes. Second, the XEB endpoints $\mathcal{F}_{\mathrm{XEB}}=1$ (ideal) and $0$ (uniform), and the identity $\mathcal{F}_{\mathrm{XEB}}=F$ under depolarizing noise, use $\sum_x p^2=2/2^n$. Third, the $\mathrm{PH}$-collapse chain $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}\subseteq\Sigma_3^p$ follows via Toda's theorem and Stockmeyer counting. The Sycamore figures ($n=53$, 20 cycles, $\mathcal{F}_{\mathrm{XEB}}\approx0.2\%$, $\sim3\times10^6$ samples) are experimental; the worked fidelity budget uses representative error rates and reproduces the measured $0.224\%$ to one significant figure. The anticoncentration constant $\alpha=2$ follows from the Porter–Thomas second moment.

Prerequisites. Quantum Circuit Model · Computational Complexity (P, NP, #P, PH) · Haar Measure and Unitary Designs · Magic State Distillation. Leads to. Boson Sampling · Quantum Supremacy / Advantage Experiments · Tensor Network Simulation · Topological Quantum Computation.

Ask the tutor: Want to see why unit variance in the Porter–Thomas histogram is the exact fingerprint of a scrambling circuit — and how a spoofing algorithm sneaks a high XEB without it? Ask me to walk through it.