CoChat
Sign Up
PreprintCited by 55Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The DOI matches its DataCite record.

Boundaries of quantum supremacy via random circuit sampling

Open access
Zlokapa, Alexander, Boixo, Sergio, Lidar, Daniel·2020·arXiv
DOI 10.48550/arxiv.2005.02464arXiv 2005.02464
Open this paper in CoChat — free accountOpen PDF

Abstract

Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling, that is beyond the practical reach of modern supercomputers. We examine the constraints of the observed quantum runtime advantage in an extrapolation to circuits with a larger number of qubits and gates. Due to the exponential decrease of the experimental fidelity with the number of qubits and gates, we demonstrate for current fidelities a theoretical classical runtime advantage for circuits deeper than a few hundred gates, while quantum runtimes for cross-entropy benchmarking limit the region of a quantum advantage to a few hundred qubits. However, the quantum runtime advantage boundary in circuit width and depth grows exponentially with respect to reduced error rates, and our work highlights the importance of continued progress along this line. Extrapolations of measured error rates suggest that the limiting circuit size for which a computationally feasible quantum runtime advantage in cross-entropy benchmarking can be achieved approximately coincides with expectations for early implementations of the surface code and other quantum error correction methods. Thus the boundaries of quantum supremacy via random circuit sampling may fortuitously coincide with the advent of scalable, error corrected quantum computing in the near term.

Overview

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.2005.02464

Cites

Statistics

Verification

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?

  • Since NISQ devices are inherently noisy, analysis is required to find out how much noise a NISQ algorithm can endure until its classical simulation becomes efficient.

    “Since NISQ devices are inherently noisy, analysis similar to (Napp et al. , 2019; Zhou et al. , 2020b; Zlokapa et al. , 2020) will be required to find out how much noise a NISQ algorithm can endure until its classical simulation becomes efficient.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Zlokapa et al., 2020

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

No references could be resolved yet.

Research works printed but not linked: 42

  1. Arute, F. et al. Supplementary information for "quantum supremacy using a programmable superconducting processor". Preprint at https://arxiv.org/abs/ 1910.11333 (2019).
  2. Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. In: Proc. Annu. ACM Symp. Theory Comput. STOC '11, pp. 333-342. Association for Computing Machinery, New York, NY, USA https://doi.org/10.1145/ 1993636.1993682 (2011). · DOI · Paper page
  3. Bremner, M. J., Jozsa, R. & Shepherd, D. J. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A: Math. Phys. Eng. Sci. 467, 459-472 (2011).
  4. Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016).
  5. Aaronson, S. & Chen, L. Complexity-Theoretic Foundations of Quantum Supre- macy Experiments. In: O'Donnell, R. (ed.) Ann. IEEE Conf. Comput. Leibniz Inter- national Proceedings in Informatics (LIPIcs), vol. 79, pp. 22-12267. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany https://doi.org/ 10.4230/LIPIcs.CCC.2017.22 (2017). · DOI
  6. Harrow, A. W. & Montanaro, A. Quantum computational supremacy. Nature 549, 203 (2017).
  7. Neill, C. et al. A blueprint for demonstrating quantum supremacy with super- conducting qubits. Science 360, 195 (2018).
  8. Movassagh, R. Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of random circuit sampling with quantified robustness. Preprint at https://arxiv.org/abs/1909.06210 (2019). · arXiv
  9. Preskill, J. Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018).
  10. Pednault, E. et al. Breaking the 49-qubit barrier in the simulation of quantum circuits. Preprint at http://arxiv.org/abs/1710.05867 (2017). · arXiv
  11. Markov, I. L., Fatima, A., Isakov, S. V. & Boixo, S. Quantum Supremacy Is Both Closer and Farther than It Appears. Preprint at https://arxiv.org/abs/1807.10749 (2018). · arXiv
  12. Villalonga, B. et al. Establishing the quantum supremacy frontier with a 281 pflop/s simulation. Quantum Sci. Technol. 5, 034003 (2020).
  13. Gray, J. & Kourtis, S. Hyper-optimized tensor network contraction. Quantum 5, 410 (2021).
  14. Huang, C. et al. Classical simulation of quantum supremacy circuits. Preprint at https://arxiv.org/abs/2005.06787 (2020). · arXiv
  15. Pednault, E., Gunnels, J. A., Nannicini, G., Horesh, L. & Wisnieff, R. Leveraging secondary storage to simulate deep 54-qubit sycamore circuits. Preprint at https://arxiv.org/abs/1910.09534 (2019). · arXiv
  16. Zhou, Y., Stoudenmire, E. M. & Waintal, X. What limits the simulation of quantum computers? Phys. Rev. 10, 041038 (2020).
  17. Gottesman, D. An introduction to quantum error correction and fault-tolerant quantum computation. In: Lomonaco, S.J. (ed.) Quantum Information Science and Its Contributions to Mathematics. Proceedings of Symposia in Applied Mathe- matics, vol. 68, p. 13. Amer. Math. Soc., Rhode Island (2010).
  18. Lidar, D. A. & Brun, T. A. (eds.) Quantum Error Correction. Cambridge University Press, Cambridge, UK http://www.cambridge.org/9780521897877 (2013).
  19. Raussendorf, R. & Harrington, J. Fault-tolerant quantum computation with high threshold in two dimensions. Phys. Rev. Lett. 98, 190504 (2007).
  20. Fowler, A. G., Mariantoni, M., Martinis, J. M. & Cleland, A. N. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. 86, 032324 (2012).
  21. Yoder, T. J. & Kim, I. H. The surface code with a twist. Quantum 1, 2 (2017).
  22. Bravyi, S., Englbrecht, M., König, R. & Peard, N. Correcting coherent errors with surface codes. npj Quantum Inf. 4, 55 (2018).
  23. Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009).
  24. Bremner, M. J., Montanaro, A. & Shepherd, D. J. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum 1, 8 (2017).
  25. Napp, J. C., La Placa, R. L., Dalzell, A. M., Brandão, F. G. S. L. & Harrow, A. W. Efficient classical simulation of random shallow 2d quantum circuits. Phys. Rev. 12, 021021 (2022).
  26. Noh, K., Jiang, L. & Fefferman, B. Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum 4, 318 (2020).
  27. Barak, B., Chou, C. & Gao, X. Spoofing linear cross-entropy benchmarking in shallow quantum circuits. Preprint at https://arxiv.org/abs/2005.02421 (2020). · arXiv
  28. Boixo, S., Isakov, S. V., Smelyanskiy, V. N. & Neven, H. Simulation of low-depth quantum circuits as complex undirected graphical models. Preprint at https:// arxiv.org/abs/1712.05384 (2017). · arXiv
  29. Chow, J. M. et al. Universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits. Phys. Rev. Lett. 109, 060501 (2012).
  30. Chen, Y. et al. Qubit architecture with high coherence and fast tunable coupling. Phys. Rev. Lett. 113, 220502 (2014).
  31. Sheldon, S., Magesan, E., Chow, J. M. & Gambetta, J. M. Procedure for systematically tuning up cross-talk in the cross-resonance gate. Phys. Rev. 93, 060302 (2016).
  32. Kjaergaard, M. et al. A quantum instruction set implemented on a superconducting quantum processor. Preprint at https://arxiv.org/abs/2001.08838 (2020). · arXiv
  33. Kalachev, G., Panteleev, P. & Yung, M.-H. Multi-Tensor Contraction for XEB Ver- ification of Quantum Circuits. Preprint at https://arxiv.org/abs/2108.05665 (2021). · arXiv
  34. Pan, F., Chen, K. & Zhang, P. Solving the sampling problem of the sycamore quantum circuits. Phys. Rev. Lett. 129, 090502 (2022).
  35. Villalonga, B. et al. A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware. npj Quantum Inf. 5, 86 (2019).
  36. Chen, J., Zhang, F., Huang, C., Newman, M. & Shi, Y. Classical simulation of intermediate-size quantum circuits. Preprint at https://arxiv.org/abs/1805.01450 (2018). · arXiv
  37. Liu, Y. A. et al. Closing the "quantum supremacy" gap: Achieving real-time simulation of a random quantum circuit using a new sunway supercomputer. In: Int. Conf. High. Perfor. SC '21. Association for Computing Machinery, New York, NY, USA https://doi.org/10.1145/3458817.3487399 (2021). · DOI
  38. Dalzell, A. M., Harrow, A. W., Koh, D. E. & La Placa, R. L. How many qubits are needed for quantum computational supremacy? Quantum 4, 264 (2020).
  39. Pokharel, B. & Lidar, D. A. Demonstration of algorithmic quantum speedup. Preprint at https://arxiv.org/abs/2207.07647 (2022). · arXiv
  40. Albash, T. & Lidar, D. A. Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Phys. Rev. 8, 031016 (2018).
  41. Denchev, V. S. et al. What is the computational value of finite-range tunneling? Phys. Rev. 6, 031015 (2016).
  42. Quintana, C. M. et al. Observation of classical-quantum crossover of 1/f flux noise and its paramagnetic temperature dependence. Phys. Rev. Lett. 118, 057702 (2017).

Cited by

Sorted by citations

Metadata

Authors
Zlokapa, A., Boixo, S., & Lidar, D.
Affiliations
  • California Institute of Technology (US)
  • Google (United States) (US)
  • University of Southern California (US)
Corresponding author
Zlokapa, Alexander
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
9
Issue
1
ISSN
2056-6387 (ISSN-L)
DOI
10.48550/arxiv.2005.02464
arXiv
2005.02464
OpenAlex
W3022917190
Cited by
55
References
0
Citations by year
2026: 7 · 2025: 12 · 2024: 14 · 2023: 9 · 2022: 1 · 2021: 9 · 2020: 3
FWCI
3.72
Type
journal article
Language
en
Open access
Licence
Locations
  • npj Quantum Information (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. Department of Energy (DESC0019227)
  • Oracle
  • California Institute of Technology
  • High Energy Physics (DE-SC0019227)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum advantage, random circuit sampling, circuit depth, qubit number, gate fidelity, error rate, surface code, error correction, scalable quantum computing, classical simulation

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