Learning Many-Body Hamiltonians with Heisenberg-Limited Scaling
Creators
Abstract
Learning a many-body Hamiltonian from its dynamics is a fundamental problem in physics. In this Letter, we propose the first algorithm to achieve the Heisenberg limit for learning an interacting ๐-qubit local Hamiltonian. After a total evolution time of ๐ชโก(๐โป¹), the proposed algorithm can efficiently estimate any parameter in the ๐-qubit Hamiltonian to ๐ error with high probability. Our algorithm uses ideas from quantum simulation to decouple the unknown ๐-qubit Hamiltonian ๐ป into noninteracting patches and learns ๐ป using a quantum-enhanced divide-and-conquer approach. The proposed algorithm is robust against state preparation and measurement error, does not require eigenstates or thermal states, and only uses polylogโก(๐โป¹) experiments. In contrast, the best existing algorithms require ๐ชโก(๐โป²) experiments and total evolution time. We prove a matching lower bound to establish the asymptotic optimality of our algorithm.
Copyright and License
© 2023 American Physical Society.
Acknowledgement
The authors thank Matthias Caro, Richard Kueng, Lin Lin, Jarrod McClean, Praneeth Netrapalli, and John Preskill for valuable input and inspiring discussions. H.-Y. H. is supported by a Google Ph.D. fellowship and a MediaTek Research Young Scholarship. Y. T. is supported in part by the U.S. Department of Energy Office of Science (DE-SC0019374), Office of Advanced Scientific Computing Research (DE-SC0020290), Office of High Energy Physics (DE-ACO2-07CH11359), and under the Quantum System Accelerator project. Work supported by DE-SC0020290 is supported by the DOE QuantISED program through the theory consortium “Intersections of QIS and Theoretical Particle Physics” at Fermilab. The Institute for Quantum Information and Matter is a NSF Physics Frontiers Center. D. F. is supported by NSF Quantum Leap Challenge Institute (QLCI) program under Grant No. OMA-2016245, NSF DMS-2208416, and a grant from the Simons Foundation under Grant No. 825053.
Contributions
H.-Y. H. and Y. T. contributed equally to this work.
Data Availability
Files
PhysRevLett.130.200403.pdf
Files
(966.0 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:61c49f3842184d8bfdaa157d0172af10
|
468.2 kB | Preview Download |
|
md5:60a61c4883d04f9b70914f88de749924
|
497.8 kB | Preview Download |
Additional details
Identifiers
- ISSN
- 1079-7114
Funding
- Google (United States)
- Google PhD Fellowship
- MediaTek (Singapore)
- United States Department of Energy
- DE-SC0019374
- United States Department of Energy
- DE-SC0020290
- United States Department of Energy
- DE-ACO2-07CH11359
- California Institute of Technology
- Institute for Quantum Information and Matter
- National Science Foundation
- OSI-2016245
- National Science Foundation
- DMS-2208416
- Simons Foundation
- 825053