On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Classical shadows is based on and inspired by shadow tomography.
“The method is based on and inspired by shadow tomography (Aaronson, 2019).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Aaronson, 2019
The paper’s Introduction (pp. 1–2) discusses random-circuit sampling and spoofing Linear Cross-Entropy Benchmarking, not classical shadows. Searches for “shadow tomography” and “classical shadows inspired by shadow tomography” found no passage addressing the claimed relationship. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 10
- Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing , STOC '11, pages 333-342, New York, NY, USA, 2011. ACM.
- Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32Nd Computational Complexity Conference , CCC '17, pages 22:1-22:67, Germany, 2017.
- Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature , 574(7779):505-510, 2019.
- Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics , 14(6):595-600, 2018.
- Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh V. Vazirani. Quantum supremacy and the complexity of random circuit sampling. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA , pages 15:1-15:2, 2019.
- M. J. Bremner, R. Jozsa, and D. J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society of London Series A , 467(2126):459-472, Feb 2011.
- Aram Harrow and Saeed Mehraban. Approximate unitary t -designs by short random quantum circuits using nearest-neighbor and long-range gates. arXiv e-prints , art. arXiv:1809.06957, Sep 2018. · arXiv
- Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong quantum simulation. CoRR , abs/1804.10368, 2018. · arXiv
- John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, and Aram W. Harrow. Efficient classical simulation of random shallow 2D quantum circuits. arXiv e-prints , art. arXiv:2001.00021, Dec 2019. · arXiv
- Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits. arXiv eprints , art. arXiv:1910.09534, Oct 2019. · arXiv
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
- Authors
- Aaronson, S., & Gunn, S.
- Affiliations
- The University of Texas at Austin (US)
- ORCID
- Aaronson, Scott
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2019
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1910.12085
- OpenAlex
- W2981350817
- Cited by
- 12
- References
- 0
- Citations by year
- 2025: 1 · 2024: 2 · 2023: 2 · 2022: 3 · 2021: 2 · 2020: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum advantage, noisy quantum circuits, superconducting qubits
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
