On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking

Scott Aaronson, Sam Gunn

Authors: Scott Aaronson and Sam Gunn

Abstract

Recently, Google announced the first demonstration of quantum computational supremacy with a programmable superconducting processor. Their demonstration is based on collecting samples from the output distribution of a noisy random quantum circuit, then applying a statistical test to those samples called Linear Cross-Entropy Benchmarking (Linear XEB). This raises a theoretical question: how hard is it for a classical computer to spoof the results of the Linear XEB test? In this short note, we adapt an analysis of Aaronson and Chen [2017] to prove a conditional hardness result for Linear XEB spoofing. Specifically, we show that the problem is classically hard, assuming that there is no efficient classical algorithm that, given a random n-qubit quantum circuit C, estimates the probability of C outputting a specific output string, say 0^n, with variance even slightly better than that of the trivial estimator that always estimates 1/2^n. Our result automatically encompasses the case of noisy circuits.

Introduction

In 2019, Google’s "Sycamore" processor achieved a landmark in physics: quantum computational supremacy. By performing a task in 200 seconds that was estimated to take a classical supercomputer thousands of years, Google demonstrated that programmable quantum devices could outperform the world's most powerful classical machines. The task chosen was Random Circuit Sampling (RCS), where the goal is to generate bitstrings according to the complex probability distribution of a random quantum circuit.

To verify that the Sycamore processor was truly sampling from the correct distribution, Google utilized a statistical metric known as Linear Cross-Entropy Benchmarking (Linear XEB). This test measures how well the experimental samples correlate with the ideal theoretical probabilities. However, a critical theoretical vulnerability remained: could a classical algorithm "spoof" this test? That is, could a classical computer produce samples that pass the Linear XEB test without actually simulating the quantum circuit? This paper by Scott Aaronson and Sam Gunn provides the theoretical "safety net" needed to address this concern.

The Spoofing Problem

The validity of a quantum supremacy claim rests on the assumption that the verification task is classically intractable. If a classical programmer could devise a shortcut to pass the Linear XEB test—essentially "faking" the statistical fingerprint of a quantum computer—the claim of supremacy would be undermined.

The authors formalize this challenge by defining the XHOG (Linear Cross-Entropy Heavy Output Generation) task. XHOG is the computational problem of producing samples that achieve a specific threshold in the Linear XEB test. The central question of the paper is whether XHOG is fundamentally hard for classical computers.

Theoretical Framework and Assumptions

To prove the hardness of spoofing, the authors introduce a new complexity-theoretic assumption: the Linear Cross-Entropy Quantum Threshold Assumption (XQUATH).

XQUATH posits that no efficient classical algorithm can estimate the probability of a specific output string (e.g., $0^n$) for a random quantum circuit significantly better than a trivial guess of $1/2^n$. Specifically, it assumes that a classical algorithm cannot achieve a variance in its estimation that is even slightly better than the trivial estimator. This is a refinement of the earlier QUATH assumption, specifically tailored to the "Linear" version of the XEB test used by Google.

Main Result: The Reduction

The core contribution of the paper is Theorem 1, which establishes a formal reduction between spoofing the test and estimating quantum amplitudes. The authors prove that if an efficient classical algorithm exists that can solve XHOG (i.e., spoof the Linear XEB test), then that same algorithm can be used to violate XQUATH.

In simpler terms, the paper shows that spoofing isn't a "shortcut." To pass the statistical test, a classical computer must essentially perform the heavy lifting of calculating quantum amplitudes. Since researchers generally believe that estimating these amplitudes is a hard problem for classical systems, the reduction implies that spoofing the XEB test is equally hard.

Key Insights

1. Robustness to Noise

One of the most significant aspects of this result is its applicability to real-world devices. Quantum computers are inherently noisy, and the Sycamore processor only produced a "diluted" version of the ideal distribution. The authors demonstrate that their hardness result is "noise-aware," showing that even when the signal is weak, the classical task of spoofing remains hard.

2. Validation of Methodology

The paper provides a formal justification for Google’s choice of Linear XEB as a verification tool. It confirms that the statistical test is theoretically robust against classical "cheating," reinforcing the integrity of the supremacy demonstration.

3. Quantitative Bounds

The authors provide specific formulas relating the success probability of a spoofing algorithm to the number of samples ($k$) and the "heaviness" ($b$) of the outputs. For the parameters used in Google's 53-qubit experiment, the paper suggests that a classical computer would need millions of samples to spoof the result by pure luck—far exceeding the number of samples required for the quantum computer to pass the test legitimately.

Limitations and Future Work

While this work provides a strong defense for quantum supremacy, it is important to note its limitations:

  • Conditional Hardness: The result is conditional on the truth of XQUATH. While XQUATH is widely accepted in the community, it remains an unproven assumption in computational complexity.
  • The Simulation Gap: The paper proves that spoofing is as hard as simulation, but it does not prevent classical simulation itself from improving. Since the 2019 experiment, improved classical algorithms (such as those based on tensor network contraction) have reduced the time required to simulate these circuits on supercomputers. The "hardness" is relative to the current best understanding of classical simulation costs.

Conclusion

Aaronson and Gunn’s analysis provides the necessary theoretical foundations to trust the results of Random Circuit Sampling experiments. By linking the statistical validity of the Linear XEB test to the fundamental difficulty of estimating quantum amplitudes, they ensure that any classical attempt to mimic a quantum computer must face the same exponential barriers as a full simulation.

Summary updated

Abstract

Recently, Google announced the first demonstration of quantum computational supremacy with a programmable superconducting processor. Their demonstration is based on collecting samples from the output distribution of a noisy random quantum circuit, then applying a statistical test to those samples called Linear Cross-Entropy Benchmarking (Linear XEB). This raises a theoretical question: how hard is it for a classical computer to spoof the results of the Linear XEB test? In this short note, we adapt an analysis of Aaronson and Chen [2017] to prove a conditional hardness result for Linear XEB spoofing. Specifically, we show that the problem is classically hard, assuming that there is no efficient classical algorithm that, given a random n-qubit quantum circuit C, estimates the probability of C outputting a specific output string, say 0^n, with variance even slightly better than that of the trivial estimator that always estimates 1/2^n. Our result automatically encompasses the case of noisy circuits.
BibTeX
@inproceedings{aaronson2020classical,
  author = {Scott Aaronson and Sam Gunn},
  title = {{On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking}},
  booktitle = {Theory Comput},
  year = {2020},
  url = {https://openreview.net/forum?id=ZCeKIBE8MtM},
}
Figure