Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper presents polynomial-time classical algorithms for estimating local thermal expectations in the Sachdev-Ye-Kitaev (SYK) model, extending previous quasipolynomial-time results to all constant temperatures. The work resolves an open question regarding classical spin glasses and introduces a rigorous quantum cavity method, which is expected to have broader applications. The developed techniques also yield a polynomial-time and sample complexity quantum algorithm for learning SYK Hamiltonians from their Gibbs state.
Classical algorithms can now compute thermal expectations for the SYK model and classical spin glasses in polynomial time, even near their phase transitions.
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.