arXiv:2610.06807
Polynomial-time classical algorithms for mean-field models up to the glass transition
Alexander Schmidhuber, Alexander Zlokapa
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.
AI Summary
The paper asks whether local thermal observables of disordered mean-field models can be computed classically in polynomial rather than quasipolynomial time, beyond regimes accessible to high-temperature expansions. It treats the quartic Sachdev–Ye–Kitaev (SYK) model and zero-field Gaussian Ising $p$-spin models. For SYK, it gives a deterministic classical algorithm estimating any fixed-weight Majorana observable at every fixed inverse temperature $\beta\geq0$. For fixed $a,c>0$, the additive error is at most $N^{-c}$ with probability at least $1-N^{-a}$ over the couplings, in time $N^{C(\beta,w,a,c)}$. For Ising $p$-spin models, it obtains simultaneous Euclidean error $N^{-c}$ for all bounded-degree spin expectations and additive error $N^{-c}$ for $\log Z$, at every fixed $\beta<\beta_*$, the static glass transition; for SK, this means $\beta<1$. The central ingredient is a rigorous quantum cavity argument establishing finite-size concentration around the SYK Schwinger–Dyson saddle. Spectral rounding and weak measurements provide conditional factorization, followed by controlled restoration of detailed balance. The algorithm combines a Hermite expansion in disorder with a truncated hierarchy of collective moments and inversion of the ladder kernel. SK instead uses logarithmic-degree graph expansions and deterministic color coding. An application learns SYK couplings from Gibbs-state copies using $O_\beta(N^{5+2c}\log(N/\delta))$ samples for normalized coupling error $N^{-c}$, with $0<c<1$. The guarantees concern typical Gaussian instances, fixed temperatures and observable weights; they do not establish efficient Gibbs sampling or growing-time dynamics, which remain proposed directions. Polynomial runtime exponents depend on the fixed parameters.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 63 + 107 pages, 4 figures