Learning quantum Hamiltonians at any temperature in polynomial time

• Published in: arXiv.org 2023-10
• Main Authors: Bakshi, Ainesh, Liu, Allen, Moitra, Ankur, Tang, Ewin
• Format: Article
• Language: English
• Subjects: Algorithms; Commutators; Exponential functions; Hamiltonian functions; High temperature; Machine learning; Polynomials; Qubits (quantum computing)
• ISSN: 2331-8422

We study the problem of learning a local quantum Hamiltonian \(H\) given copies of its Gibbs state \(\rho = e^{-\beta H}/\textrm{tr}(e^{-\beta H})\) at a known inverse temperature \(\beta>0\). Anshu, Arunachalam, Kuwahara, and Soleimanifar (arXiv:2004.07266) gave an algorithm to learn a Hamiltonian on \(n\) qubits to precision \(\epsilon\) with only polynomially many copies of the Gibbs state, but which takes exponential time. Obtaining a computationally efficient algorithm has been a major open problem [Alhambra'22 (arXiv:2204.08349)], [Anshu, Arunachalam'22 (arXiv:2204.08349)], with prior work only resolving this in the limited cases of high temperature [Haah, Kothari, Tang'21 (arXiv:2108.04842)] or commuting terms [Anshu, Arunachalam, Kuwahara, Soleimanifar'21]. We fully resolve this problem, giving a polynomial time algorithm for learning \(H\) to precision \(\epsilon\) from polynomially many copies of the Gibbs state at any constant \(\beta > 0\). Our main technical contribution is a new flat 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 suffices to accurately learn the Hamiltonian.