Classically Estimating Observables of Noiseless Quantum Circuits
Creators
-
1.
École Polytechnique Fédérale de Lausanne
-
2.
Massachusetts Institute of Technology
-
3.
Los Alamos National Laboratory
-
4.
Google (United States)
-
5.
California Institute of Technology
Abstract
We present a classical algorithm based on Pauli propagation for estimating expectation values of arbitrary observables on random unstructured quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that, for any architecture where each circuit layer is randomly sampled from a distribution invariant under single-qubit rotations, our algorithm achieves a small error 𝜖 on all circuits except for a small fraction 𝛿. The computational time is polynomial in qubit count and circuit depth for any small constant 𝜖, 𝛿 and quasipolynomial for inverse-polynomially small 𝜖, 𝛿. Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.
Copyright and License
© 2025 American Physical Society.
Acknowledgement
The authors thank Sergio Boixo, Su Yeon Chang, Soonwon Choi, Soumik Ghosh, Sacha Lerch, Jarrod R. McClean, Antonio Anna Mele, Thomas Schuster, and Yanting Teng for valuable discussions and feedback. A. A. and Z. H. acknowledge support from the Sandoz Family Foundation-Monique de Meuron program for Academic Promotion. A. S. acknowledges support by the Simons Foundation (MP-SIP-00001553, AWH) and National Science Foundation Grant No. PHY-2325080. M. S. R. acknowledges support by the Swiss National Science Foundation (Grant No. 200021-219329). M. C. acknowledges support by the Laboratory Directed Research and Development (LDRD) program of Los Alamos National Laboratory (LANL) under Projects No. 20230527ECR and No. 20230049DR. This work was also supported by LANL’s ASC Beyond Moore’s Law project.
Data Availability
The data that support the findings of this article are openly available [80].
Supplemental Material
The Supplemental Material contains the rigorous mathematical derivations of all the main results provided in the Main Text, as well as additional ancillary results and numerical experiments. The intuition behind our main results is also provided in the Main Text, and several proof sketches are included in the End Matter.
Files
lh6x-7rc3.pdf
Files
(1.5 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:4205bd4d71ca424b024d592319c79f53
|
552.6 kB | Preview Download |
|
md5:60282df0bad3ac64b58e6830f6058c45
|
981.4 kB | Preview Download |
Additional details
Related works
- Is new version of
- Discussion Paper: arXiv:2409.01706 (arXiv)
- Is supplemented by
- Dataset: arXiv:2505.21606 (arXiv)
- Supplemental Material: https://journals.aps.org/prl/supplemental/10.1103/lh6x-7rc3/press_supp.pdf (URL)
Funding
- Sandoz Family Foundation
- Simons Foundation
- MP-SIP-00001553
- National Science Foundation
- PHY-2325080
- Swiss National Science Foundation
- 200021-219329
- Los Alamos National Laboratory
- 20230527ECR
- Los Alamos National Laboratory
- 20230049DR
Dates
- Accepted
-
2025-09-08