CoChat
Sign Up
Cited by 28Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

Bell Sampling from Quantum Circuits

Open access
Hangleiter, Dominik, Gullans, Michael J.·2024·Physical Review Letters
DOI 10.1103/physrevlett.133.020601
Open this paper in CoChat — free accountOpen PDF

Abstract

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this Letter, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone toward fault tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a "circuit shadow": from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give several new and efficient protocols: an estimator of state fidelity, an error-mitigated estimator of Pauli expectation values, a test for the depth of a circuit, and an algorithm to estimate a lower bound on the number of T gates in the circuit. With some additional measurements, the latter algorithm can be used to learn a full description of states prepared by circuits with low T count.

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

Crossref · 10.1103/physrevlett.133.020601

Cites

58 of 59 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?

  • Bell-basis measurements between two copies of the same state are a powerful method to extract various quantities of interest.

    “A powerful method to extract various quantities of interest are Bell-basis measurements between two copies of the same state21,22,52.”

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

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: 56

  1. Y. Liu, M. Otten, R. Bassirianjahromi, L. Jiang, and B. Feffer- man, Benchmarking Near-Term Quantum Computers via Ran- dom Circuit Sampling, (2022), arXiv:2105.05232. · arXiv
  2. M. Heinrich, M. Kliesch, and I. Roth, General Guarantees for Randomized Benchmarking with Random Quantum Circuits, (2022), arXiv:2212.06181. · arXiv
  3. A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengtsson, P. V. Klimov, Z. Chen, S. Hong, C. Erickson, I. K. Droz- dov, J. Chau, G. Laun, R. Movassagh, A. Asfaw, L. T. A. N. Brandão, R. Peralta, D. Abanin, R. Acharya, R. Allen, T. I. An- dersen, and others, Phase Transition in Random Circuit Sam- pling, (2023), arXiv:2304.11119. · arXiv
  4. Y.-H. Deng, Y.-C. Gu, H.-L. Liu, S.-Q. Gong, H. Su, Z.-J. Zhang, H.-Y. Tang, M.-H. Jia, J.-M. Xu, M.-C. Chen, H.-S. Zhong, J. Qin, H. Wang, L.-C. Peng, J. Yan, Y. Hu, J. Huang, H. Li, Y. Li, Y. Chen, and others, Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quan- tum Computational Advantage, (2023), arXiv:2304.12240. · arXiv
  5. B. Ware, A. Deshpande, D. Hangleiter, P. Niroula, B. Fef- ferman, A. V. Gorshkov, and M. J. Gullans, A Sharp Phase Transition in Linear Cross-Entropy Benchmarking, (2023), arXiv:2305.04954. · arXiv
  6. S. Aaronson and A. Arkhipov, The Computational Complexity of Linear Optics, Th. Comp. 9, 143 (2013). · DOI
  7. A. Montanaro, Learning Stabilizer States by Bell Sampling, (2017), arXiv:1707.04012. · arXiv
  8. T. Haug, S. Lee, and M. S. Kim, Efficient Stabilizer Entropies for Quantum Computers, (2023), arXiv:2305.19152. · arXiv
  9. R. Movassagh, Quantum Supremacy and Random Circuits, (2020), arXiv:1909.06210. · arXiv
  10. H. Krovi, Average-Case Hardness of Estimating Probabilities of Random Quantum Circuits with a Linear Scaling in the Error Exponent, (2022), arXiv:2206.05642. · arXiv
  11. D. Gottesman, An Introduction to Quantum Error Cor- rection and Fault-Tolerant Quantum Computation, (2009), arXiv:0904.2557. · arXiv
  12. A. Winick, J. J. Wallman, D. Dahlen, I. Hincks, E. Ospadov, and J. Emerson, Concepts and Conditions for Error Suppression through Randomized Compiling, (2022), arXiv:2212.07500. · arXiv
  13. S. Arunachalam, S. Bravyi, C. Nirkhe, and B. O'Gorman, The Parameterized Complexity of Quantum Verification, (2022), arXiv:2202.08119. · arXiv
  14. L. Leone, S. F. E. Oliviero, S. Lloyd, and A. Hamma, Learn- ing Efficient Decoders for Quasi-Chaotic Quantum Scramblers, (2023), arXiv:2212.11338. · arXiv
  15. M. Guta, J. Kahn, R. Kueng, and J. A. Tropp, Fast State Tomog- raphy with Optimal Error Bounds, (2018), arXiv:1809.11162. · arXiv
  16. A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and C. Macchiavello, Stabilisation of Quantum Computations by Symmetrisation, (1996), arXiv:quant-ph/9604028. · arXiv
  17. X. Gao and L. Duan, Efficient Classical Simulation of Noisy Quantum Computation, (2018), arXiv:1810.03176. · arXiv
  18. S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates, (2023), arXiv:2305.13409. · arXiv
  19. N. Hunter-Jones, Unitary Designs from Statistical Mechanics in Random Quantum Circuits, (2019), arXiv:1905.12053. · arXiv
  20. A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandão, Random Quantum Circuits Transform Local Noise into Global White Noise, (2021), arXiv:2111.14907. · arXiv
  21. M. Ringbauer, M. Hinsche, T. Feldker, P. K. Faehrmann, J. Bermejo-Vega, C. Edmunds, L. Postler, R. Stricker, C. D. Marciniak, M. Meth, I. Pogorelov, R. Blatt, P. Schindler, J. Eis- ert, T. Monz, and D. Hangleiter, Verifiable Measurement- Based Quantum Random Sampling with Trapped Ions, (2023), arXiv:2307.14424. · arXiv
  22. S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Ef- ficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements, (2023), arXiv:2308.07175. · arXiv
  23. M. B. Hastings, Locality in Quantum Systems, (2010), arXiv:1008.5137 [math-ph]. · arXiv
  24. D. Hangleiter and J. Eisert, Computational Advantage of Quan- tum Random Sampling, Rev. Mod. Phys. 95, 035001 (2023). · DOI · Paper page
  25. M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average- Case Complexity Versus Approximate Simulation of Commuting Quantum Computations, Physical Review Letters 117, 080501 (2016). · DOI · Paper page
  26. H. Krovi, Average-Case Hardness of Estimating Probabilities of Random Quantum Circuits with a Linear Scaling in the Error Exponent, (2022), arXiv:2206.05642. · arXiv
  27. H. Zhu, R. Kueng, M. Grassl, and D. Gross, The Clifford Group Fails Gracefully to Be a Unitary 4-Design, (2016), arXiv:1609.08172. · arXiv
  28. F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Lo- cal Random Quantum Circuits Are Approximate Polynomial- Designs, Commun. Math. Phys. 346, 397 (2016). · DOI · Paper page
  29. T. Zhou and A. Nahum, Emergent Statistical Mechanics of Entanglement in Random Unitary Circuits, Phys. Rev. B 99, 174205 (2019). · DOI
  30. N. Hunter-Jones, Unitary Designs from Statistical Mechanics in Random Quantum Circuits, (2019), arXiv:1905.12053. · arXiv
  31. B. Barak, C.-N. Chou, and X. Gao, Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits, in 12th Innovations in Theoretical Computer Science Confer- ence (ITCS 2021), Leibniz International Proceedings in In- formatics (LIPIcs), Vol. 185, edited by J. R. Lee (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2021) pp. 30:1-30:20, arXiv:2005.02421. · DOI
  32. A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandão, Random Quantum Circuits Anticoncentrate in Log Depth, PRX Quantum 3, 010333 (2022). · DOI
  33. J. J. Wallman and J. Emerson, Noise Tailoring for Scalable Quantum Computation via Randomized Compiling, Phys. Rev. A 94, 052325 (2016). · DOI · Paper page
  34. B. Ware, A. Deshpande, D. Hangleiter, P. Niroula, B. Fef- ferman, A. V. Gorshkov, and M. J. Gullans, A Sharp Phase Transition in Linear Cross-Entropy Benchmarking, (2023), arXiv:2305.04954. · arXiv
  35. A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengtsson, P. V. Klimov, Z. Chen, S. Hong, C. Erickson, I. K. Droz- dov, J. Chau, G. Laun, R. Movassagh, A. Asfaw, L. T. A. N. Brandão, R. Peralta, D. Abanin, R. Acharya, R. Allen, T. I. An- dersen, and others, Phase Transition in Random Circuit Sam- pling, (2023), arXiv:2304.11119. · arXiv
  36. G. M. Sommers, D. A. Huse, and M. J. Gullans, Crystalline Quantum Circuits, PRX Quantum 4, 030313 (2023). · DOI
  37. A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandão, Random Quantum Circuits Transform Local Noise into Global White Noise, (2021), arXiv:2111.14907. · arXiv
  38. J. Choi, A. L. Shaw, I. S. Madjarov, X. Xie, R. Finkelstein, J. P. Covey, J. S. Cotler, D. K. Mark, H.-Y. Huang, A. Kale, H. Pich- ler, F. G. S. L. Brandão, S. Choi, and M. Endres, Preparing Random States and Benchmarking with Many-Body Quantum Chaos, Nature 613, 468 (2023). · DOI
  39. M. Ringbauer, M. Hinsche, T. Feldker, P. K. Faehrmann, J. Bermejo-Vega, C. Edmunds, L. Postler, R. Stricker, C. D. Marciniak, M. Meth, I. Pogorelov, R. Blatt, P. Schindler, J. Eis- ert, T. Monz, and D. Hangleiter, Verifiable Measurement- Based Quantum Random Sampling with Trapped Ions, (2023), arXiv:2307.14424. · arXiv
  40. S. T. Flammia and Y.-K. Liu, Direct Fidelity Estimation from Few Pauli Measurements, Phys. Rev. Lett. 106, 230501 (2011). · DOI · Paper page
  41. J. F. Fitzsimons and E. Kashefi, Unconditionally Verifiable Blind Quantum Computation, Phys. Rev. A 96, 012303 (2017). · DOI
  42. B. W. Reichardt, F. Unger, and U. Vazirani, Classical Com- mand of Quantum Systems, Nature 496, 456 (2013). · DOI
  43. U. Mahadev, Classical Verification of Quantum Computations, in 2018 IEEE 59th Annual Symposium on Foundations of Com- puter Science (FOCS) (2018) pp. 259-267. · DOI
  44. D. N. Page, Average Entropy of a Subsystem, Phys. Rev. Lett. 71, 1291 (1993). · DOI · Paper page
  45. S. Garnerone, T. R. de Oliveira, and P. Zanardi, Typicality in Random Matrix Product States, Phys. Rev. A 81, 032336 (2010). · DOI
  46. B. Collins, C. E. Gonzalez-Guillen, and D. Perez-Garcia, Ma- trix Product States, Random Matrix Theory and the Principle of Maximum Entropy, Communications in Mathematical Physics 320, 663 (2013). · DOI
  47. M. Fukuda and R. Koenig, Typical Entanglement for Gaussian States, Journal of Mathematical Physics 60, 112203 (2019). · DOI
  48. J. T. Iosue, A. Ehrenberg, D. Hangleiter, A. Deshpande, and A. V. Gorshkov, Page Curves and Typical Entanglement in Lin- ear Optics, Quantum 7, 1017 (2023). · DOI
  49. A. Montanaro, Learning Stabilizer States by Bell Sampling, (2017), arXiv:1707.04012. · arXiv
  50. H.-Y. Huang, R. Kueng, and J. Preskill, Information-Theoretic Bounds on Quantum Advantage in Machine Learning, Phys. Rev. Lett. 126, 190505 (2021). · DOI
  51. V. Mnih, C. Szepesvári, and J.-Y. Audibert, Empirical Bern- stein Stopping, in Proceedings of the 25th International Con- ference on Machine Learning, ICML '08 (Association for Com- puting Machinery, Helsinki, Finland, 2008) pp. 672-679. · DOI
  52. P. Erdös and A. Rényi, Probabilistic Methods in Group Theory, J. Anal. Math. 14, 127 (1965). · DOI
  53. S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Ef- ficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements, (2023), arXiv:2308.07175. · arXiv
  54. M. B. Hastings, Locality in Quantum Systems, (2010), arXiv:1008.5137 [math-ph]. · arXiv
  55. X. Gao and L. Duan, Efficient Classical Simulation of Noisy Quantum Computation, (2018), arXiv:1810.03176. · arXiv
  56. D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, A Polynomial-Time Classical Algorithm for Noisy Random Cir- cuit Sampling, (2022), arXiv:2211.03999. · arXiv

Cited by

Sorted by citations

Related

Authors
Hangleiter, D., & Gullans, M. J.
Affiliations
Joint Center for Quantum Information and Computer Science (US)
Corresponding author
Hangleiter, Dominik
ORCID
Venue
Physical Review Letters
Publisher
American Physical Society (APS)
Published
2024-07-08
Volume
133
Issue
2
Pages
020601-020601
ISSN
  • 0031-9007 (ISSN-L)
  • 1079-7114
DOI
10.1103/physrevlett.133.020601
OpenAlex
W4400413075
Cited by
28
References
59
Citations by year
2026: 7 · 2025: 19 · 2024: 1 · 2023: 1
FWCI
4.00
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical Review Letters (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (OMA-2120757, PHY-1748958)
  • U.S. Department of Defense
  • QuICS Hartree fellowship
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 circuit verification, quantum benchmarking, error mitigation, fault tolerance, quantum computing

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