When a quantum computer runs a job no classical machine can copy, an awkward question follows: how do you check that it got the answer right? If the whole point is that no ordinary computer can reproduce the result, then no ordinary computer can grade it either. This is the puzzle at the heart of random circuit sampling, the task Google used to stake its first claim of quantum advantage. The escape hatch is a statistic called the linear cross-entropy benchmark, or XEB, and understanding it explains both why those early demonstrations mattered and why critics never stopped poking at them.
A deliberately useless task
Random circuit sampling is not designed to solve anything. You take a stack of qubits, apply a long sequence of randomly chosen gates, and then measure. Out comes a bit string. Run it again, out comes another. The output is not uniformly random, though. Quantum interference makes some bit strings far more likely than others, a speckled pattern of peaks and troughs that physicists call a speckle or a Porter-Thomas distribution. A perfect quantum computer would produce those particular strings with those particular probabilities. A classical computer can predict the distribution only by simulating the entire quantum state, and that cost explodes as you add qubits and depth.
So the task is engineered to be easy for the right hardware and brutally expensive for everything else. The catch remains: measuring the machine gives you a pile of bit strings, not a verdict.
What XEB actually measures
The linear cross-entropy score works by cheating, but in a controlled way. For a circuit small enough to still be simulated classically, you compute the ideal probability of each bit string the quantum computer spat out. Then you average those ideal probabilities over all the samples the machine produced.
The logic is simple once you see it. A flawless quantum computer favors the high-probability strings, so the average of their ideal probabilities comes out high. A machine spewing pure noise picks strings at random, so its average lands at the value you'd expect from chance. XEB is scaled so that a perfect run scores 1 and a fully scrambled run scores 0. A score of 0.002 sounds like failure, but in this context it means roughly two-tenths of a percent of the runs behaved as an ideal circuit would, which for a deep circuit on dozens of qubits is a signal you can actually stand on.
The score also tracks fidelity in a predictable way. Every gate leaks a little error, and those errors multiply. XEB effectively reports the product of all the individual gate and measurement fidelities across the circuit. That makes it a blunt but honest report card for the whole processor at once.
The verification trap
Here is the uncomfortable part. XEB can only be computed for circuits a classical computer can still simulate. Push the circuit into the regime where quantum advantage supposedly lives, and you can no longer calculate the ideal probabilities to check against. The trust comes from extrapolation. You verify XEB in the simulable regime, watch it fall exactly as your error model predicts, and then argue that the same physics carries into the region you can't check.
That extrapolation is precisely where the fights broke out. Classical algorithms teams responded to Google's first claim by finding smarter simulation methods, tensor-network approaches and clever approximations that chipped away at the supposed advantage. Some argued that a classical machine could match a low XEB score without truly reproducing the distribution, since a slightly noisy target is easier to fake. Each side kept raising the bar, which is arguably the healthiest thing that could happen to a benchmark.
Why it still matters
Random circuit sampling produces nothing you can sell. It won't design a drug or price a bond. But XEB gave the field its first quantitative handle on a machine operating past the edge of classical reach, and it forced everyone to be specific about what advantage even means. It also doubles as a diagnostic. Because the score reflects total system fidelity, engineers use it to catch a drifting gate or a flaky coupler across many qubits in a single sweep, rather than benchmarking each component in isolation.
As hardware moves toward error-corrected logical qubits, the spotlight is shifting to benchmarks that measure useful work rather than raw sampling. Still, the linear cross-entropy score remains the tool that turned a philosophical headache, how to grade the ungradable, into a number you can argue about.
