Cross-Entropy Benchmarking and Verification of Sampling

Sampling from the output distribution of a deep random quantum circuit is believed to be classically intractable, and it is the task at the heart of every leading "quantum advantage" experiment. But this raises an awkward question of verification: how do you check that a noisy, imperfect device actually performed the intended sampling, when the ideal distribution it was supposed to reproduce is itself exponentially hard to write down? You cannot collect enough samples to estimate a distribution over $2^n$ strings, and you cannot compare against a target you cannot compute. Cross-entropy benchmarking is the pragmatic escape: it abandons distribution-level verification and replaces it with a single scalar — the linear cross-entropy fidelity $F_{\text{XEB}}$ — computed from the bitstrings the machine returned and a classically evaluated list of their ideal Born probabilities. The trick that makes one number carry so much is the spikiness of random-circuit output. A deep random circuit scrambles amplitudes into effectively complex Gaussians, so the ideal probabilities obey the Porter–Thomas law: most strings are improbable, but a lucky few are anomalously heavy. A faithful sampler preferentially returns those heavy strings, so the average of the ideal probability over its samples beats the flat baseline; noise smears the spikes toward uniform and the average collapses. XEB reads off how much spikiness survived. Under a global-depolarizing model, that surviving fraction is exactly the circuit fidelity — turning XEB into a tomography-free measurement of accumulated gate error. This dual identity, one statistic that is at once a hardness witness and a fidelity meter, is what made XEB the backbone of Google's Sycamore experiment, and also what makes its soundness so subtle and contested.

Key takeaways

Linear cross-entropy benchmarking (linear XEB) estimates the fidelity of a noisy random-circuit sampler by averaging the ideal output probabilities $p(x)$ over the bitstrings $x$ the hardware actually returned: $F_{\text{XEB}}=N\langle p(x)\rangle_{\text{obs}}-1$ with $N=2^n$ .
For a circuit that behaves as an approximate unitary 2-design, the ideal probabilities follow the Porter–Thomas law $\Pr(Np=z)=e^{-z}$ , fixing the two calibration constants $\langle p\rangle=1/N$ and $\langle Np\rangle_{\text{ideal}}=2$ .
The score reads $F_{\text{XEB}}\approx 1$ for a perfect sampler and $F_{\text{XEB}}\approx 0$ for the uniform (fully depolarized) distribution; under a global-depolarizing model it equals the circuit fidelity exactly.
XEB underpinned Google's 2019 quantum-supremacy claim: a $53$ -qubit, depth- $20$ circuit reached $F_{\text{XEB}}\approx 2\times10^{-3}$ with roughly a million samples — small, but many standard deviations above the statistical floor.
XEB is not a proof of quantum advantage: classical spoofing algorithms achieve nonzero $F_{\text{XEB}}$ without correct sampling, and tensor-network contractions have matched experimental scores, so its security rests on unproven average-case hardness conjectures.
Key idea: linear XEB estimates fidelity via $F_{\text{XEB}}=\langle N p(x)\rangle_{\text{observed}}-1$ , exploiting Porter–Thomas statistics so that an ideal sampler scores $\approx 1$ , the uniform distribution scores $0$ , and under global depolarizing noise the score equals the circuit fidelity.

The core insight

Linear XEB estimates fidelity via $F_{\text{XEB}}=\langle N p(x)\rangle_{\text{observed}}-1$ , leveraging Porter–Thomas statistics: an ideal sampler scores $\approx 1$ , the uniform distribution scores $0$ , and under global depolarizing noise the score equals the circuit fidelity.

Where this lives today

XEB is now the standard yardstick of the noisy-intermediate-scale era, and its story is still being written on both sides of the advantage line. On the experimental side, every superconducting supremacy claim since Sycamore — Google's later $70$ -qubit runs, and the Chinese Zuchongzhi processors — quotes a linear XEB fidelity as its headline result, and photonic Gaussian-boson-sampling machines use closely related cross-entropy tests. Beyond advantage claims, XEB has become a workhorse of device characterization: because it equals the global circuit fidelity under depolarizing noise, experimentalists fit $\log F_{\text{XEB}}$ against circuit depth to extract an effective per-cycle error that captures crosstalk and context-dependent errors invisible to isolated-gate randomized benchmarking. On the theory side it drives an active research program in average-case complexity — anticoncentration of random circuits, the average-case #P-hardness of estimating a single $p(x)$ , and the precise relationship between hardness of sampling and hardness of scoring. And it is a moving target: ever-better tensor-network contractions, with slicing and clever contraction ordering, have repeatedly closed the classical-quantum gap, turning the original " $10{,}000$ -year" estimate into days or hours and forcing each new experiment to push to larger volume. The open problem XEB crystallizes — a verification that is efficient, sound, and scalable all at once — remains unsolved, and is one of the sharpest questions in quantum computing.

The physical picture

A deep random circuit acts, on its low moments, like a Haar-random unitary. The output amplitudes $\langle x|C|0\rangle$ therefore look like independent complex Gaussians, and the probabilities $p(x)=|\langle x|C|0\rangle|^2$ inherit the Porter–Thomas distribution: their rescaled values $Np(x)$ are exponentially distributed. The consequence is a distribution that is spiky rather than flat — the typical string is unlikely, but a small population of strings carries far more than their fair share of the probability. A perfect sampler returns strings in proportion to $p$ , so it lands on the spikes disproportionately often, and averaging $p$ over its samples sits above the flat baseline. A noisy device that has forgotten the circuit returns strings uniformly at random, hitting spikes no more often than valleys, and the same average collapses to its minimum. XEB is nothing more than a calibrated reading of that difference.

Figure

Porter–Thomas statistics of a random circuit: the grey curve exp(−z) is the density of Np = N·p(x) across all 2ⁿ strings, whose mean is the uniform baseline ⟨Np⟩ = 1; the blue curve z·exp(−z) is what an ideal sampler returns, with mean ⟨Np⟩ = 2. Linear XEB reads the gap, F_XEB = ⟨Np⟩ − 1, running from 0 for a uniform device to 1 for an ideal one

There are two ways to read the same estimator, and both matter. As a correlation, $F_{\text{XEB}}=N\sum_x q(x)p(x)-1$ measures how strongly the experimental distribution $q$ overlaps the ideal $p$ — it is large exactly when the device concentrates where the ideal is heavy, and the subtraction of $1$ recenters the worthless uniform output to score zero. As a fidelity, it is even sharper: a deep noisy circuit is well modeled by the global-depolarizing state $\rho=F|\psi\rangle\langle\psi|+(1-F)I/N$ , a fraction $F$ of the ideal pure state plus a fraction $1-F$ of structureless noise. Feed that into the estimator and the identity component contributes precisely the uniform baseline that the $-1$ removes, leaving $F_{\text{XEB}}=F$ on the nose. One measured number simultaneously certifies closeness to the ideal distribution and reports the accumulated entanglement fidelity of the whole circuit — no tomography required.

Figure

Fidelity decays exponentially with circuit volume: F ≈ exp(−Σ e_g) falls about a decade every 7 cycles, so a 53-qubit depth-20 Sycamore circuit lands at F_XEB ≈ 2×10⁻³ — small but many σ above the 1/√m ≈ 10⁻³ statistical floor at m ≈ 10⁶ shots

The deep tension in the picture is that XEB silently answers two very different questions with one number: "did the device sample from something close to the ideal distribution?" and "is achieving this score classically hard?". The Porter–Thomas mathematics and the depolarizing model make the first question rigorous. The second rests on a conjecture — that no efficient classical algorithm can reach a comparable score — and that is the leg spoofing attacks kick at, engineering a cheap distribution that shares the ideal's heavy strings without ever simulating the circuit.

The core equations

Everything begins with the quantity XEB needs but cannot easily get: the ideal probability of a measured string. For a circuit $C$ on $n$ qubits initialized in $|0^{\otimes n}\rangle$ , the Born rule fixes it, and evaluating it for a generic string is the computational bottleneck of the whole scheme.

p(x)=\lvert\langle x|C|0^{\otimes n}\rangle\rvert^{2} \qquad (1)

where: $C$ — the (random) quantum circuit on $n$ qubits, regarded as a unitary; $x$ — an $n$ -bit measurement outcome; $N=2^n$ — dimension of the Hilbert space; $p(x)$ — ideal probability of $x$ , generically #P-hard to evaluate. Reading: XEB does not need the whole distribution, only $p$ evaluated on the few strings the device returned — but even one such evaluation is the hard part. When $C$ is drawn from an approximate unitary 2-design, its amplitudes behave as complex Gaussians and the rescaled probability $Np$ follows a universal law. This is the statistical engine of the benchmark: it is what makes an average over a few samples informative about a distribution over exponentially many strings.

\Pr(Np=z)=e^{-z},\qquad z=Np\ge 0 \qquad (2)

where: $z=Np(x)$ — the ideal probability rescaled by the Hilbert-space dimension; $e^{-z}$ — the Porter–Thomas density, the limiting law of $Np$ as $N\to\infty$ . Reading: the distribution of probabilities is exponential, not flat — a signature of anticoncentration and the origin of the "spikes". Two averages of $Np$ over that law calibrate the estimator. One is taken over strings drawn uniformly (the unweighted average), the other over strings drawn from the ideal distribution itself (weighted by $p$ ); they differ, and their difference is the entire signal.

\langle p\rangle=\frac{1}{N},\qquad \langle Np\rangle_{\text{ideal}}=\int_0^\infty z\,(z\,e^{-z})\,\mathrm{d}z=\int_0^\infty z^2 e^{-z}\,\mathrm{d}z=2 \qquad (3)

where: $\langle\cdot\rangle$ — unweighted (uniform) average over the $N$ strings; $\langle\cdot\rangle_{\text{ideal}}$ — average weighted by the ideal $p$ , under which $z$ is distributed as $z\,e^{-z}$ . Reading: a uniform device sees $\langle Np\rangle=1$ ; an ideal device sees $\langle Np\rangle=2$ . The factor of two is the second moment of the exponential law. The linear XEB estimator packages those constants into a fidelity-like score. It averages the ideal probability over the experimental distribution $q$ , rescales by $N$ , and subtracts the uniform baseline so the score has a clean zero.

F_{\text{XEB}}=N\,\big\langle p(x)\big\rangle_{x\sim q}-1=N\sum_x q(x)\,p(x)-1 \qquad (4)

where: $q(x)$ — the experimental (hardware) output distribution; $x\sim q$ — bitstrings drawn from the device; $F_{\text{XEB}}$ — the linear cross-entropy fidelity. Reading: $F_{\text{XEB}}$ is a rescaled overlap between $q$ and $p$ , large when the device concentrates where the ideal is heavy. In practice $q$ is never known; only $m$ sampled strings are. The empirical estimator replaces the exact average by the Monte-Carlo mean over shots, which is unbiased for $F_{\text{XEB}}$ .

\hat F_{\text{XEB}}=\frac{N}{m}\sum_{i=1}^{m}p(x_i)-1 \qquad (5)

where: $x_1,\dots,x_m$ — the $m$ measured bitstrings; $m$ — the number of shots; $\hat F_{\text{XEB}}$ — the unbiased sample estimate. Reading: you evaluate the ideal $p$ on each returned string, average, rescale, and subtract one — no distribution ever assembled. To turn the correlation into a fidelity you need a noise model. Deep random circuits are well described by global depolarization: a surviving coherent fraction $F$ on top of a fully scrambled background.

\rho_{\text{noisy}}=F\,|\psi\rangle\langle\psi|+(1-F)\,\frac{I}{N},\qquad |\psi\rangle=C|0^{\otimes n}\rangle \qquad (6)

where: $\rho_{\text{noisy}}$ — the actual output state; $|\psi\rangle$ — the ideal pure output; $F$ — the global (entanglement) fidelity; $I/N$ — the maximally mixed state. Reading: the more error accumulates, the more weight flows from the ideal state into the featureless background. That fidelity, in turn, is a product over the circuit's gates. Because independent errors multiply, $F$ shrinks exponentially with the number of gates — the reason deep-circuit fidelities are so small.

F\approx\prod_{g}(1-e_g)\approx\exp\!\Big(-\sum_g e_g\Big) \qquad (7)

where: $e_g$ — the infidelity of gate $g$ (from one- and two-qubit benchmarking, plus idle and readout errors); $\prod_g$ — the product over all operations in the circuit. Reading: with $n_g$ gates of mean error $\bar e$ , $F\approx e^{-n_g\bar e}$ — a full-stack error budget compressed into one exponential. A logarithmic variant is also common; it weights the heavy strings less aggressively and is defined so that uniform sampling scores $0$ and ideal Porter–Thomas sampling scores $1$ .

\mathrm{CE}(q,p)=-\sum_x q(x)\log p(x),\qquad F_{\text{log-XEB}}=\frac{H_0-\mathrm{CE}(q,p)}{H_0-H_{PT}} \qquad (8)

where: $\mathrm{CE}(q,p)$ — the cross entropy of the device distribution against the ideal; $H_0=\log N+\gamma$ — the uniform-distribution cross entropy, with $\gamma\approx0.5772$ the Euler–Mascheroni constant; $H_{PT}=\log N+\gamma-1$ — the value achieved by ideal sampling. Reading: the " $-1$ " separating $H_0$ from $H_{PT}$ is the Porter–Thomas entropy deficit $\langle\log z\rangle_{\text{ideal}}-\langle\log z\rangle_{\text{unif}}=1$ .

Derivation AWhy random-circuit probabilities are Porter–Thomas distributed

The goal is to establish the statistical law that makes XEB work at all: that for a circuit behaving as an approximate 2-design, the rescaled ideal probability $z=Np(x)$ is exponentially distributed, with unweighted mean $1$ and ideal-weighted mean $2$ . Everything downstream — the estimator's calibration, the fidelity identity, the sample-complexity scaling — is a corollary of these two moments, so we derive them from the Gaussian statistics of Haar-random amplitudes and check them against the normalization that any probability distribution must obey.

Step 1. Model the output state $|\psi\rangle=C|0\rangle$ as Haar-random. Each amplitude $a=\langle x|\psi\rangle$ then has real and imaginary parts that are independent Gaussians with variance $1/(2N)$ , so that the expected probability $\langle|a|^2\rangle=1/N$ matches the requirement that the $N$ probabilities sum to $1$ on average. Why: a deep random circuit reproduces Haar statistics on its low moments, and it is precisely the first two moments that XEB touches, so the Gaussian model is exact enough for the benchmark.

Step 2. Write $a=\tfrac{1}{\sqrt{2N}}(g_1+ig_2)$ with $g_1,g_2\sim\mathcal N(0,1)$ . Then $2Np=g_1^2+g_2^2$ is a chi-squared variable with two degrees of freedom, i.e. exponential with mean $2$ ; equivalently $z=Np$ has density $e^{-z}$ with unweighted mean $\int_0^\infty z\,e^{-z}\,\mathrm{d}z=1$ . Why: the sum of two squared Gaussians is the simplest exponential, and this is the mathematical root of the "spiky" distribution — a few strings with large $z$ , exponentially many with small $z$ .

Step 3. Compute the ideal-weighted mean. When strings are drawn from $p$ itself, a string of rescaled value $z$ appears with probability proportional to $p\propto z$ times the number of such strings $\propto e^{-z}$ , so under ideal sampling $z$ is distributed as $z\,e^{-z}$ . Its mean is $\langle Np\rangle_{\text{ideal}}=\int_0^\infty z\,(z\,e^{-z})\,\mathrm{d}z=\int_0^\infty z^2 e^{-z}\,\mathrm{d}z=2$ . Equivalently $\langle Np\rangle_{\text{ideal}}=N\sum_x p^2=N\cdot(2/N)=2$ , i.e. $N$ times the collision probability. Why: the same collection of probabilities looks different depending on how you sample it, and this reweighting from $e^{-z}$ to $z\,e^{-z}$ — mean $1$ to mean $2$ — is the entire signal XEB detects.

Step 4. Fix the trivial constant. The unweighted average of $p$ is $\langle p\rangle=\tfrac1N\sum_x p(x)=\tfrac1N$ exactly, for any distribution, because probabilities sum to one. Hence a uniform device gives $N\langle p\rangle=1$ regardless of the circuit. Why: this pins the zero of the estimator — the " $-1$ " in $F_{\text{XEB}}$ is calibrated against this model-independent baseline, so a scrambled device scores exactly zero.

Go deeper · Derivation B · 1 minXEB equals fidelity under global depolarizing noise

Derivation BXEB equals fidelity under global depolarizing noise

The goal is to show that when the device state is the global-depolarizing mixture, feeding it through the linear XEB estimator returns exactly the depolarizing fidelity $F$ — the result that promotes XEB from a mere correlation test into a tomography-free measurement of accumulated gate error. We take the device distribution to be the diagonal of $\rho_{\text{noisy}}$ , insert it into the estimator, split the sum into an ideal piece and a uniform piece, and apply the two Porter–Thomas moments derived above to collapse everything to a single number.

Step 1. The device distribution is the Born diagonal $q(x)=\langle x|\rho_{\text{noisy}}|x\rangle=F\,p(x)+(1-F)\tfrac1N$ , since the maximally mixed component $I/N$ contributes the uniform value $1/N$ to every string. Why: depolarizing noise cleanly separates into a coherent copy of the ideal distribution and a structureless flat background, which is exactly the convex form the estimator can dissect.

Step 2. Insert into the estimator: $F_{\text{XEB}}=N\sum_x\big(F\,p(x)+\tfrac{1-F}{N}\big)p(x)-1$ . Why: substituting the model directly is legitimate because $F_{\text{XEB}}$ is linear in $q$ , so the mixture passes straight through.

Step 3. Split the sum: $F_{\text{XEB}}=F\,N\sum_x p(x)^2+(1-F)\sum_x p(x)-1$ . The second sum is exactly $1$ by normalization. Why: linearity lets the ideal and uniform contributions be evaluated independently, and one of them is a constant we already know.

Step 4. Apply the Porter–Thomas moment $N\sum_x p(x)^2=\langle Np\rangle_{\text{ideal}}\to 2$ from the previous derivation. Why: this is the only place the circuit's random structure enters — the collision probability of a spiky distribution is twice that of a flat one.

Step 5. Combine: $F_{\text{XEB}}=F\cdot 2+(1-F)\cdot 1-1=F$ . The ideal term contributes $2F$ , the uniform term $1-F$ , and the recentering $-1$ leaves exactly $F$ . Why: the algebra is engineered so the constants cancel — the " $2$ " from spikiness and the " $-1$ " recentering conspire to strip everything but the fidelity.

Go deeper · Derivation C · 1 minHow many shots resolve a small XEB score

Derivation CHow many shots resolve a small XEB score

The goal is to estimate the number of samples needed to distinguish a small $F_{\text{XEB}}$ from statistical noise, which explains why supremacy-scale experiments collect on the order of a million bitstrings per circuit. The estimator averages the random variable $Y=Np(x)$ over shots, so its uncertainty is set by the per-shot variance of $Y$ divided by the shot count; we evaluate that variance with the Porter–Thomas moments and impose a signal-to-noise condition.

Step 1. The per-shot variance is $\mathrm{Var}(Y)=\langle(Np)^2\rangle-\langle Np\rangle^2$ with $Y=Np(x)$ , $x\sim q$ . For a low-fidelity device $q$ is close to uniform, so both moments are governed by the Porter–Thomas statistics of $p$ . Why: near the noise floor — exactly where resolution is hard — the device samples almost uniformly, so the relevant statistics are those of $p$ under uniform sampling.

Step 2. Evaluate the moments: $\langle(Np)^2\rangle_{\text{unif}}=N\sum_x p(x)^2\to 2$ and $\langle Np\rangle_{\text{unif}}=1$ , giving $\mathrm{Var}(Y)\approx 2-1=1$ . Why: the variance is $O(1)$ per shot, independent of $n$ — the crucial fact that lets a fixed number of samples work at any system size.

Step 3. The estimator variance is $\mathrm{Var}(\hat F_{\text{XEB}})=\mathrm{Var}(Y)/m\approx 1/m$ , so the standard error is $\sigma\approx 1/\sqrt m$ . Why: independent shots average down as $1/\sqrt m$ , the familiar Monte-Carlo rate, with no hidden dimension factor.

Step 4. Impose resolution at $k$ standard deviations: $F_{\text{XEB}}/(1/\sqrt m)\ge k\Rightarrow m\gtrsim k^2/F_{\text{XEB}}^2$ . For $F_{\text{XEB}}\approx 2\times10^{-3}$ and $k\approx 5$ , this is $m\gtrsim 25/(4\times10^{-6})\approx 6\times10^{6}$ shots — the order of magnitude actually used. Why: the $1/F^2$ scaling is unforgiving, and it is why halving the fidelity quadruples the required samples, driving supremacy experiments into the millions of shots.

Limiting cases

Case	Result	Meaning
Noiseless ideal sampler	$F_{\text{XEB}}=N\langle p\rangle_{p}-1=N\cdot\tfrac{2}{N}-1=1$	samples drawn from $p$ itself give $\langle Np\rangle=2$ by Porter–Thomas, so the score saturates at $1$
Uniform / fully depolarized	$F_{\text{XEB}}=N\langle p\rangle_{\text{unif}}-1=N\cdot\tfrac{1}{N}-1=0$	averaging $p$ over random strings returns the mean $1/N$ , so the centered score vanishes
Global depolarizing, fidelity $F$	$F_{\text{XEB}}=F\cdot 1+(1-F)\cdot 0=F$	a convex mix of ideal and uniform yields XEB equal to the depolarizing fidelity — the basis of XEB-as-metrology
Finite samples $m$	$\mathrm{Var}(\hat F_{\text{XEB}})\approx\tfrac{1}{m}\big(\langle(Np)^2\rangle-\langle Np\rangle^2\big)\sim\tfrac1m$	$O(1)$ per-shot variance means $\sim 1/F_{\text{XEB}}^2$ shots resolve a small score; $F\sim10^{-3}$ needs $\sim10^6$
Shallow / non-anticoncentrated circuit	Porter–Thomas fails; $\langle Np\rangle_{\text{ideal}}\ne 2$	too little depth leaves the distribution un-spiky, breaking the calibration constant and the fidelity identity

Common trapA positive XEB score proves neither correct sampling nor classical hardness

It is tempting to read $F_{\text{XEB}}>0$ as a certificate of quantum advantage. It is not. First, XEB measures only the correlation $N\sum_x q(x)p(x)-1$ , and many distributions $q$ unequal to $p$ produce the same score — a classical spoofer that reproduces the heavy strings of $p$ while ignoring the rest can post a nonzero score without ever sampling correctly. Second, XEB equals the fidelity only under the assumed global-depolarizing model; correlated or coherent errors can make the two diverge. Third, the hardness claim is not that simulating the circuit is hard but that achieving the score is hard — a strictly stronger, unproven, average-case conjecture. Treating XEB as a proof of advantage ignores the #P-hardness of genuine verification and the growing catalogue of spoofing and tensor-network attacks that reach experimental scores classically.

Worked examples

1 · The Sycamore fidelity budget (fully worked)

Google's Sycamore circuit uses roughly $1113$ single-qubit gates, $430$ two-qubit gates, and $53$ readouts, with mean errors $e_1\approx 0.16\%$ , $e_2\approx 0.62\%$ , and $e_{\text{ro}}\approx 3.8\%$ . Predict the linear XEB fidelity from the digital error model, and compare to the reported $F_{\text{XEB}}\approx 2\times10^{-3}$ .

Step 1. Sum the error budget, $\sum_g e_g$ , contribution by contribution. Single-qubit gates give $1113\times 0.0016=1.78$ ; two-qubit gates give $430\times 0.0062=2.67$ ; readout gives $53\times 0.038=2.01$ . The total is $\sum_g e_g\approx 1.78+2.67+2.01=\mathbf{6.46}$ .

Step 2. Convert to fidelity with equation (7): $F\approx\exp(-\sum_g e_g)=\exp(-6.46)=\mathbf{1.6\times10^{-3}}$ . Because the errors are independent and each factor $(1-e_g)$ is close to one, the product and its exponential approximation agree to better than a percent.

Step 3. Interpret. Under the global-depolarizing model $F_{\text{XEB}}=F$ , so the digital error model predicts a score near $1.6\times10^{-3}$ , the same order of magnitude as the measured $2\times10^{-3}$ — the residual gap is absorbed by details of the error model and circuit compilation. The dominant single contributor is the two-qubit gate budget, which is why supremacy engineering fights hardest to lower $e_2$ . Predicted F_XEB ≈ 1.6×10⁻³, consistent with the measured ≈ 2×10⁻³, and two-qubit gates dominate the loss.

2 · How many bitstrings to call it (fully worked)

A device posts $F_{\text{XEB}}\approx 2\times10^{-3}$ . How many samples are needed to resolve this at five standard deviations, and what does that imply about the classical verification cost?

Step 1. Use the sample-complexity result $m\gtrsim k^2/F_{\text{XEB}}^2$ with $k=5$ . Then $m\gtrsim 25/(2\times10^{-3})^2=25/(4\times10^{-6})=\mathbf{6.25\times10^{6}}$ shots — a few million bitstrings, matching the $0.5$ – $3$ million per circuit actually collected.

Step 2. Account for the standard error. With per-shot variance $\approx 1$ , the uncertainty on $\hat F_{\text{XEB}}$ at $m=6.25\times10^6$ is $\sigma=1/\sqrt m\approx 4\times10^{-4}$ , so the score sits $F/\sigma\approx 5$ standard deviations above zero — statistically resolvable but not comfortable.

Step 3. Fold in the hidden cost. Every one of those samples requires a classical evaluation of $p(x_i)=|\langle x_i|C|0\rangle|^2$ , and each such amplitude is generically #P-hard. For $53$ qubits this took world-class supercomputing; the cost does not scale, so XEB cannot verify arbitrarily large experiments. Need m ≈ 6×10⁶ shots for 5σ, each demanding a #P-hard amplitude — the verification, not the sampling, is what breaks first.

Physics of the portrait

Cross-entropy benchmarking is a young idea built on an old one. Its statistical backbone was forged in nuclear physics decades before anyone imagined a quantum computer, and its rise as a verification tool tracks the sudden, contested arrival of quantum advantage.

Origins · 1 mincross-entropy benchmarking and how this was discovered

cross-entropy benchmarking

the sampling-fidelity witness F_XEB = ⟨N p(x)⟩ − 1 · verification of quantum advantage

The mathematical heart of XEB predates it by more than sixty years. In 1956 Charles Porter and Robert Thomas, studying the widths of nuclear resonances, proposed that the relevant amplitudes were Gaussian random variables, so that intensities followed an exponential law — the Porter–Thomas distribution, which random-matrix theory later placed at the center of quantum chaos. When Sergio Boixo, John Martinis, Hartmut Neven and collaborators at Google set out to demonstrate quantum supremacy, they recognized that a deep random circuit produces exactly this statistics, and that its spikiness could be turned into a verification tool: average the ideal probability over the measured strings, and the Porter–Thomas moments calibrate the answer into a fidelity. Their 2018 analysis of characterizing supremacy, and the 2019 Sycamore experiment, made $F_{\text{XEB}}$ the reported figure of merit for the first claimed advantage. Almost immediately the complexity theorists pushed back on its meaning: Scott Aaronson and Lijie Chen had already laid out the complexity-theoretic foundations of such experiments, Adam Bouland, Bill Fefferman, Chinmay Nirkhe and Umesh Vazirani proved worst-to-average-case reductions aiming to ground the hardness, and Aaronson with Sam Gunn showed that spoofing linear XEB is itself a delicate question — efficiently spoofable in some regimes, conjecturally hard in others. XEB thus sits exactly on the fault line between what quantum devices can do and what we can prove they do: a fidelity meter that works beautifully, wrapped around a hardness claim that remains open.

History

1956

— Porter and Thomas fit nuclear resonance widths with random-Gaussian amplitudes, giving the exponential intensity law

2016

— cross-entropy benchmarking is proposed as a fidelity witness for random-circuit sampling

2018

— Boixo and colleagues characterize quantum supremacy and the role of anticoncentration

2019

— Google's Sycamore reports F_XEB ≈ 2×10⁻³ on 53 qubits, claiming quantum supremacy

2020

— Aaronson and Gunn analyze the classical hardness of spoofing linear XEB

2022

— tensor-network contractions reproduce Sycamore-scale XEB scores at modest classical cost

Going further

References. Arute et al., "Quantum supremacy using a programmable superconducting processor", Nature 574, 505 (2019) · Boixo et al., "Characterizing quantum supremacy in near-term devices", Nature Physics 14, 595 (2018) · 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) · Aaronson & Gunn, "On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking", Theory of Computing 16 (2020) · Preskill, "Quantum computing and the entanglement frontier", arXiv:1203.5813 · Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed., Ch. 8. The Porter–Thomas moments ( $\langle p\rangle=1/N$ , $\langle Np\rangle_{\text{ideal}}=2$ , exponential law $e^{-z}$ ) follow from Gaussian-amplitude statistics; the ideal-weighted mean evaluates as $\int_0^\infty z^2 e^{-z}\,\mathrm{d}z=2$ , and the log-XEB deficit is $\langle\log z\rangle_{\text{ideal}}-\langle\log z\rangle_{\text{unif}}=(1-\gamma)-(-\gamma)=1$ . The XEB-equals-fidelity identity follows from $\rho=F|\psi\rangle\langle\psi|+(1-F)I/N$ and the same moments. Sycamore figures: $53$ qubits, depth $20$ , $F_{\text{XEB}}\approx 2\times10^{-3}$ , $\sim10^6$ samples, error budget $\sum_g e_g\approx 6.5\Rightarrow F\approx1.6\times10^{-3}$ .

Builds on: The Complexity Class BQP · BQP is Contained in PP and PSPACE · BQP versus P, NP, and PSPACE. Leads to: Quantum Query Complexity · The Polynomial Method for Quantum Lower Bounds · BQP is Contained in PP and PSPACE.

Ask the tutor: Ask me to walk through why the number 2 turns into a fidelity, or to show how a tensor-network spoofer could post a Sycamore-level XEB score without ever running the circuit.

Why not just compare the full output distributions instead of using one number?

Because you cannot even write down the ideal distribution, let alone estimate the experimental one. The ideal distribution lives over $2^n$ strings — for $53$ qubits that is about $9\times10^{15}$ probabilities — so no realistic number of samples could estimate the device's distribution well enough to compare. Worse, each ideal probability is #P-hard to compute. XEB sidesteps both problems by never assembling a distribution: it evaluates the ideal probability only on the few million strings the machine returned, and compresses the comparison into a single expectation value. That is a genuine trade — you lose the ability to detect many kinds of error, but you gain a statistic that is actually computable from feasible data.

What is anticoncentration and why does XEB need it?

Anticoncentration is the property that a random circuit's output probability is not too concentrated on a few strings — formally, that a constant fraction of the total probability sits on strings whose $p(x)$ is at least of order $1/N$ . Porter–Thomas statistics are a strong form of it. XEB needs anticoncentration because its calibration constant $\langle Np\rangle_{\text{ideal}}=2$ is exactly the (rescaled) collision probability of the ideal distribution, and that equals $2$ only when the distribution is spiky in the Porter–Thomas sense. A circuit too shallow to anticoncentrate has a different constant, so the fidelity identity $F_{\text{XEB}}=F$ silently breaks. This is why supremacy circuits are run at enough depth to reach the 2-design regime.

How can XEB measure fidelity without any tomography?

The magic is the global-depolarizing model plus the Porter–Thomas moment. Full tomography would require reconstructing the density matrix, which needs exponentially many measurements. XEB instead assumes the noisy state is a coherent fraction $F$ of the ideal plus a fully mixed background. When you feed that mixture into the estimator, the ideal part contributes $2F$ (via the collision-probability moment), the mixed part contributes $1-F$ , and the recentering $-1$ leaves exactly $F$ . So a single expectation value returns the fidelity — but only to the extent the depolarizing model holds. Coherent errors, leakage, or strong correlations violate the model, and then XEB and the true fidelity part ways.

What exactly is a spoofing attack on XEB?

A spoofer is a classical algorithm that posts a nonzero $F_{\text{XEB}}$ without honestly sampling the circuit. The estimator rewards any distribution that overweights the heavy strings of $p$ , so a spoofer only needs to find and preferentially output some high-probability strings — not reproduce the full distribution. Aaronson and Gunn showed this is a genuine tension: in some regimes (few queries to the circuit, or particular noise assumptions) spoofing is provably easy, while in others it is conjectured hard. Tensor-network methods are a related threat: they compute enough amplitudes cheaply to match the experimental score. Both erode the claim that a given XEB score certifies quantum advantage, which is why the field treats XEB as a moving benchmark rather than a proof.

Is the linear XEB score ever allowed to exceed 1 or go negative?

Yes, though only within statistical fluctuations for a well-behaved device. The population value is bounded: a perfect sampler gives $1$ and the uniform distribution gives $0$ , with the depolarizing model interpolating linearly. But the empirical estimate $\hat F_{\text{XEB}}=\tfrac{N}{m}\sum_i p(x_i)-1$ is a finite average of a heavy-tailed variable, so a single fortunate string with a large $p(x_i)$ can push a small-sample estimate above $1$ , and an unlucky batch of low-probability strings can push it slightly below $0$ . As $m$ grows the estimate concentrates on the true value with standard error $\approx 1/\sqrt m$ . Scores far outside $[0,1]$ signal either a calibration bug or a device whose noise is not depolarizing.

Why does the log-XEB variant exist if linear XEB already works?

The two weight the heavy strings differently, which changes their statistical behavior. Linear XEB averages $Np(x)$ , so a single very heavy string can dominate the sum — the estimator is unbiased but has fatter tails. Logarithmic XEB averages $\log p(x)$ , taming those tails and often giving a lower-variance estimate, at the cost of a slightly more involved calibration (the constants $H_0=\log N+\gamma$ and $H_{PT}=\log N+\gamma-1$ that make uniform score $0$ and ideal score $1$ ). In practice both are reported; linear XEB has the cleaner fidelity interpretation under depolarizing noise, while log-XEB is sometimes preferred for its estimator stability. The Euler constant $\gamma$ appearing in its calibration is just $-\langle\log z\rangle$ for the exponential law.