An (almost) efficient classical algorithm for sampling from typical Gibbs states

arXiv:2609.40250 · quant-ph · Submitted 2026-09-30 · Read on arXiv

quant-ph

Submitted: 2026-09-30

Updated: 2026-10-05

Terminology

• Stochastic Localization — 40× in this paper
• Gibbs State — 13× in this paper · explained in 2 episodes
• Trace — 7× in this paper · explained in 2 episodes
• SYK Model — 6× in this paper · explained in 2 episodes
• Wasserstein Distance — 6× in this paper · explained in 4 episodes
• Phase Transitions — 3× in this paper · explained in 2 episodes
• Accuracy — 2× in this paper · explained in 1 episode
• Foundations of Computer Science — 2× in this paper
• Quantum Circuits — 2× in this paper · explained in 2 episodes
• Adam — 1× in this paper · explained in 2 episodes
• Adaptivity — 1× in this paper · explained in 1 episode
• Diffusion Model — 1× in this paper · explained in 8 episodes
• Diffusion Models — 1× in this paper · explained in 6 episodes
• Hubbard Model — 1× in this paper · explained in 3 episodes

Sources

• Proofs for Folklore Theorems on the Radon-Nikodym Derivative
• Optimizing random local Hamiltonians by dissipation
• Statistical Mechanics of Equilibrium and Nonequilibrium Phase Transitions: The Yang-Lee Formalism
• The Lee-Yang theory of equilibrium and nonequilibrium phase transitions
• Parisi Formula for the ground state energy of quantum p-Spin Hamiltonians
• Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
• Slow Mixing of Quantum Gibbs Samplers
• The replica symmetric region in the Sherrington-Kirkpatrick mean field spin glass model. The Almeida-Thouless line
• Total Variation Guarantees for Sampling with Stochastic Localization
• A simplified version of the quantum OTOC$^{(2)}$ problem
• Quantum spin glasses and Sachdev-Ye-Kitaev models
• A Bosonic Model of Quantum Holography
• Quantum Language Processing
• SYK thermal expectations are classically easy at any temperature
• Average-case quantum complexity from glassiness
• A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity