PIRSA:21060002

Video URL

https://pirsa.org/21060002

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

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

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 

          @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/pirsa/21060002}}
          }

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

Talk numberPIRSA:21060002
DOI10.48660/21060002
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

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.