Classical algorithms for quantum Gibbs states
summary
Claims a rigorous classical algorithm that estimates local thermal expectations for SYK by proving a zero‑free disk around β=0 and using Barvinok-style Taylor continuation and a disorder-driven cluster expansion, yielding a quasi‑polynomial N^{O(log N/ε)} runtime for constant β up to a k‑dependent cutoff. Shows SYK has no constant‑β phase transition nonrigorously (and rigorously up to a concrete β), contrasts that Gibbs purifications require many quantum gates, and presents a quantum Kikuchi approach that gives a quartic time speedup and polynomial space advantage for planted hypergraph inference.
AI-written summary · about
chapters (9)
- 0:00Classical Gibbs state algorithms
- 3:16Chemistry and random Hamiltonians
- 10:26SYK model as non-stoquastic
- 17:57Barvinok’s partition function
- 22:32Zero-free disks in SYK
- 39:14Spin glasses and replica symmetry
- 46:04Pauli Hamiltonians and clusters
- 53:16Thermodynamics for inference
- 1:00:34Open questions and future
related talks
44mOptimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
38mQuantum Computational Advantage With Constant-Temperature Gibbs Sampling
30mQuantum Thermal Simulation
44mEmergence of Universal Randomness in Quantum Many-body Dynamics
01h 06mQuantum Algorithms for Approximating Partition Functions
59mOptimizing Noncommutative Polynomials: The SYK Model
36mA Combinatorial Approach to Complexity Transitions in Quantum Physics
01h 15mDissipative State Preparation and the Dissipative Quantum Eigensolver