Cross-Entropy Benchmarking

Cross-entropy benchmarking (XEB) is a technique for quantifying how faithfully a quantum processor executes a given circuit. It works by running a random circuit on the quantum hardware, collecting the output distribution, and comparing it to the ideal output distribution computed via classical simulation. The comparison metric, called the linear cross-entropy fidelity, provides a single number between 0 and 1 that indicates how well the quantum output matches the ideal. Google used XEB as the primary validation method in their 2019 quantum supremacy experiment with the Sycamore processor.

The linear cross-entropy fidelity

Given a random quantum circuit $C$ acting on $n$ qubits, let $p(x) = |\langle x | C | 0\rangle|^2$ be the ideal probability of measuring bitstring $x$. The processor runs the circuit $N$ times and collects bitstrings $x_1, x_2, \ldots, x_N$. The linear XEB fidelity is:

$F_{\text{XEB}} = 2^n \cdot \frac{1}{N} \sum_{i=1}^{N} p(x_i) - 1$

Intuitively, if the processor produces bitstrings with high ideal probability (meaning it correctly amplifies the “peaks” in the output distribution), $F_{\text{XEB}}$ is close to 1. If the processor outputs uniformly random bitstrings (complete noise), the average of $p(x_i)$ is $1/2^n$, giving $F_{\text{XEB}} = 0$. A perfect processor gives $F_{\text{XEB}} = 1$.

The factor of $2^n$ and the subtraction of 1 normalize the metric so that it ranges from 0 (no signal) to 1 (perfect execution). This normalization relies on the Porter-Thomas distribution of output probabilities for random circuits: for Haar-random circuits on $n$ qubits, the ideal probabilities $p(x)$ follow an exponential distribution with mean $1/2^n$.

Connection to quantum supremacy

In Google’s 2019 experiment, the Sycamore processor (53 qubits) executed random circuits with depth 20 and achieved $F_{\text{XEB}} \approx 0.002$. While this fidelity seems low, the key claim was that computing the same output distribution classically would require approximately 10,000 years on the world’s fastest supercomputer, while the quantum processor completed the task in 200 seconds.

The argument structure is:

1. For shallow circuits (small depth), both the quantum processor and classical simulation can compute the output. The measured $F_{\text{XEB}}$ matches the predicted fidelity based on individual gate error rates, validating the benchmark.
2. As circuit depth increases, classical simulation becomes intractable, but the per-gate fidelity model predicts what $F_{\text{XEB}}$ should be.
3. If the measured $F_{\text{XEB}}$ matches the prediction at the largest depths (where classical verification is infeasible), this provides evidence that the quantum processor is correctly executing the circuit.

How XEB relates to gate fidelity

For a circuit with $g$ two-qubit gates, each with average error rate $\epsilon$, the expected XEB fidelity is approximately:

$F_{\text{XEB}} \approx (1 - \epsilon)^g$

This exponential decay means that XEB is sensitive to the total accumulated error across the circuit. A processor with $0.5\%$ two-qubit gate error running a circuit with 400 two-qubit gates has expected $F_{\text{XEB}} \approx (0.995)^{400} \approx 0.13$, which is still detectable above the noise floor.

This relationship also makes XEB a useful tool for extracting average gate errors from full circuit execution, complementing randomized benchmarking which measures gate errors in isolation.

Limitations and criticisms

XEB has several known limitations:

• Classical simulation required: Computing $p(x)$ for each measured bitstring requires classically simulating the circuit. For circuits in the “quantum supremacy” regime, even computing individual amplitudes is expensive, requiring approximate methods.
• Sensitivity to noise structure: XEB assumes that errors behave approximately like depolarizing noise. Correlated errors, leakage, or structured noise can cause XEB fidelity to overestimate or underestimate true circuit fidelity.
• Spoofability concerns: Researchers have debated whether certain classical algorithms could “spoof” a high XEB score without actually sampling from the correct distribution. Tensor network methods have narrowed (though not closed) the gap between classical and quantum XEB scores for the Sycamore circuits.
• Not application-relevant: High XEB fidelity on random circuits does not directly imply good performance on structured algorithms like VQE or QAOA.

Why it matters for learners

XEB is the benchmark at the center of the quantum supremacy debate, one of the most publicly visible milestones in quantum computing. Understanding how it works, including its strengths and limitations, is essential for critically evaluating claims about quantum computational advantage. XEB also illustrates a deep connection between quantum information theory and statistical mechanics: the Porter-Thomas distribution of random circuit outputs, the exponential decay of fidelity with circuit size, and the computational complexity of classical simulation.

See also

• Quantum Volume
• Randomized Benchmarking
• Gate Fidelity
• Quantum Benchmark