Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
Author(s)
Bakshi, Ainesh; Liu, Allen; Moitra, Ankur; Tang, Ewin
Download3618260.3649619.pdf (210.6Kb)
Publisher with Creative Commons License
Publisher with Creative Commons License
Creative Commons Attribution
Terms of use
Metadata
Show full item recordAbstract
We study the problem of learning a local quantum Hamiltonian
given copies of its Gibbs state =
− /tr(
− ) at a known
inverse temperature > 0. Anshu, Arunachalam, Kuwahara, and
Soleimanifar gave an algorithm to learn a Hamiltonian on qubits
to precision with only polynomially many copies of the Gibbs
state, but which takes exponential time. Obtaining a computationally e cient algorithm has been a major open problem, with prior
work only resolving this in the limited cases of high temperature or
commuting terms. We fully resolve this problem, giving a polynomial time algorithm for learning to precision from polynomially
many copies of the Gibbs state at any constant > 0.
Our main technical contribution is a new at polynomial approximation to the exponential function, and a translation between
multi-variate scalar polynomials and nested commutators. This enables us to formulate Hamiltonian learning as a polynomial system.
We then show that solving a low-degree sum-of-squares relaxation
of this polynomial system su ces to accurately learn the Hamiltonian.
Description
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
Date issued
2024-06-10Department
Massachusetts Institute of Technology. Department of Mechanical Engineering; Massachusetts Institute of Technology. Department of Mathematics; Massachusetts Institute of Technology. Department of Electrical Engineering and Computer SciencePublisher
ACM STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Citation
Bakshi, Ainesh, Liu, Allen, Moitra, Ankur and Tang, Ewin. 2024. "Learning Quantum Hamiltonians at Any Temperature in Polynomial Time."
Version: Final published version
ISBN
979-8-4007-0383-6
Collections
The following license files are associated with this item: