# Cross-Entropy Benchmarking: How Google Measures Quantum Quality **Source**: https://quantumsequrity.com/blog/cross-entropy-benchmarking **Category**: Quantum Computing Fundamentals --- [← Back to Blog](../../blog.html) Quantum Computing Fundamentals # Cross-Entropy Benchmarking: How Google Measures Quantum Quality 12 min read When Google announced quantum supremacy in October 2019 with the 53 qubit Sycamore chip, the entire claim rested on a benchmarking technique called Cross-Entropy Benchmarking, abbreviated XEB. Without XEB, the announcement would have been just a story about a chip generating random looking outputs. With XEB, Google could mathematically argue that those outputs matched what a quantum circuit should produce, and that the same outputs were genuinely beyond the reach of any classical computer in reasonable time. XEB has remained the dominant benchmark for measuring whether a quantum chip is doing something genuinely quantum, not just producing noise. This article explains what XEB measures, how it underpinned the Sycamore claim, the statistical foundation, and the criticisms that emerged. ## A Plain English Picture Imagine you have a deck of trick cards that produces a specific weighted distribution. The two of hearts comes up 5 percent of the time. The ace of spades comes up 0.1 percent of the time. The king of diamonds, 2 percent. Every card has a specific probability. Now you watch someone shuffle and deal cards. After 10 thousand deals, you check whether the observed frequencies match the expected probabilities. If the dealer is using your trick deck honestly, the observed and expected match closely. If the dealer is using a normal deck, every card comes up about 1 in 52 of the time, which does not match. The closer the match between observed and expected, the more confident you can be that the dealer is using your special deck. Cross-Entropy Benchmarking is exactly this idea applied to quantum circuits. The trick deck is a quantum circuit with a known output probability distribution. The dealer is the quantum chip running that circuit. The observed deals are the chip's output samples. XEB measures how closely the chip's outputs match the circuit's expected distribution, which tells you whether the chip is actually executing the circuit or producing random noise. ## The Mathematical Setup A random quantum circuit with N qubits has 2 to the N possible output bitstrings. Each bitstring has some probability of appearing if the circuit is run on an ideal quantum computer. These probabilities are not uniform. Some bitstrings are more likely than others, and the specific probability distribution is determined by the structure of the circuit. Critically, computing these probabilities classically takes exponential time. For a 53 qubit circuit with a few dozen gate layers, the classical work to compute even a single output probability is enormous. This is the property that makes random circuit sampling a candidate for quantum supremacy. XEB is defined as follows. Take many output samples from the chip running the circuit. For each sample, compute the ideal probability that the sample would have occurred. Average those probabilities, multiply by 2 to the N, subtract 1. A perfect quantum chip has XEB approaching 1 in the limit of large circuits. A pure random sampler that produces uniformly random outputs has XEB equal to 0. Real noisy chips produce values somewhere in between, and the XEB value tells you how close to ideal the chip is performing. ### The Heavy Output Connection XEB is mathematically related to another concept called heavy output sampling. The heavy outputs of a circuit are those bitstrings whose probability is above the median. An ideal quantum circuit produces heavy outputs about 85 percent of the time, while a random sampler produces them 50 percent of the time. The difference between XEB and heavy output sampling is mostly in mathematical convenience, but they capture the same fundamental fact, that the output distribution is non uniform in a specific way determined by the circuit. ## How Google Used XEB for the Sycamore Claim In October 2019, Google's Nature paper described running Sycamore on random quantum circuits with up to 53 qubits and 20 layers of two qubit gates. They collected millions of samples and computed the XEB. The reported XEB was small but consistent and statistically significant. Sycamore was producing outputs whose probabilities were correlated with the ideal circuit distribution at a level much higher than any noisy classical sampler could achieve. Google's claim then translated this XEB value into a runtime comparison. Producing outputs with the same XEB classically would require simulating the quantum circuit accurately enough to bias the sampler toward heavy outputs. They estimated the world's most powerful supercomputer would take 10 thousand years to do this. Sycamore did it in 200 seconds. ### The Statistical Argument The reason this argument is rigorous is that XEB has a precise statistical interpretation. It measures the Kullback-Leibler divergence between the chip's output distribution and the uniform distribution, weighted toward heavy outputs. The expected value of XEB for a fully decohered circuit is 0. The expected value for an ideal circuit is 1. Anything in between corresponds to a specific level of partial coherence, with quantitative bounds. This made XEB much more credible than just observing that the chip output something unusual. The metric came with mathematical guarantees about what could and could not produce specific values. ## Criticisms and Refinements The XEB framework received serious scrutiny from theorists and from competing quantum computing groups, particularly IBM. ### IBM's Classical Algorithm Response Within weeks of the Sycamore announcement, IBM published an analysis arguing that with better classical algorithms, particularly tensor network methods and improved memory management, a supercomputer could simulate the Sycamore output in around 2 days, not 10 thousand years. This was a significant correction to the supremacy timeline, though it did not eliminate the supremacy claim entirely. Sycamore's 200 seconds versus 2 days is still a meaningful gap. ### Improved Classical Simulation Techniques Subsequent work over the following years has continued to chip away at the supremacy gap. By 2022, several papers had demonstrated that the original Sycamore result could be simulated classically in around a week or less on large supercomputers. This is not a refutation of XEB as a metric, but it complicates the supremacy narrative. The chip did something fast that classical computers can also do, slowly, with sufficient resources. ### XEB Spoofing Theoretical analyses have explored whether XEB could be spoofed by classical samplers using approximation techniques. In specific limited regimes, it is possible to produce a sampler that achieves nontrivial XEB without truly performing quantum computation. The practical relevance of these spoofing attacks for the actual Sycamore experiment is limited, but they remain a topic of debate. ### Sample Size Issues XEB requires a large number of samples to be statistically meaningful. For a 53 qubit circuit, distinguishing a chip with XEB equal to 0.002 from a fair coin requires millions of samples, which Sycamore collected. For smaller circuits or smaller XEB values, the required sample size grows enormously, making the metric expensive to evaluate in some regimes. ## XEB Versus Other Benchmarks XEB is one of several benchmarks used to characterize quantum hardware. Each has strengths. | Benchmark | What it measures | Common platforms | |---|---|---| | XEB | Output distribution accuracy | Google, neutral atom | | Quantum Volume | Combined width and depth capability | IBM, trapped ion | | Algorithmic qubits | Application specific capacity | IonQ | | CLOPS | Throughput | IBM | | Random benchmarking | Average gate fidelity | Most platforms | | Process tomography | Full gate characterization | Small systems only | XEB is particularly suited for sampling tasks like the Sycamore demonstration but less natural for general algorithm performance. Quantum Volume is more suited for general capability comparison. Together, they paint a fuller picture than either alone. ## What XEB Tells Us About Cryptographic Risk XEB demonstrations are not direct threats to cryptography. The Sycamore chip running random circuits cannot factor RSA. The output samples have no algebraic structure that maps to integer factoring. What XEB does tell us is that quantum hardware can genuinely access computational regimes classical computers cannot easily replicate. This is a confirmation that the underlying physics works as predicted. It supports the long term plausibility of fault tolerant quantum computing eventually achieving cryptographically relevant scale. For security teams, XEB progress is a leading indicator rather than a threat trigger. The right response is to deploy [post-quantum cryptography](../what-is-post-quantum-cryptography.html) ahead of any plausible cryptographically relevant quantum computer, regardless of XEB benchmark progress. QNSQY ships [NIST standardized](../nist-fips-guide.html) algorithms today, including [ML-KEM](../ml-kem-explained.html) for key exchange and [ML-DSA](../mldsa-vs-slhdsa.html) for signatures. ## How XEB Is Calculated in Practice The mathematics of XEB looks intimidating but the calculation is straightforward in practice. For each output sample bitstring s, the verifier computes the ideal probability P of s under the random circuit U being executed. This probability is computed by classical simulation of the circuit. The XEB value is the average of P times 2 to the N over all samples, minus 1. For a perfect quantum chip, the average probability of observed samples is well above 1 over 2 to the N because the chip preferentially produces high probability bitstrings. The factor of 2 to the N normalizes the result so XEB equals 1 for perfect circuits. For a chip that produces uniformly random bitstrings, the average probability is exactly 1 over 2 to the N, giving XEB equal to 0. The catch is that computing P for arbitrary bitstrings requires classical simulation of the quantum circuit, which has exponential complexity. For a 53 qubit circuit, this simulation is expensive but feasible on supercomputers. For larger circuits, the simulation becomes intractable, which is precisely why XEB is hard to verify at the largest scales. ### Cross Verification Tricks To extend XEB beyond the regime of direct classical simulation, researchers use cross verification. The full system is broken into smaller subsystems, the XEB of each subsystem is computed, and the full system XEB is inferred from these pieces. The technique introduces some additional uncertainty but allows extrapolation to circuit sizes that cannot be directly simulated. This is one of the active research areas in benchmark methodology. As quantum chips grow beyond 60 qubits, direct XEB becomes infeasible and indirect methods like cross verification become essential. ## XEB and the Future of Quantum Benchmarking The benchmarking ecosystem has matured considerably since 2019. XEB remains a standard but is increasingly supplemented by application specific benchmarks that measure performance on practical algorithms. As error corrected systems begin operating, the relevance of pure XEB will decline in favor of metrics that measure logical qubit performance and fault tolerant algorithm execution. For now, XEB continues to be reported by major hardware groups for new chip generations. The metric remains a useful sanity check that the chip is doing something genuinely quantum and a comparable benchmark across vendors when properly normalized. ## Frequently Asked Questions ### What does an XEB value of 0.002 actually mean? An XEB of 0.002 means the chip's output distribution is approximately 0.2 percent of the way from the uniform distribution toward the ideal quantum circuit distribution. This is small but, for a 53 qubit circuit with millions of samples, statistically distinguishable from pure noise. It corresponds to the chip executing the circuit with limited but measurable fidelity, accumulating noise but still showing a quantum signature. ### Could a noisy classical algorithm fake XEB values? Specific limited regimes allow approximation techniques to produce nontrivial XEB without true quantum computation, but these techniques have specific structural constraints that the Sycamore experiment was designed to avoid. The full theoretical analysis is ongoing in the cryptography and complexity theory communities, but no practical spoofing attack has been demonstrated against the Sycamore protocol. ### Is XEB still relevant in 2026? Yes. XEB remains the standard benchmark for sampling demonstrations and continues to be reported by hardware groups for new chips. It complements rather than replaces metrics like Quantum Volume and algorithmic benchmarks. ### Does XEB scale with chip size? XEB can be evaluated on circuits of any size in principle, but the sample size and classical verification cost grow rapidly with qubit count. For circuits beyond about 60 qubits, computing the ideal probabilities for verification is infeasible on classical hardware, making direct XEB measurement impractical. Researchers use cross verification with smaller subsystems to extrapolate. ### How does QNSQY's defense relate to XEB progress? QNSQY uses post-quantum algorithms whose security depends on mathematical problems unrelated to random circuit sampling. XEB progress measures hardware quality, not cryptanalytic capability. Whether a future chip has XEB approaching 1 or far below, QNSQY's lattice based and hash based protections remain valid against any quantum algorithm currently known. ## Sources 1. [Google Sycamore quantum supremacy paper, Nature 2019](https://www.nature.com/articles/s41586-019-1666-5) 2. [IBM challenge to Sycamore classical runtime](https://research.ibm.com/blog/on-quantum-supremacy) 3. [Boixo et al, Characterizing quantum supremacy in near term devices, 2018](https://arxiv.org/abs/1608.00263) 4. [NIST post-quantum cryptography standards](https://csrc.nist.gov/projects/post-quantum-cryptography) 5. [Pan, Chen, Zhang, Solving the sampling problem of the Sycamore quantum circuits](https://arxiv.org/abs/2111.03011) 6. [NSA Commercial National Security Algorithm 2.0 advisory](https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF) ## Related Articles - [What is post-quantum cryptography](../what-is-post-quantum-cryptography.html) - [Q-Day: when quantum breaks encryption](../q-day-when-quantum-breaks-encryption.html) - [CRQC meaning explained](../crqc-meaning-explained.html) - [Google quantum Willow chip](../google-quantum-willow-chip.html) - [Logical qubits vs physical qubits](../logical-qubits-vs-physical-qubits.html) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)