Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Open accessThe DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
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 certain class of highly entangled many-body wave functions. It has been suggested that such a quantum advantage can be certified with the (XEB). We critically examine this notion. First, we consider a “benign” setting, where an honest implementation of a noisy quantum circuit is assumed, and characterize the conditions under which the XEB approximates the of quantum dynamics. Second, we assume an “adversarial” setting, where all possible classical algorithms are considered for comparisons, and show that achieving relatively high XEB values does not imply faithful simulation of quantum dynamics. Specifically, we present an efficient classical algorithm that achieves high XEB values, namely 5–12% of those obtained in the state-of-the-art experiments, within just a few seconds using a single GPU machine. This is made possible by identifying and exploiting several vulnerabilities of the XEB, which allows us to achieve high XEB values without simulating a full quantum circuit. Remarkably, our algorithm features with the system size than a noisy quantum device for commonly studied random circuit ensembles in various architecture. We quantitatively explain the success of our algorithm and the limitations of the XEB by using a theoretical framework, in which the dynamics of the average XEB and fidelity are mapped to classical statistical mechanics models. Using this framework, we illustrate the relation between the XEB and the fidelity for quantum circuits in various architectures, with different choices of gate sets, and in the presence of noise. Taken together, our results demonstrate that XEB’s utility as a proxy for fidelity hinges on several conditions, which should be independently checked in the benign setting, but cannot be assumed in the general adversarial setting. Therefore, the XEB on its own has a limited utility as a benchmark for quantum advantage. We briefly discuss potential ways to overcome these limitations. Published by the American Physical Society 2024
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
Density matrix formulation for quantum renormalization groups
White, S. R. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2863 · Cited by 7,702
Completely positive linear maps on complex matrices
Choi, M.-D. (1975) · Linear Algebra and its Applications · doi:10.1016/0024-3795(75)90075-0 · Cited by 2,659
Quantum computational advantage using photons
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., et al. (2020) · Science · doi:10.1126/science.abe8770 · Cited by 2,405
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Self-citationBlack holes as mirrors: quantum information in random subsystems
Hayden, P., & Preskill, J. (2007) · Journal of High Energy Physics · doi:10.1088/1126-6708/2007/09/120 · Cited by 1,332 · cited 3×
“Such demonstration is important because it not only constitutes a milestone of quantum technology, but also challenges the so called extended Church-Turing thesis [1, 2], which has been central to computational complexity theory.”
BackgroundThe Theory of Quantum Information
Watrous, J. (2018) · doi:10.1017/9781316848142 · Cited by 1,325 · cited 4×
“[25] the blue part the black part with 1 being excluded USTC-2: Fig.”
BackgroundInfluentialPredicting many properties of a quantum system from very few measurements
Huang, H.-Y., Kueng, R., & Preskill, J. (2020) · Nature Physics · doi:10.1038/s41567-020-0932-7 · Cited by 1,240
Buhrman, H., Cleve, R., Watrous, J., & de Wolf, R. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.167902 · Cited by 1,190
Cited by
Logical quantum processor based on reconfigurable atom arrays
Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz, T., Ebadi, S., Cain, M., Kalinowski, M., Hangleiter, D., et al. (2024) · Nature · doi:10.1038/s41586-023-06927-3 · Cited by 1,119
Self-citationPhase transition in Random Circuit Sampling
Morvan, A., Villalonga, B., Mi, X., Mandrà, S., Bengtsson, A., Klimov, P. V., Chen, Z., Hong, S., Erickson, C., Drozdov, I. K., et al. (2023) · arXiv · doi:10.48550/arxiv.2304.11119 · Cited by 138
Self-citationVariational benchmarks for quantum many-body problems
Wu, D., Rossi, R., Vicentini, F., Astrakhantsev, N., Becca, F., Cao, X., Carrasquilla, J., Ferrari, F., Georges, A., Hibat-Allah, M., et al. (2024) · Science · doi:10.1126/science.adg9774 · Cited by 79
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M. D., Barak, B., & Choi, S. (2021) · arXiv · doi:10.48550/arxiv.2112.01657 · Cited by 54
Self-citationComputational Power of Random Quantum Circuits in Arbitrary Geometries
(2025) · doi:10.1103/physrevx.15.021052 · Cited by 45
The computational power of random quantum circuits in arbitrary geometries
DeCross, M., Haghshenas, R., Liu, M., Rinaldi, E., Gray, J., Alexeev, Y., Baldwin, C. H., Bartolotta, J. P., Bohn, M., Chertkov, E., et al. (2024) · arXiv · doi:10.48550/arxiv.2406.02501 · Cited by 45
Bell Sampling from Quantum Circuits
Hangleiter, D., & Gullans, M. J. (2024) · Physical Review Letters · doi:10.1103/physrevlett.133.020601 · Cited by 28
Fully Scalable Randomized Benchmarking Without Motion Reversal
Hines, J., Hothem, D., Blume-Kohout, R., Whaley, B., & Proctor, T. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.030334 · Cited by 12
“This is because XEB estimates the fidelity of random circuits using the (linear) cross entropy, which is not an accurate fidelity estimator for general Markovian noise models [34, 36].”
MethodRobust sparse IQP sampling in constant depth
Paletta, L., Leverrier, A., Sarlette, A., Mirrahimi, M., & Vuillot, C. (2024) · Quantum · doi:10.22331/q-2024-05-06-1337 · Cited by 8
“Unfortunately, the evidence for the classical hardness of this problem is thinner, and recent works have cast some serious doubts on the possibility of demonstrating a quantum advantage with this approach [6, 7, 8, 9, 10].”
A sharp phase transition in linear cross-entropy benchmarking
Ware, B., Deshpande, A., Hangleiter, D., Niroula, P., Fefferman, B., Gorshkov, A. V., & Gullans, M. J. (2023) · arXiv · doi:10.48550/arxiv.2305.04954 · Cited by 4
Metadata
- Authors
- Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M. D., Barak, B., & Choi, S.
- Venue
- PRX Quantum
- Publisher
- American Physical Society (APS)
- Published
- 2024-02-29
- Volume
- 5
- Issue
- 1
- ISSN
- 2691-3399 (ISSN-L)
- OpenAlex
- W4392284845
- Cited by
- 53
- References
- 35
- FWCI
- 6.10
- Type
- journal article
- Language
- en
- Open access
- gold
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.