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

Provable bounds for noise-free expectation values computed from noisy samples

Open access
Barron, Samantha V., Egger, Daniel J., Pelofske, Elijah, Bärtschi, Andreas, Eidenbenz, Stephan, Lehmkuehler, Matthis, Woerner, Stefan·2024·Nature Computational Science
DOI 10.1038/s43588-024-00709-1PMC PMC11578887
Open this paper in CoChat — free accountOpen PDF

Abstract

Quantum computing has emerged as a powerful computational paradigm capable of solving problems beyond the reach of classical computers. However, today’s quantum computers are noisy, posing challenges to obtaining accurate results. Here, we explore the impact of noise on quantum computing, focusing on the challenges in sampling bit strings from noisy quantum computers and the implications for optimization and machine learning. We formally quantify the sampling overhead to extract good samples from noisy quantum computers and relate it to the layer fidelity, a metric to determine the performance of noisy quantum processors. Further, we show how this allows us to use the conditional value at risk of noisy samples to determine provable bounds on noise-free expectation values. We discuss how to leverage these bounds for different algorithms and demonstrate our findings through experiments on real quantum computers involving up to 127 qubits. The results show strong alignment with theoretical predictions. In this study, the authors investigate the impact of noise on quantum computing with a focus on the challenges in sampling bit strings from noisy quantum computers, which has implications for optimization and machine learning.

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.1038/s43588-024-00709-1

Cites

11 of 11 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?

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

  1. [2]Ollitrault, P. J., Miessen, A. & Tavernelli, I. Molecular quantum dynamics: a quantum computing perspective. Acc. Chem. Res. 54, 4229–4238 (2021). 34787398 · DOI
  2. [3]Di Meglio, A. et al. Quantum computing for high-energy physics: state of the art and challenges. PRX Quantum 5, 037001 (2024). · DOI
  3. [4]Barkoutsos, P. K. et al. Quantum algorithm for alchemical optimization in material design. Chem. Sci. 12, 4345–4352 (2021). 34163697 PMC8179438 · DOI
  4. [6]Zoufal, C., Lucchi, A. & Woerner, S. Quantum generative adversarial networks for learning and loading random distributions. npj Quantum Inf. 5, 103 (2019). · DOI · Paper page
  5. [7]Zoufal, C., Lucchi, A. & Woerner, S. Variational quantum Boltzmann machines. Quantum Mach. Intell. 3, 7 (2021). · DOI
  6. [8]Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at 10.48550/arXiv.1411.4028 (2014). · DOI · Paper page
  7. [11]Sack, S. H. & Egger, D. J. Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation. Phys. Rev. Res. 6, 013223 (2024). · DOI
  8. [12]Abbas, A. et al. Quantum optimization: potential, challenges, and the path forward. Preprint at 10.48550/arXiv.2312.02279 (2023). · DOI
  9. [13]Egger, D. J. et al. Quantum computing for finance: state-of-the-art and future prospects. IEEE Trans. Quantum Eng. 1, 3101724 (2020). · DOI
  10. [14]Lidar, D. A. & Brun, T. A. Quantum Error Correction (Cambridge Univ. Press, 2013).
  11. [16]Piveteau, C., Sutter, D. & Woerner, S. Quasiprobability decompositions with reduced sampling overhead. npj Quantum Inf. 8, 12 (2022). · DOI
  12. [17]Temme, K., Bravyi, S. & Gambetta, J. M. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett. 119, 180509 (2017). 29219599 · DOI · Paper page
  13. [18]Kim, Y. et al. Evidence for the utility of quantum computing before fault tolerance. Nature 618, 500–505 (2023). 37316724 PMC10266970 · DOI · Paper page
  14. [19]Anand, S., Temme, K., Kandala, A. & Zaletel, M. Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime. Preprint at 10.48550/arXiv.2306.17839 (2023). · DOI
  15. [20]Bravyi, S., Dial, O., Gambetta, J. M., Gil, D. & Nazario, Z. The future of quantum computing with superconducting qubits. J. Appl. Phys. 132, 160902 (2022). · DOI · Paper page
  16. [21]Zoufal, C. et al. Variational quantum algorithm for unconstrained black box binary optimization: application to feature selection. Quantum 7, 909 (2023). · DOI
  17. [22]Letcher, A., Woerner, S. & Zoufal, C. From tight gradient bounds for parameterized quantum circuits to the absence of barren plateaus in QGANs. Quantum 8, 1484 (2024). · DOI
  18. [23]Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I. & Woerner, S. Improving variational quantum optimization using CVaR. Quantum 4, 256 (2020). · DOI · Paper page
  19. [24]McKay, D. C. et al. Benchmarking quantum processor performance at scale. Preprint at 10.48550/arXiv.2311.05933 (2023). · DOI · Paper page
  20. [25]Sachdeva, N. et al. Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems. Preprint at 10.48550/arXiv.2406.01743 (2024). · DOI
  21. [26]Wurtz, J. & Love, P. MaxCut quantum approximate optimization algorithm performance guarantees for p > 1. Phys. Rev. A 103, 042612 (2021). · DOI
  22. [27]Gentinetta, G., Thomsen, A., Sutter, D. & Woerner, S. The complexity of quantum support vector machines. Quantum 8, 1225 (2024). · DOI
  23. [28]Gentinetta, G., Sutter, D., Zoufal, C., Fuller, B. & Woerner, S. Quantum kernel alignment with stochastic gradient descent. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 256–262 (IEEE, 2023).
  24. [29]McArdle, S. et al. Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Inf. 5, 75 (2019). · DOI · Paper page
  25. [30]Yuan, X., Endo, S., Zhao, Q., Li, Y. & Benjamin, S. C. Theory of variational quantum simulation. Quantum 3, 191 (2019). · DOI · Paper page
  26. [31]Zoufal, C., Sutter, D. & Woerner, S. Error bounds for variational quantum time evolution. Phys. Rev. Appl. 20, 044059 (2023). · DOI
  27. [32]Gacon, J., Zoufal, C., Carleo, G. & Woerner, S. Simultaneous perturbation stochastic approximation of the quantum Fisher information. Quantum 5, 567 (2021). · DOI
  28. [33]Gacon, J., Zoufal, C., Carleo, G. & Woerner, S. Stochastic approximation of variational quantum imaginary time evolution. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 129–139 (IEEE, 2023).
  29. [34]Gacon, J., Nys, J., Rossi, R., Woerner, S. & Carleo, G. Variational quantum time evolution without the quantum geometric tensor. Phys. Rev. Res. 6, 013143 (2024). · DOI
  30. [35]Weidenfeller, J. et al. Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware. Quantum 6, 870 (2022). · DOI
  31. [37]Fuller, B. et al. Approximate solutions of combinatorial problems via quantum relaxations. IEEE Trans. Quantum Eng. 5, 3102615 (2024). · DOI
  32. [38]Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014). · DOI · Paper page
  33. [40]Sack, S. H. & Serbyn, M. Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum 5, 491 (2021). · DOI
  34. [41]Ozaeta, A., van Dam, W. & McMahon, P. L. Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems. Quantum Sci. Technol. 7, 045036 (2022). · DOI
  35. [42]Hadfield, S. et al. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12, 34 (2019). · DOI · Paper page
  36. [43]Bärtschi, A. & Eidenbenz, S. Short-depth circuits for Dicke state preparation. In 2022 IEEE International Conference on Quantum Computing & Engineering (QCE) 87–96 (IEEE, 2022).
  37. [45]Wang, Z., Rubin, N. C., Dominy, J. M. & Rieffel, E. G. X Y mixers: analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A 101, 012320 (2020). · DOI · Paper page
  38. [46]Cook, J., Eidenbenz, S. & Bärtschi, A. The quantum alternating operator ansatz on maximum k-vertex cover. In 2020 IEEE International Conference on Quantum Computing & Engineering (QCE) 83–92 10.1109/QCE49297.2020.00021 (IEEE, 2020). · DOI
  39. [47]Golden, J., Bärtschi, A., Eidenbenz, S. & O’Malley, D. Numerical evidence for exponential speed-up of QAOA over unstructured search for approximate constrained optimization. In 2023 IEEE International Conference on Quantum Computing & Engineering (QCE) 496–505 10.1109/QCE57702.2023.00063 (IEEE, 2023). · DOI
  40. [49]Sheldon, S., Magesan, E., Chow, J. M. & Gambetta, J. M. Procedure for systematically tuning up cross-talk in the cross-resonance gate. Phys. Rev. A 93, 060302 (2016). · DOI
  41. [50]Javadi-Abhari, A. et al. Quantum computing with Qiskit. Preprint at 10.48550/arXiv.2405.08810 (2024). · DOI
  42. [52]Nation, P. D., Kang, H., Sundaresan, N. & Gambetta, J. M. Scalable mitigation of measurement errors on quantum computers. PRX Quantum 2, 040326 (2021). · DOI
  43. [55]Pelofske, E., Bärtschi, A. & Eidenbenz, S. Quantum annealing vs. QAOA: 127 qubit higher-order Ising problems on NISQ computers. In High Performance Computing. ISC High Performance 2023 (eds Bhatele, A. et al.) 240–258 (Springer, 2023).
  44. [56]Pelofske, E., Bärtschi, A. & Eidenbenz, S. Short-depth QAOA circuits and quantum annealing on higher-order Ising models. npj Quantum Inf. 10, 30 (2024). · DOI
  45. [57]Chamberland, C., Zhu, G., Yoder, T. J., Hertzberg, J. B. & Cross, A. W. Topological and subsystem codes on low-degree graphs with flag qubits. Phys. Rev. X 10, 011022 (2020).
  46. [58]Pelofske, E., Bärtschi, A., Cincio, L., Golden, J. & Eidenbenz, S. Scaling whole-chip QAOA for higher-order Ising spin glass models on heavy-hex graphs. Preprint at 10.48550/arXiv.2312.00997 (2023). · DOI
  47. [61]Dankert, C., Cleve, R., Emerson, J. & Livine, E. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A 80, 012304 (2009). · DOI
  48. [62]Magesan, E., Gambetta, J. M. & Emerson, J. Scalable and robust randomized benchmarking of quantum processes. Phys. Rev. Lett. 106, 180504 (2011). 21635076 · DOI
  49. [63]Kokosaka, S. & Zwillinger, D. CRC Standard Probability and Statistics Tables and Formulae (CRC Press, 2000).
  50. [64]Zhang, Z., Chen, S., Liu, Y. & Jiang, L. A generalized cycle benchmarking algorithm for characterizing mid-circuit measurements. Preprint at 10.48550/arXiv.2406.02669 (2024). · DOI
  51. [65]Koh, J. M., Koh, D. E. & and Thompson, J. Readout error mitigation for mid-circuit measurements and feedforward. Preprint at 10.48550/arXiv.2406.07611 (2024). · DOI
  52. [66]Hines, J. & Proctor, T. Pauli noise learning for mid-circuit measurements. Preprint at 10.48550/arXiv.2406.09299 (2024). 39913840 · DOI
  53. [68]Gokhale, P. et al. Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families. Preprint at 10.48550/arXiv.1907.13623 (2019). · DOI
  54. [71]Woerner, S. stefan-woerner/provable_bounds_cvar: provable bounds for noise-free expectation values computed from noisy samples. Zenodo10.5281/zenodo.13738011 (2024). PMC11578887 39487271

Cited by

Sorted by citations

Authors
Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkuehler, M., & Woerner, S.
Affiliations
  • IBM (United States) (US)
  • IBM Research - Zurich (CH)
  • Los Alamos National Laboratory (US)
  • University of Basel (CH)
Corresponding author
Woerner, Stefan
ORCID
Venue
Nature Computational Science
Publisher
Springer Science and Business Media LLC
Published
2024-11-01
Volume
4
Issue
11
Pages
865-875
ISSN
2662-8457 (ISSN-L)
DOI
10.1038/s43588-024-00709-1
PMC
PMC11578887
OpenAlex
W4403984119
Cited by
25
References
11
Citations by year
2026: 9 · 2025: 10 · 2024: 5 · 2023: 1
FWCI
3.54
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature Computational Science (publishedVersion, cc-by-nc-nd)
  • PubMed Central (publishedVersion, cc-by-nc-nd)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Science Foundation (89233218CNA000001)
  • U.S. Department of Energy (#89233218CNA000001)
  • Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (214919)
  • National Nuclear Security Administration (89233218C-NA000001, No. 89233218CNA000001)
  • Los Alamos National Laboratory (89233218CNA 000001)
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
noisy quantum computers, sampling overhead, conditional value at risk, quantum sampling, quantum optimization, quantum machine learning

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