Optimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
summary
Proves optimal sample complexity for learning L‑local n‑qubit Hamiltonian coefficients from high‑temperature Gibbs states (beta below a constant): sample count matches classical lower bounds and yields a polynomial‑time algorithm. Uses cluster expansion / multivariate Taylor series of the log partition function to express local marginals as low‑degree polynomials in the lambdas, proves a bounded Jacobian inverse (Lipschitz relation marginals→coefficients), estimates local expectations with simple local measurements (no shadows), and solves the truncated polynomial system by Newton's method in O(log(1/(beta epsilon))) iterations.
AI-written summary · about
chapters (12)
- 0:00Intro
- 6:35Classical Hamiltonians
- 11:50Markov Random Field
- 17:40HighTemperature Learning
- 25:32Cluster Expansion
- 27:02System of polynomial equations
- 29:27Classical algorithm
- 32:17Questions
- 35:12Lower Bounds
- 35:57Classical Hamiltonian
- 38:42Bounds
- 40:52Motivation
related talks
38mQuantum Computational Advantage With Constant-Temperature Gibbs Sampling
01h 08mFast mixing of all-to-all quantum systems at high temperatures
16mRobust Quantum Entanglement at (nearly) Room Temperature
01h 07mClassical algorithms for quantum Gibbs states
54mLearning the structure of open quantum systems
30mQuantum Thermal Simulation
46mLocal Minima in Quantum Systems
01h 26mQuantum Gibbs Sampling