Quantum learning algorithms imply circuit lower bounds
Srinivasan Arunachalam, Alex B. Grilo, et al.
FOCS 2021
Learning the Hamiltonian that describes interactions in a quantum system is an important task in both condensed-matter physics and the verification of quantum technologies. Its classical analogue arises as a central problem in machine learning known as learning Boltzmann machines. Previously, the best known methods for quantum Hamiltonian learning with provable performance guarantees required a number of measurements that scaled exponentially with the number of particles. Here we prove that only a polynomial number of local measurements on the thermal state of a quantum system are necessary and sufficient for accurately learning its Hamiltonian. We achieve this by establishing that the absolute value of the finite-temperature free energy of quantum many-body systems is strongly convex with respect to the interaction coefficients. The framework introduced in our work provides a theoretical foundation for applying machine learning techniques to quantum Hamiltonian learning, achieving a long-sought goal in quantum statistical learning.
Srinivasan Arunachalam, Alex B. Grilo, et al.
FOCS 2021
Diego Ristè, Luke Govia, et al.
APS March Meeting 2020
Lorenzo Laneve, Francesco Tacchino, et al.
Quantum
Muir Kumph, James Raftery, et al.
APS March Meeting 2021