Can classical algorithms compute mean-field thermal expectations up to the glass transition?

What the polynomial-time claim actually covers

The paper answers a question left open by earlier work. Classical algorithms could already estimate local thermal expectations of the SYK model at sufficiently high temperature, but only in quasipolynomial time. This work shows that local observables can be estimated at all constant temperatures in polynomial time.

The distinction matters because the two results are not the same kind of guarantee. A quasipolynomial-time algorithm scales like exp(polylog N); a polynomial-time algorithm scales like N^k for fixed k. The paper also extends the techniques to classical systems, resolving an open question about computing thermal expectations of a classical spin glass up to its phase transition.

The claim is about estimating local observables, not about representing the full thermal state. The abstract notes that Gaussian states are far from the thermal state and that representing it requires large polynomial-size quantum circuits. The algorithmic result concerns local expectations, which is a narrower target than full state preparation.

Why SYK looked classically hard

The SYK model is defined on Majorana fermions with random four-body interactions, and it has been studied heavily in condensed matter and holography. The paper lists several obstructions that suggested classical hardness: a sign problem, entanglement, magic, and the large quantum circuit complexity of its thermal state.

Unlike the classical Ising p-spin model, the SYK model has no thermodynamic phase transition at any temperature. That removes one obstacle but not the others. The earlier rigorous classical algorithm for SYK was based on proving zero-free regions of the partition function in the complex β-plane, and the paper states that those techniques likely break down.

The prior high-temperature cluster expansion also appears to break at constant temperature. So the gap was not just a matter of optimizing constants; a different proof technique was needed to reach all constant temperatures.

The quantum cavity method in plain terms

The main technical step is showing concentration of the empirical two-point field around the saddle point solution G*. The paper proves this using the cavity method, which proceeds by iteratively reducing from N+1 to N sites: each fermion is removed from interacting with the rest of the Hamiltonian and is instead coupled to a free bath.

In the classical version, adding a spin σ_{N+1} with fresh disorder lets one write the new partition function in terms of a cavity expectation. If correlators factorize into products of local expectations, the cavity spin feels an effective Hamiltonian that can be solved easily. The quantum version replaces the interacting bath of the added Majorana fermion with a quadratic bath of free fermion modes of energy x_j and couplings v_j.

The paper emphasizes that making this rigorous for SYK is difficult. Directly showing factorization of four-point correlators is hard, and earlier rigorous work on the annealed free energy used a de Finetti theorem for operator algebras. The construction here instead uses spectral rounding, measurement, and restoration of detailed balance to achieve concentration strong enough for the algorithm.

From concentration to a polynomial-time algorithm

The concentration bound is stated as Theorem 4: for a Hermitian linear combination B of finitely many operators of the form built from ψ_i and G*, the normalized trace of e^{βH} B^{2m} is bounded by C^m N^{-δm/(4r+4)}. This decay in N improves with the moment order m, which is what allows the expansion to achieve arbitrary inverse polynomial error.

The cavity computation chooses the bath energies and couplings so that the self-energy Σ equals β²G³, matching the SYK saddle point equations by construction. Lemma 17 shows that the resulting quadratic Hamiltonian's two-point function D(Σ) can be represented as a free-fermion two-point function.

Once G and Σ approximate the N→∞ solution, the algorithm expands around G*, Σ* using the ladder kernel. The paper notes that controlling the error requires the concentration bound first, which is difficult without a quantum cavity method. In the classical Ising p-spin case, a similar resummation is needed for p=2 but not p≥3, which admits a simpler algorithm due to a trivial Hessian; both settings still require a cavity proof of concentration.

The classical spin glass result and its threshold

For the classical Ising p-spin model with p≥3, the model has a spin glass phase. Cooling from infinite temperature gets stuck in a metastable state at a dynamical transition 1/β_d, and at that transition a large family of natural algorithms, such as low-degree or stable algorithms, also fail to sample from the Gibbs measure.

Earlier work showed that quasipolynomial-time algorithms can still estimate thermal expectations of local observables at some β > β_d, using Barvinok's interpolation method. That technique typically succeeds above a thermodynamic phase transition, where the free energy density becomes non-analytic in the N→∞ limit. For the Ising p-spin model, the phase transition occurs at a colder temperature 1/β* below the dynamical transition 1/β_d.

The open question was whether thermal expectations can be efficiently estimated all the way to β*. This paper resolves that question for the classical spin glass, extending the techniques straightforwardly from the quantum case. The relevant threshold is the thermodynamic phase transition β*, not the dynamical transition β_d.

Learning SYK Hamiltonians from the Gibbs state

As an application, the paper gives a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity. This improves on prior work that obtained a quasipolynomial-time algorithm for learning SYK coefficients from polynomially many copies of a high-temperature Gibbs state, with polynomial sample complexity at all temperatures.

The learning algorithm measures Hamiltonian terms and accounts for the leading-order correction, described in physics terms as the 1/N mean-field correction, to recover the couplings. In diagrammatic language, it uses the leading order and 1/N correction directly from the saddle point solution, then uses the cavity method to bound the higher-order remainder.

The paper states that because of the quantum cavity method, the algorithm and its analysis are fairly straightforward. This is a case where the proof technique, not a new measurement primitive, drives the improvement.

Where the guarantees stop

The polynomial-time guarantee applies to estimating local thermal expectations at all constant temperatures. The paper does not claim polynomial time for temperatures that scale with system size, nor does it claim efficient preparation of the full thermal state. The abstract explicitly contrasts local expectations with representing the thermal state, which requires large polynomial-size quantum circuits.

The classical spin glass result is stated for computing thermal expectations up to the phase transition. The paper describes the extension to classical systems as straightforward, but the threshold remains the thermodynamic phase transition, not beyond it.

The paper also notes that the rigorous classical algorithm it improves upon was based on zero-free regions in the complex β-plane, and that those techniques likely break down. The new approach is a formal quantum cavity method, and the paper expects it to find further applications in optimization, sampling, inference, and learning, but those are stated as expectations rather than proved results.

What to watch in the cavity construction

The most decision-relevant comparison in this paper is between the dynamical transition β_d and the thermodynamic phase transition β*. Natural algorithms fail at β_d, and earlier rigorous algorithms reached some β > β_d. This work reaches β* for the classical spin glass and all constant temperatures for SYK. The gap that remains is between β* and zero temperature, not between β_d and β*.

A second comparison is between quasipolynomial and polynomial time. The earlier SYK result was quasipolynomial; this one is polynomial. For readers assessing whether a classical simulation is practical, the polynomial scaling is the relevant change, and it comes from the concentration bound whose decay improves with moment order.

The paper's own framing points to the quantum cavity method as the transferable contribution. The specific algorithmic wins are the SYK thermal expectation algorithm, the SYK Hamiltonian learning algorithm, and the classical spin glass result up to β*. The expectation of further applications is explicitly labeled as an expectation, so readers should treat the proved results and the projected ones separately.

Sources used in this answer