Cross-Entropy Benchmarking

Cross-entropy benchmarking (XEB) scores a device on random circuit sampling: run a random circuit many times, then ask whether the observed bitstrings are biased toward the outputs the ideal circuit makes likely. It is both a practical calibration tool (per-gate-pair XEB is core to Google’s tune-up workflow) and the headline metric of the 2019 quantum supremacy experiment.

How it works

For a random circuit on n qubits, ideal output probabilities follow the exponential (Porter–Thomas) distribution, so a perfect device samples “heavy” bitstrings noticeably more often than chance. The linear cross-entropy fidelity is

F_XEB = 2^n · ⟨ p_ideal(x) ⟩ − 1

where the average runs over the bitstrings x the device actually produced, and p_ideal is computed by classical simulation. A perfect device gives F_XEB ≈ 1; a device emitting uniform noise gives F_XEB ≈ 0. Under a white-noise (depolarizing) model, F_XEB estimates total circuit fidelity, and small variants of the estimator trade statistical efficiency for robustness. The Cirq XEB documentation walks through the theory and a reference implementation.

Strengths and limitations

XEB works on circuits far too entangled for tomography and needs only sampled bitstrings plus classical simulation — which is also its central limitation: computing p_ideal is exponentially hard, so XEB is directly verifiable only up to circuit sizes a classical supercomputer can still simulate. Beyond that regime, quoted fidelities rest on extrapolation.

The metric’s adversarial robustness is an active research area. Tensor-network “spoofing” results, notably Pan, Chen & Zhang (2022), cut the classical cost of matching Sycamore’s XEB scores by orders of magnitude, and later theoretical work showed that under a constant noise rate, polynomial-time classical algorithms can achieve nontrivial XEB values. High XEB on its own is therefore weaker evidence of quantum advantage than originally hoped, though it remains a standard, sensitive full-stack calibration signal.

Notable results

Google’s 53-qubit Sycamore processor reported F_XEB ≈ 0.2% at depth 20 in the 2019 Nature experiment — small in absolute terms, but statistically far from classical spoofing baselines at the time. Follow-up random-circuit-sampling experiments by Google (67–70 qubits, 2023–24) and USTC’s Zuchongzhi processors pushed the verifiable and extrapolated regimes further while the classical-simulation frontier advanced in parallel.