CoChat
Sign Up
PreprintCited by 54Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage

Open access
Gao, Xun, Kalinowski, Marcin, Chou, Chi-Ning, Lukin, Mikhail D., Barak, Boaz, Choi, Soonwon·2021·arXiv
DOI 10.48550/arxiv.2112.01657arXiv 2112.01657
Open this paper in CoChat — free accountOpen PDF

Abstract

Demonstrating quantum advantage requires experimental implementation of a computational task that is hard to achieve using state-of-the-art classical systems. One approach is to perform sampling from a probability distribution associated with a class of highly entangled many-body wavefunctions. It has been suggested that this approach can be certified with the Linear Cross-Entropy Benchmark (XEB). We critically examine this notion. First, in a "benign" setting where an honest implementation of noisy quantum circuits is assumed, we characterize the conditions under which the XEB approximates the fidelity. Second, in an "adversarial" setting where all possible classical algorithms are considered for comparison, we show that achieving relatively high XEB values does not imply faithful simulation of quantum dynamics. We present an efficient classical algorithm that, with 1 GPU within 2s, yields high XEB values, namely 2-12% of those obtained in experiments. By identifying and exploiting several vulnerabilities of the XEB, we achieve high XEB values without full simulation of quantum circuits. Remarkably, our algorithm features better scaling with the system size than noisy quantum devices for commonly studied random circuit ensembles. To quantitatively explain the success of our algorithm and the limitations of the XEB, we use a theoretical framework in which the average XEB and fidelity are mapped to statistical models. We illustrate the relation between the XEB and the fidelity for quantum circuits in various architectures, with different gate choices, and in the presence of noise. Our results show that XEB's utility as a proxy for fidelity hinges on several conditions, which must be checked in the benign setting but cannot be assumed in the adversarial setting. Thus, the XEB alone has limited utility as a benchmark for quantum advantage. We discuss ways to overcome these limitations.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2112.01657

Cites

53 of 56 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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?

  • The XEB is a better benchmark for IQP circuits than for generic random circuit sampling settings such as Haar-random circuits.

    “Moreover, the XEB turns out to be a better benchmark for IQP circuits than for generic random circuit sampling settings (such as Haar-random circuits)102–104.”

    From Logical quantum processor based on reconfigurable atom arrays (2024) · cites this paper as [102]

    The Abstract discusses limitations of XEB as a benchmark, and Result 2 examines circuits with Haar-random gates. Neither passage compares XEB’s suitability for IQP circuits with its suitability for Haar-random circuits. Searches for “IQP,” “commuting circuits,” and that comparison found no passage addressing it. (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

Flagged first, then by citations

Research works printed but not linked: 37

  1. Y. Wu et al., Strong quantum computational advan- tage using a superconducting quantum processor. arXiv preprint arXiv:2106.14734 (2021). · arXiv
  2. Q. Zhu et al., Quantum computational advantage via 60- qubit 24-cycle random circuit sampling. arXiv preprint arXiv:2109.03494 (2021). · arXiv
  3. S. Ebadi et al., Quantum phases of matter on a 256- atom programmable quantum simulator. arXiv preprint arXiv:2012.12281 (2020). · arXiv
  4. J. Preskill, Quantum computing and the entanglement frontier. arXiv preprint arXiv:1203.5813 (2012). · arXiv
  5. E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674 (2016). · arXiv
  6. J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Architectures for quantum simulation showing quantum supremacy. arXiv preprint arXiv:1703.00466 (2017). · arXiv
  7. B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and arthur- merlin games. arXiv preprint arXiv:quant-ph/0205133 (2002). · arXiv
  8. S. Aaronson and L. Chen, Complexity-theoretic founda- tions of quantum supremacy experiments. arXiv preprint arXiv:1612.05903 (2016). · arXiv
  9. R. Movassagh, Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of random circuit sampling. arXiv preprint arXiv:1810.04681 (2018). · arXiv
  10. A. Bouland, B. Fefferman, Z. Landau, and Y. Liu, Noise and the frontier of quantum supremacy. arXiv preprint arXiv:2102.01738 (2021). · arXiv
  11. Y. Kondo, R. Mori, and R. Movassagh, Fine-grained analysis and improved robustness of quantum supremacy for random circuit sampling. arXiv preprint arXiv:2102.01960 (2021). · arXiv
  12. Y. Rinott, T. Shoham, and G. Kalai, Statistical aspects of the quantum supremacy demonstration. arXiv preprint arXiv:2008.05177 (2020). · arXiv
  13. J. Choi et al., Emergent randomness and benchmark- ing from many-body quantum chaos. arXiv preprint arXiv:2103.03535 (2021). · arXiv
  14. Y. Liu, M. Otten, R. Bassirianjahromi, L. Jiang, and B. Fefferman, Benchmarking near-term quantum com- puters via random circuit sampling. arXiv preprint arXiv:2105.05232 (2021). · arXiv
  15. S. Aaronson and S. Gunn, On the classical hardness of spoofing linear cross-entropy benchmarking. arXiv preprint arXiv:1910.12085 (2019). · arXiv
  16. J. Gray and S. Kourtis, Hyper-optimized tensor network contraction. arXiv preprint arXiv:2002.01935 (2020). · arXiv
  17. C. Huang et al., Classical simulation of quantum supremacy circuits. arXiv preprint arXiv:2005.06787 (2020). · arXiv
  18. F. Pan and P. Zhang, Simulating the sycamore quan- tum supremacy circuits. arXiv preprint arXiv:2103.03074 (2021). · arXiv
  19. H. Fu et al., Closing the "quantum supremacy" gap: Achieving real-time simulation of a random quantum cir- cuit using a new Sunway supercomputer. arXiv preprint arXiv:2110.14502 (2021). · arXiv
  20. X. Liu et al., Redefining the quantum supremacy base- line with a new generation Sunway supercomputer. arXiv:2111.01066 (2021). · arXiv
  21. F. Pan, K. Chen, and P. Zhang, Solving the sampling problem of the Sycamore quantum supremacy circuits. arXiv:2111.03011 (2021). · arXiv
  22. I. L. Markov, A. Fatima, S. V. Isakov, and S. Boixo, Quan- tum supremacy is both closer and farther than it appears. arXiv preprint arXiv:1807.10749 (2018). · arXiv
  23. N. Hunter-Jones, Unitary designs from statistical mechan- ics in random quantum circuits. arXiv preprint arXiv:1905. 12053 (2019).
  24. J. Napp, R. L. La Placa, A. M. Dalzell, F. G. Bran- dao, and A. W. Harrow, Efficient classical simulation of random shallow 2D quantum circuits. arXiv preprint arXiv:2001.00021 (2019). · arXiv
  25. G. Kalachev, P. Panteleev, and M.-H. Yung, Recursive multi-tensor contraction for XEB verification of quantum circuits. arXiv preprint arXiv:2108.05665 (2021). · arXiv
  26. A. Harrow and S. Mehraban, Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates. arXiv preprint arXiv:1809.06957 (2018). · arXiv
  27. X. Gao and L. Duan, Efficient classical simulation of noisy quantum computation. arXiv preprint arXiv:1810.03176 (2018). · arXiv
  28. B. Barak, C.-N. Chou, and X. Gao, in 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), (2021), p. 30:1, 2005.02421.
  29. A. M. Dalzell, N. Hunter-Jones, and F. G. Brandão, Ran- dom quantum circuits anti-concentrate in log depth. arXiv preprint arXiv:2011.12277 (2020). · arXiv
  30. D. Niedermayer, in Innovations in Bayesian networks: Theory and applications (Springer, Berlin, Heidelberg, 2008), p. 117.
  31. A. Deshpande et al., Tight bounds on the convergence of noisy random circuits to uniform. arXiv preprint arXiv:2112.00716 (2021). · arXiv
  32. G. D. Kahanamoku-Meyer, S. Choi, U. V. Vazirani, and N. Y. Yao, Classically-verifiable quantum advantage from a computational Bell test. arXiv preprint arXiv:2104.00687 (2021). · arXiv
  33. Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick, Sim- pler proofs of quantumness. arXiv preprint arXiv:2005. 04826 (2020).
  34. Z. Liu and A. Gheorghiu, Depth-efficient proofs of quan- tumness. arXiv preprint arXiv:2107.02163 (2021). · arXiv
  35. S. Hirahara and F. L. Gall, Test of quantumness with small-depth quantum circuits. arXiv preprint arXiv:2105.05500 (2021). · arXiv
  36. Daniel Greenbaum, Introduction to quantum gate set tomography. arXiv preprint arXiv:1509.02921 (2015). · arXiv
  37. Benoît Collins, Moments and cumulants of polynomial random variables on unitarygroups, the Itzykson-Zuber integral, and free probability, Int. Math. Res. Not. 2003, 953 (2003).

Cited by

Sorted by citations

Related

Authors
Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M. D., Barak, B., & Choi, S.
Affiliations
  • Harvard University (US)
  • Massachusetts Institute of Technology (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2021
Volume
5
Issue
1
ISSN
2691-3399 (ISSN-L)
DOI
10.48550/arxiv.2112.01657
arXiv
2112.01657
OpenAlex
W4392284845
Cited by
54
References
55
Citations by year
2026: 7 · 2025: 19 · 2024: 16 · 2023: 6 · 2022: 6
FWCI
6.22
Type
journal article
Language
en
Open access
Licence
Locations
  • PRX Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • CU Scholar (University of Colorado Boulder) (submittedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1565264, TRT 0159)
  • Adolph C. and Mary Sprague Miller Institute for Basic Research in Science, University of California Berkeley
  • Templeton Religion Trust (TRT0159)
  • Defense Advanced Research Projects Agency (W911NF2010021)
  • Multidisciplinary University Research Initiative
  • Army Research Office
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
quantum advantage, classical simulation of quantum circuits, random quantum circuits, statistical mechanical model, noisy quantum devices, quantum benchmarking

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