Quantum Algorithms

Cross-Entropy Benchmarking

A statistical test that estimates the fidelity of a random circuit's output by how often it produces high-probability bitstrings.

The verification problem

When a quantum processor runs a random circuit, we want to know whether it actually produced the intended distribution or just noise. For advantage-scale circuits we cannot compute the full distribution classically, so we need a test that works from limited classical computation and hardware samples. Cross-entropy benchmarking (XEB) is that test.

Linear cross-entropy fidelity

Kronos motion — 14 mev materials test

For each measured bitstring x, compute (from a classical simulation of the ideal circuit, feasible up to moderate size) its ideal probability p(x). The linear XEB fidelity is F = (2^n * average over samples of p(x)) - 1. A perfect device concentrates its samples on high-p(x) bitstrings, giving F near 1; a uniform noise sampler gives F near 0. F thus estimates the fraction of runs that were error-free.

Interpretation

F near 1: the hardware reproduces the ideal distribution.
F near 0: output is indistinguishable from uniform noise.
F decays exponentially with the number of gate errors, so it is a sensitive fidelity probe.

Why it works

Random circuits produce Porter-Thomas-distributed probabilities. Sampling proportionally to those probabilities makes high-p(x) strings appear more often than chance, and the weighted average of p(x) over samples encodes exactly this bias. The gap from the uniform baseline scales with the global circuit fidelity, letting a few thousand samples estimate a tiny fidelity precisely.

Limits and controversy

XEB requires computing ideal probabilities, so full verification is only possible below the classical simulation frontier; at advantage scale it relies on extrapolating per-gate fidelities. Spoofing attacks, classical algorithms that produce high XEB scores without simulating the full circuit, have challenged the interpretation of XEB as proof of advantage. It remains the standard fidelity metric for random circuit sampling while its role in advantage claims is scrutinized.