PIRSA:21060002

Time-efficient learning of quantum Hamiltonians from high-temperature Gibbs states

APA

Haah, J. (2021). Time-efficient learning of quantum Hamiltonians from high-temperature Gibbs states. Perimeter Institute for Theoretical Physics. https://pirsa.org/21060002

MLA

Haah, Jeongwan. Time-efficient learning of quantum Hamiltonians from high-temperature Gibbs states. Perimeter Institute for Theoretical Physics, Jun. 09, 2021, https://pirsa.org/21060002

BibTex

          @misc{ scivideos_PIRSA:21060002,
            doi = {10.48660/21060002},
            url = {https://pirsa.org/21060002},
            author = {Haah, Jeongwan},
            keywords = {Quantum Information},
            language = {en},
            title = {Time-efficient learning of quantum Hamiltonians from high-temperature Gibbs states},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2021},
            month = {jun},
            note = {PIRSA:21060002 see, \url{https://scivideos.org/index.php/pirsa/21060002}}
          }
          

Jeongwan Haah Massachusetts Institute of Technology (MIT) - Department of Physics

Talk numberPIRSA:21060002
Source RepositoryPIRSA

Abstract

We study the problem of learning a Hamiltonian given copies of its Gibbs state at a known inverse temperature. Anshu et al. recently studied the sample complexity (number of copies of the Gibbs state needed) of this problem for geometrically local Hamiltonians. In the high-temperature regime, their algorithm has sample complexity polynomial in the system size, temperature, and accuracy. Their algorithm can also be implemented with polynomial, but suboptimal, time complexity. Here, we study the same question for a more general class of Hamiltonians and present an algorithm that solves this problem with improved sample complexity and time complexity linear in the sample size. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. Joint work with Robin Kothari and Ewin Tang.