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

The DOI matches its DataCite record; its reference list is not available.

Phase transition in Random Circuit Sampling

Open access
Morvan, A., Villalonga, B., Mi, X., Mandrà, S., Bengtsson, A., Klimov, P. V., Chen, Z., Hong, S., Erickson, C., Drozdov, I. K., Chau, J., Laun, G., Movassagh, R., Asfaw, A., Brandão, L. T. A. N., Peralta, R., Abanin, D., Acharya, R., Allen, R., Andersen, T. I., Anderson, K., Ansmann, M., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Bilmes, A., Bortoli, G., Bourassa, A., Bovaird, J., Brill, L., Broughton, M., Buckley, B. B., Buell, D. A., Burger, T., Burkett, B., Bushnell, N., Campero, J., Chang, H. S., Chiaro, B., Chik, D., Chou, C., Cogan, J., Collins, R., Conner, P., Courtney, W., Crook, A. L., Curtin, B., Debroy, D. M., Barba, A. Del Toro, Demura, S., Di Paolo, A., Dunsworth, A., Faoro, L., Farhi, E., Fatemi, R., Ferreira, V. S., Burgos, L. Flores, Forati, E., Fowler, A. G., Foxen, B., Garcia, G., Genois, E., Giang, W., Gidney, C., Gilboa, D., Giustina, M., Gosula, R., Dau, A. Grajales, Gross, J. A., Habegger, S., Hamilton, M. C., Hansen, M., Harrigan, M. P., Harrington, S. D., Heu, P., Hoffmann, M. R., Huang, T., Huff, A., Huggins, W. J., Ioffe, L. B., Isakov, S. V., Iveland, J., Jeffrey, E., Jiang, Z., Jones, C., Juhas, P., Kafri, D., Khattar, T., Khezri, M., Kieferová, M., Kim, S., Kitaev, A., Klots, A. R., Korotkov, A. N., Kostritsa, F., Kreikebaum, J. M., Landhuis, D., Laptev, P., Lau, K. -M., Laws, L., Lee, J., Lee, K. W., Lensky, Y. D., Lester, B. J., Lill, A. T., Liu, W., Livingston, W. P., Locharla, A., Malone, F. D., Martin, O., Martin, S., McClean, J. R., McEwen, M., Miao, K. C., Mieszala, A., Montazeri, S., Mruczkiewicz, W., Naaman, O., Neeley, M., Neill, C., Nersisyan, A., Newman, M., Ng, J. H., Nguyen, A., Nguyen, M., Niu, M. Yuezhen, O'Brien, T. E., Omonije, S., Opremcak, A., Petukhov, A., Potter, R., Pryadko, L. P., Quintana, C., Rhodes, D. M., Rosenberg, E., Rocque, C., Roushan, P., Rubin, N. C., Saei, N., Sank, D., Sankaragomathi, K., Satzinger, K. J., Schurkus, H. F., Schuster, C., Shearn, M. J., Shorter, A., Shutty, N., Shvarts, V., Sivak, V., Skruzny, J., Smith, W. C., Somma, R. D., Sterling, G., Strain, D., Szalay, M., Thor, D., Torres, A., Vidal, G., Heidweiller, C. Vollgraff, White, T., Woo, B. W. K., Xing, C., Yao, Z. J., Yeh, P., Yoo, J., Young, G., Zalcman, A., Zhang, Y., Zhu, N., Zobrist, N., Rieffel, E. G., Biswas, R., Babbush, R., Bacon, D., Hilton, J., Lucero, E., Neven, H., Megrant, A., Kelly, J., Aleiner, I., Smelyanskiy, V., Kechedzhi, K., Chen, Y., Boixo, S.·2023·arXiv
DOI 10.48550/arxiv.2304.11119arXiv 2304.11119PMC PMC11464376
Open this paper in CoChat — free accountOpen PDF

Abstract

Undesired coupling to the surrounding environment destroys long-range correlations on quantum processors and hinders the coherent evolution in the nominally available computational space. This incoherent noise is an outstanding challenge to fully leverage the computation power of near-term quantum processors. It has been shown that benchmarking Random Circuit Sampling (RCS) with Cross-Entropy Benchmarking (XEB) can provide a reliable estimate of the effective size of the Hilbert space coherently available. The extent to which the presence of noise can trivialize the outputs of a given quantum algorithm, i.e. making it spoofable by a classical computation, is an unanswered question. Here, by implementing an RCS algorithm we demonstrate experimentally that there are two phase transitions observable with XEB, which we explain theoretically with a statistical model. The first is a dynamical transition as a function of the number of cycles and is the continuation of the anti-concentration point in the noiseless case. The second is a quantum phase transition controlled by the error per cycle; to identify it analytically and experimentally, we create a weak link model which allows varying the strength of noise versus coherent evolution. Furthermore, by presenting an RCS experiment with 67 qubits at 32 cycles, we demonstrate that the computational cost of our experiment is beyond the capabilities of existing classical supercomputers, even when accounting for the inevitable presence of noise. Our experimental and theoretical work establishes the existence of transitions to a stable computationally complex phase that is reachable with current quantum processors.

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

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?

  • 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 [103]

    Appendix A (pp. 10–11) develops XEB for general random circuit sampling, and the main text (p. 2) describes when XEB estimates fidelity. Searches for IQP circuits and a comparison with Haar-random circuits found no passage addressing whether XEB is a better benchmark for IQP circuits. (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.

Citations

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

References 38 · Cited by 138

Research works printed but not linked: 34

  1. [5]K. Zyczkowski and H.-J. Sommers, Induced measures in the space of mixed quantum states, Journal of Physics A: Mathematical and General 34 , 7111 (2001).
  2. [7]R. Barends, C. M. Quintana, A. G. Petukhov, Y. Chen, D. Kafri, K. Kechedzhi, R. Collins, O. Naaman, S. Boixo, F. Arute, K. Arya, D. Buell, B. Burkett, Z. Chen, B. Chiaro, A. Dunsworth, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, T. Huang, E. Jeffrey, J. Kelly, P. V. Klimov, F. Kostritsa, D. Landhuis, E. Lucero, M. McEwen, A. Megrant, X. Mi, J. Mutus, M. Neeley, C. Neill, E. Ostby, P. Roushan, D. Sank, K. J. Satzinger, A. Vainsencher, T. White, J. Yao, P. Yeh, A. Zalcman, H. Neven, V. N. Smelyanskiy, and J. M. Martinis, Diabatic gates for frequency-tunable superconducting qubits, Physical Review Letters 123 , 210501 (2019).
  3. [9]P. V. Klimov, J. Kelly, J. M. Martinis, and H. Neven, The snake optimizer for learning quantum processor control parameters (2020), arXiv:2006.04594. · arXiv
  4. [11]X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, Limitations of linear cross-entropy as a measure for quantum advantage, arXiv:2112.01657 (2021). · arXiv
  5. [13]B. Barak, C.-N. Chou, and X. Gao, Spoofing linear cross-entropy benchmarking in shallow quantum circuits, arXiv:2005.02421 (2020). · arXiv
  6. [14]D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, A polynomial-time classical algorithm for noisy random circuit sampling, arXiv:2211.03999 (2022). · arXiv
  7. [15]I. L. Markov, A. Fatima, S. V. Isakov, and S. Boixo, Quantum supremacy is both closer and farther than it appears, arXiv:1807.10749 (2018). · arXiv
  8. [16]I. L. Markov and Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM Journal on Computing 38 , 963 (2008).
  9. [17]S. Boixo, S. V. Isakov, V. N. Smelyanskiy, and H. Neven, Simulation of low-depth quantum circuits as complex undirected graphical models, arXiv:1712.05384 (2017). · arXiv
  10. [19]C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan, M. Szegedy, Y. Shi, and J. Chen, Classical simulation of quantum supremacy circuits, arXiv:2005.06787 (2020). · arXiv
  11. [20]G. Kalachev, P. Panteleev, and M.-H. Yung, Multitensor contraction for xeb verification of quantum circuits, arXiv:2108.05665 (2021). · arXiv
  12. [21]G. Kalachev, P. Panteleev, P. Zhou, and M.-H. Yung, Classical sampling of random quantum circuits with bounded fidelity, arXiv:2112.15083 (2021). · arXiv
  13. [22]F. Pan, K. Chen, and P. Zhang, Solving the sampling problem of the sycamore quantum circuits, Physical Review Letters 129 , 090502 (2022).
  14. [23]Y. Liu, Y. Chen, C. Guo, J. Song, X. Shi, L. Gan, W. Wu, W. Wu, H. Fu, X. Liu, D. Chen, G. Yang, and J. Gao, Validating quantum-supremacy experiments with exact and fast tensor network contraction, arXiv:2212.04749 (2022). · arXiv
  15. [24]J. Chen, F. Zhang, C. Huang, M. Newman, and Y. Shi, Classical simulation of intermediate-size quantum circuits, arXiv:1805.01450 (2018). · arXiv
  16. [26]Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, Q. Zhu, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.W. Pan, Strong quantum computational advantage using a superconducting quantum processor, Physical Review Letters 127 , 180501 (2021).
  17. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Quantum computational advantage via 60qubit 24-cycle random circuit sampling, Science Bulletin 67 , 240 (2022).
  18. [28]Y. Zhou, E. M. Stoudenmire, and X. Waintal, What limits the simulation of quantum computers?, Physical Review X 10 , 041038 (2020).
  19. [29]T. Ayral, T. Louvet, Y. Zhou, C. Lambert, E. M. Stoudenmire, and X. Waintal, A density-matrix renormalisation group algorithm for simulating quantum circuits with a finite fidelity, arXiv:2207.05612 (2022). · arXiv
  20. [31]R. Oliveira, O. Dahlsten, and M. Plenio, Generic entanglement can be generated efficiently, Physical Review Letters 98 , 130502 (2007).
  21. [33]R. Movassagh and A. Edelman, Isotropic entanglement, arXiv:1012.5039 (2010). · arXiv
  22. [35]K. M. Audenaert and M. B. Plenio, Entanglement on mixed stabilizer states: normal forms and reduction procedures, New Journal of Physics 7 , 170 (2005).
  23. [37]R. Bassirian, A. Bouland, B. Fefferman, S. Gunn, and A. Tal, On certified randomness from quantum advantage experiments, arXiv:2111.14846 (2021). · arXiv
  24. [38]S. Aaronson and S.-H. Hung, Certified randomness from quantum supremacy, arXiv:2303.01625 (2023). · arXiv
  25. [40]Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick, A cryptographic test of quantumness and certifiable randomness from a single quantum device, in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2018) pp. 320-331.
  26. [41]U. Mahadev, U. Vazirani, and T. Vidick, Efficient certifiable randomness from a single quantum device, arXiv:2204.11353 (2022). · arXiv
  27. [42]M.-H. Yung and B. Cheng, Anti-forging quantum data: Cryptographic verification of quantum computational power, arXiv:2005.01510 (2020). · arXiv
  28. [44]L. Trevisan, Extractors and pseudorandom generators, Journal of the ACM 48 , 860 (2001).
  29. [45]L. Brand˜ ao and R. Peralta, Notes on interrogating random quantum circuits, National Institute of Standards and Technology (2020), doi: 10.13140/RG.2.2.24562.94400. · DOI
  30. [46]F. Pan and P. Zhang, Simulating the sycamore quantum supremacy circuits, arXiv:2103.03074 (2021). · arXiv
  31. [48]R. Raz, O. Reingold, and S. Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Journal of Computer and System Sciences 65 , 97 (2002).
  32. [49]W. Mauerer, C. Portmann, and V. B. Scholz, A modular framework for randomness extraction based on trevisan's construction, arXiv:1212.0520 (2012). · arXiv
  33. [51]X. Ma, F. Xu, H. Xu, X. Tan, B. Qi, and H.-K. Lo, Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction, Physical Review A 87 , 062327 (2013).
  34. [53]Y. Dodis, R. Gennaro, J. H˚ astad, H. Krawczyk, and T. Rabin, Randomness extraction and key derivation using the cbc, cascade and hmac modes, in Advances in Cryptology - CRYPTO 2004 , edited by M. Franklin (Springer Berlin Heidelberg, Berlin, Heidelberg, 2004) pp. 494-510.

Metadata

Authors
Morvan, A., Villalonga, B., Mi, X., Mandrà, S., Bengtsson, A., Klimov, P. V., Chen, Z., Hong, S., Erickson, C., Drozdov, I. K., Chau, J., Laun, G., Movassagh, R., Asfaw, A., Brandão, L. T. A. N., Peralta, R., Abanin, D., Acharya, R., Allen, R., Andersen, T. I., Anderson, K., Ansmann, M., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Bilmes, A., Bortoli, G., Bourassa, A., Bovaird, J., Brill, L., Broughton, M., Buckley, B. B., Buell, D. A., Burger, T., Burkett, B., Bushnell, N., Campero, J., Chang, H. S., Chiaro, B., Chik, D., Chou, C., Cogan, J., Collins, R., Conner, P., Courtney, W., Crook, A. L., Curtin, B., Debroy, D. M., Barba, A. D. T., Demura, S., Di Paolo, A., Dunsworth, A., Faoro, L., Farhi, E., Fatemi, R., Ferreira, V. S., Burgos, L. F., Forati, E., Fowler, A. G., Foxen, B., Garcia, G., Genois, E., Giang, W., Gidney, C., Gilboa, D., Giustina, M., Gosula, R., Dau, A. G., Gross, J. A., Habegger, S., Hamilton, M. C., Hansen, M., Harrigan, M. P., Harrington, S. D., Heu, P., Hoffmann, M. R., Huang, T., Huff, A., Huggins, W. J., Ioffe, L. B., Isakov, S. V., Iveland, J., Jeffrey, E., Jiang, Z., Jones, C., Juhas, P., Kafri, D., Khattar, T., Khezri, M., Kieferová, M., Kim, S., Kitaev, A., Klots, A. R., Korotkov, A. N., Kostritsa, F., Kreikebaum, J. M., Landhuis, D., Laptev, P., Lau, K. M., Laws, L., Lee, J., Lee, K. W., Lensky, Y. D., Lester, B. J., Lill, A. T., Liu, W., Livingston, W. P., Locharla, A., Malone, F. D., Martin, O., Martin, S., McClean, J. R., McEwen, M., Miao, K. C., Mieszala, A., Montazeri, S., Mruczkiewicz, W., Naaman, O., Neeley, M., Neill, C., Nersisyan, A., Newman, M., Ng, J. H., Nguyen, A., Nguyen, M., Niu, M. Y., O'Brien, T. E., Omonije, S., Opremcak, A., Petukhov, A., Potter, R., Pryadko, L. P., Quintana, C., Rhodes, D. M., Rosenberg, E., Rocque, C., Roushan, P., Rubin, N. C., Saei, N., Sank, D., Sankaragomathi, K., Satzinger, K. J., Schurkus, H. F., Schuster, C., Shearn, M. J., Shorter, A., Shutty, N., Shvarts, V., Sivak, V., Skruzny, J., Smith, W. C., Somma, R. D., Sterling, G., Strain, D., Szalay, M., Thor, D., Torres, A., Vidal, G., Heidweiller, C. V., White, T., Woo, B. W. K., Xing, C., Yao, Z. J., Yeh, P., Yoo, J., Young, G., Zalcman, A., Zhang, Y., Zhu, N., Zobrist, N., Rieffel, E. G., Biswas, R., Babbush, R., Bacon, D., Hilton, J., Lucero, E., Neven, H., Megrant, A., Kelly, J., Aleiner, I., Smelyanskiy, V., Kechedzhi, K., Chen, Y., & Boixo, S.
Affiliations
  • Google (United States) (US)
  • Ames Research Center (US)
  • National Institute of Standards and Technology (US)
  • University of Technology Sydney (AU)
  • University of California, Riverside (US)
Corresponding author
Kechedzhi, K.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
Volume
634
Issue
8033
Pages
328-333
ISSN
0028-0836 (ISSN-L)
DOI
10.48550/arxiv.2304.11119
arXiv
2304.11119
PMC
PMC11464376
OpenAlex
W4403244104
Cited by
138
References
38
Citations by year
2026: 38 · 2025: 65 · 2024: 26 · 2023: 9
FWCI
19.00
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature (publishedVersion, cc-by-nc-nd)
  • PubMed Central (publishedVersion, cc-by-nc-nd)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • RePEc: Research Papers in Economics (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Aeronautics and Space Administration (80ARC020D0010)
  • Agence Nationale de la Recherche (ANR-22-PETQ-0007)
  • Ames Research Center (80ARC020D0010)
  • Advanced Research Projects Agency
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 › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
random circuit sampling, quantum phase transitions, dynamical phase transitions, anti-concentration, computational complexity

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