Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155708 |
| _version_ | 1824458323568623616 |
|---|---|
| author | Bakshi, Ainesh Liu, Allen Moitra, Ankur Tang, Ewin |
| author2 | Massachusetts Institute of Technology. Department of Mechanical Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Mechanical Engineering Bakshi, Ainesh Liu, Allen Moitra, Ankur Tang, Ewin |
| author_sort | Bakshi, Ainesh |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T14:52:33Z |
| format | Article |
| id | mit-1721.1/155708 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:24:04Z |
| publishDate | 2024 |
| publisher | ACM STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557082025-01-02T05:03:29Z Learning Quantum Hamiltonians at Any Temperature in Polynomial Time Bakshi, Ainesh Liu, Allen Moitra, Ankur Tang, Ewin 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 Science STOC ’24, June 24–28, 2024, Vancouver, BC, Canada 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. 2024-07-18T16:06:37Z 2024-07-18T16:06:37Z 2024-06-10 2024-07-01T07:47:05Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155708 Bakshi, Ainesh, Liu, Allen, Moitra, Ankur and Tang, Ewin. 2024. "Learning Quantum Hamiltonians at Any Temperature in Polynomial Time." PUBLISHER_CC en 10.1145/3618260.3649619 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Bakshi, Ainesh Liu, Allen Moitra, Ankur Tang, Ewin Learning Quantum Hamiltonians at Any Temperature in Polynomial Time |
| title | Learning Quantum Hamiltonians at Any Temperature in Polynomial Time |
| title_full | Learning Quantum Hamiltonians at Any Temperature in Polynomial Time |
| title_fullStr | Learning Quantum Hamiltonians at Any Temperature in Polynomial Time |
| title_full_unstemmed | Learning Quantum Hamiltonians at Any Temperature in Polynomial Time |
| title_short | Learning Quantum Hamiltonians at Any Temperature in Polynomial Time |
| title_sort | learning quantum hamiltonians at any temperature in polynomial time |
| url | https://hdl.handle.net/1721.1/155708 |
| work_keys_str_mv | AT bakshiainesh learningquantumhamiltoniansatanytemperatureinpolynomialtime AT liuallen learningquantumhamiltoniansatanytemperatureinpolynomialtime AT moitraankur learningquantumhamiltoniansatanytemperatureinpolynomialtime AT tangewin learningquantumhamiltoniansatanytemperatureinpolynomialtime |