Polynomial-time classical algorithms for mean-field models up to the glass transition
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.
Related
- Shifted Pell–Lucas Polynomial-Based Algorithms for Fractional and Classical Rosenau–Hyman Models
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
- Polynomial-Time Algorithms for Links
- Integrable Generators of Polynomial Vector Fields for Complex Classical Lie Groups
BibTeX
@misc{schmidhuber2026polynomialtime,
title = {{Polynomial-time classical algorithms for mean-field models up to the glass transition}},
author = {Alexander Schmidhuber and Alexander Zlokapa},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06807},
eprint = {2610.06807},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06807},
}
RIS
TY - UNPB
TI - Polynomial-time classical algorithms for mean-field models up to the glass transition
AU - Alexander Schmidhuber
AU - Alexander Zlokapa
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06807
UR - https://arxiv.org/abs/2610.06807
AB - 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.
ER -