arXiv preprint ·
Polynomial-time classical algorithms for mean-field models up to the glass transition
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Fast mixing of the SYK model at high temperatures
Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data
A Solvable Model of Adaptive Learning Rate Rescaling: Acceleration, Stability & Scaling
Classifications in modular restricted Boltzmann machines
Observing the magic Mpemba effect in localized dynamics on a digital quantum computer
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.