Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

Abstract

We study the problem of learning a Hamiltonian $H$ to precision $\epsilon$, supposing we are given copies of its Gibbs state $\rho =\exp (-\beta H)/\mathrm{Tr}(\exp (-\beta H))$ at a known inverse temperature $\beta$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of $\rho$ needed) of this problem for geometrically local $N$-qubit Hamiltonians. In the high-temperature (low $\beta$) regime, their algorithm has sample complexity poly$(N,1/\beta ,1/\epsilon )$ and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\epsilon$ with sample complexity $S=O(\log N/(\beta \epsilon {)}^2)$ and time complexity linear in the sample size, $O(SN)$. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e^{-itH}$ in a small $t$ regime with similar sample and time complexity.

55 pages, v2: incorporated reviewer comments, improved exposition of appendix; v3: fixed a problem with Lemma 3.9 tracing back to prior work

References in corpus (2)

• Learning many-body Hamiltonians with Heisenberg-limited scaling
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

Cited by in corpus (24)

• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
• On the Sample Complexity of Quantum Boltzmann Machine Learning
• Optimal quantum algorithm for Gibbs state preparation
• Measurement-Induced Entanglement Phase Transition in Free Fermion Systems
• Hamiltonian and Liouvillian learning in weakly-dissipative quantum many-body systems
• The power and limitations of learning quantum dynamics incoherently
• Hamiltonian learning for 300 trapped ion qubits with long-range couplings
• Structure learning of Hamiltonians from real-time evolution
• Machine learning of quantum channels on NISQ devices
• Clustering of conditional mutual information and quantum Markov structure at arbitrary temperatures
• Hamiltonian Learning using Machine Learning Models Trained with Continuous Measurements
• Learning interacting fermionic Hamiltonians at the Heisenberg limit
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Finite temperature tensor network algorithm for frustrated two-dimensional quantum materials
• Nearly query-optimal classical shadow estimation of unitary channels
• Quantum natural gradient with thermal-state initialization
• Lieb-Robinson bounds with exponential-in-volume tails
• Learning the structure of any Hamiltonian from minimal assumptions
• Stability of thermal equilibrium in long-range quantum systems
• High-temperature partition functions and classical simulatability of long-range quantum systems
• Optimal Hamiltonian recognition of unknown quantum dynamics
• Characterizing errors in parameter estimation by local measurements
• Learning mixed quantum states in large-scale experiments
• Short remarks on shallow unitary circuits