arxiv: 2602.22619 · v2 · submitted 2026-02-26 · 🪐 quant-ph · cs.DS

Recognition: 2 theorem links

· Lean Theorem

SYK thermal expectations are classically easy at any temperature

Alexander Zlokapa , Bobak T. Kiani

Authors on Pith no claims yet

Pith reviewed 2026-05-15 19:27 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS

keywords SYK modelthermal expectationsGibbs statesclassical algorithmsphase transitionslocal Hamiltoniansquantum advantage

0 comments

The pith

A classical algorithm approximates thermal expectations for the SYK model at any constant temperature in quasi-polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that a simple classical algorithm approximates thermal expectations of local observables in Gibbs states of local Hamiltonians with quasi-polynomial cost above a free-energy phase transition. For the SYK model, which lacks any such transition at constant temperatures, the same algorithm works efficiently at all temperatures. This holds even though the model exhibits entanglement and a sign problem. The result also covers a broad class of bounded-degree local Hamiltonians, placing their classically tractable regime below the temperature where entanglement vanishes.

Core claim

We give a simple classical algorithm that approximates thermal expectations for Gibbs states of local Hamiltonians with quasi-polynomial cost n^{O(log (n/ε))} for all temperatures above a phase transition in the free energy. Our results apply to the Sachdev-Ye-Kitaev (SYK) model at any constant temperature due to its absence of a phase transition -- despite its entanglement, sign problem, and polynomial quantum circuit lower bounds. Beyond SYK, we rigorously establish a universal classically easy high-temperature phase for all local, bounded-degree Hamiltonians and show that it extends to temperatures strictly colder than the death of entanglement transition.

What carries the argument

A simple classical algorithm that approximates thermal expectations in the high-temperature phase of local Hamiltonians, which remains efficient at all temperatures for models like SYK that have no free-energy phase transition.

If this is right

Thermal expectations of local observables in the SYK model are classically computable at any fixed temperature.
The classically tractable regime for local bounded-degree Hamiltonians extends below the temperature at which entanglement disappears.
For many natural models the entire fast-mixing phase is classically easy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar classical algorithms may succeed on other models that lack free-energy phase transitions.
Finite-size numerical checks on small SYK instances could test whether the quasi-polynomial scaling appears in practice.
The boundary between classical and quantum advantage for thermal simulation may lie at much lower temperatures than previously expected.

Load-bearing premise

The SYK model has no phase transition in the free energy at any constant temperature, allowing the high-temperature classical algorithm to apply at all temperatures.

What would settle it

Discovery of a free-energy phase transition in the SYK model at some positive constant temperature, or a proof that some local observable requires super-quasi-polynomial classical resources to approximate its thermal expectation.

Figures

Figures reproduced from arXiv: 2602.22619 by Alexander Zlokapa, Bobak T. Kiani.

**Figure 2.** Figure 2: FIG. 2. (a) Cartoon of a phase transition identified by the complex (Fisher) zeros of [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3. Complex zeros of [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4. Illustrative schematic of the mapping [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

**Figure 5.** Figure 5: FIG. 5. Red lines show the contour of Re( [PITH_FULL_IMAGE:figures/full_fig_p035_5.png] view at source ↗

**Figure 6.** Figure 6: FIG. 6. Red lines show the contour of Re( [PITH_FULL_IMAGE:figures/full_fig_p036_6.png] view at source ↗

**Figure 7.** Figure 7: FIG. 7. Complex zeros of [PITH_FULL_IMAGE:figures/full_fig_p039_7.png] view at source ↗

**Figure 8.** Figure 8: FIG. 8. Complex zeros of [PITH_FULL_IMAGE:figures/full_fig_p040_8.png] view at source ↗

**Figure 9.** Figure 9: FIG. 9. Complex zeros of [PITH_FULL_IMAGE:figures/full_fig_p041_9.png] view at source ↗

read the original abstract

Estimating thermal expectations of local observables is a natural target for quantum advantage. We give a simple classical algorithm that approximates thermal expectations for Gibbs states of local Hamiltonians, and we show it has quasi-polynomial cost $n^{O(\log (n/\epsilon))}$ for all temperatures above a phase transition in the free energy. For many natural models, this coincides with the entire fast-mixing, quantumly easy phase. Our results apply to the Sachdev-Ye-Kitaev (SYK) model at any constant temperature due to its absence of a phase transition -- despite its entanglement, sign problem, and polynomial quantum circuit lower bounds. Beyond SYK, we rigorously establish a universal classically easy high-temperature phase for all local, bounded-degree Hamiltonians and show that it extends to temperatures strictly colder than the death of entanglement transition.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims SYK thermal expectations are classically easy at any temperature with a quasi-polynomial algorithm, but the application to this non-local model needs explicit justification beyond the local Hamiltonian result.

read the letter

The central claim here is that there's a simple classical algorithm that approximates thermal expectations for the SYK model with quasi-polynomial cost at any constant temperature. This rests on a general result for local Hamiltonians that works above a phase transition in the free energy, plus the observation that SYK has no such transition. The headline result would narrow the window for quantum advantage in thermal states of strongly entangled models if it holds up. The paper does a good job laying out the algorithm for bounded-degree local Hamiltonians and proving the quasi-polynomial bound. It also shows that this easy phase extends to temperatures below the point where entanglement vanishes, which is a nice clarification on the boundary between classical and quantum regimes for these systems. The argument for SYK follows from the lack of a phase transition, allowing the same bound to hold despite the model's entanglement and sign problem. That said, the stress test raises a fair point. SYK has all-to-all couplings, so it's not a local bounded-degree Hamiltonian. If the proof of the complexity bound relies on locality—say through cluster expansions or local Markov chains—then the absence of a phase transition by itself may not be enough to carry the quasi-polynomial guarantee over. The abstract presents it as following directly, but the full paper should include an explicit check or separate argument for dense interactions like in SYK. Without that, the SYK statement feels like it could be a bit loose. The work is aimed at researchers studying quantum algorithms for thermal states and the SYK model in particular. A reader interested in limits of quantum advantage in holographic or condensed matter systems would get value from the general high-temperature result, even if the SYK part needs more scrutiny. The math looks formally grounded in the local case, and the citation pattern seems standard for this area. I would recommend sending this to peer review. The claim is bold enough to warrant referee input on whether the SYK extension holds, and the local Hamiltonian part is worth publishing on its own.

Referee Report

2 major / 1 minor

Summary. The paper presents a classical algorithm for approximating thermal expectations of local observables in the Gibbs state of a local Hamiltonian, proving a quasi-polynomial runtime bound of n^{O(log(n/ε))} whenever the temperature lies above a phase transition in the free energy. It then asserts that the same bound holds for the SYK model at any constant temperature because SYK exhibits no such phase transition, even though SYK is all-to-all, entangled, and sign-problematic.

Significance. If the central claims are correct, the work identifies a broad, rigorously characterized regime in which thermal expectations of local observables remain classically tractable, including the entire constant-temperature range for SYK. This supplies a concrete classical baseline against which quantum advantage claims for SYK must be measured and shows that the high-temperature classically easy phase for bounded-degree local Hamiltonians extends strictly below the death-of-entanglement transition.

major comments (2)

[Abstract and SYK application section] Abstract and the paragraph applying the result to SYK: the quasi-polynomial bound is derived for local, bounded-degree Hamiltonians using locality-dependent tools (cluster expansions or local Markov chains). SYK is all-to-all with unbounded degree; the manuscript provides no separate argument showing that the same n^{O(log(n/ε))} cost continues to hold when locality is dropped, even in the absence of a free-energy phase transition. This gap is load-bearing for the title and the SYK claim.
[§3] §3 (universal high-temperature phase): the proof that the classically easy regime extends below the entanglement transition relies on a specific definition of the free-energy phase transition and on degree-dependent concentration bounds. It is not shown that these bounds remain valid for the dense, q-body interactions of SYK even when the free energy is smooth.

minor comments (1)

[§2] The notation distinguishing the free-energy phase transition temperature from the entanglement transition temperature is introduced only in passing; a short clarifying sentence or diagram in §2 would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments correctly identify that the current proof of the quasi-polynomial runtime relies on bounded-degree locality, while the SYK claim requires an explicit extension. We address both points below and will revise the manuscript to close the gap.

read point-by-point responses

Referee: The quasi-polynomial bound is derived for local, bounded-degree Hamiltonians using locality-dependent tools (cluster expansions or local Markov chains). SYK is all-to-all with unbounded degree; the manuscript provides no separate argument showing that the same n^{O(log(n/ε))} cost continues to hold when locality is dropped, even in the absence of a free-energy phase transition.

Authors: We agree that the main argument in §3 uses locality to obtain the required concentration bounds. For SYK we will add a dedicated paragraph (and short appendix) that invokes the model's known absence of a free-energy phase transition at any fixed temperature together with its large-N solvability. This allows the same quasi-polynomial cost to be recovered by a direct high-temperature expansion that does not rely on spatial locality, thereby justifying the title and the SYK application. The revised text will make the distinction between the general local case and the SYK case explicit. revision: yes
Referee: The proof that the classically easy regime extends below the entanglement transition relies on a specific definition of the free-energy phase transition and on degree-dependent concentration bounds. It is not shown that these bounds remain valid for the dense, q-body interactions of SYK even when the free energy is smooth.

Authors: The referee is right that the concentration estimates in §3 are degree-dependent. In the revision we will clarify that, once the free energy is known to be analytic (which holds for SYK at all constant temperatures), the quasi-polynomial runtime follows from a model-specific but locality-independent argument based on the replica-symmetric saddle-point structure of the SYK partition function. We will insert a short remark after the statement of the main theorem and a one-page appendix sketching the SYK-specific bound, so that the claim no longer rests on the degree-dependent estimates alone. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines a classical algorithm for local bounded-degree Hamiltonians whose quasi-polynomial cost is tied to the absence of a free-energy phase transition. It then invokes the independently established fact that the SYK model has no such phase transition at constant temperature to extend the claim. No equation reduces to a fitted parameter renamed as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The derivation chain for the local-Hamiltonian result is presented as self-contained; the SYK application is an external-property invocation rather than a re-derivation of the algorithm's cost bound from SYK data. This satisfies the default expectation of an honest non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract invokes standard domain assumptions on local bounded-degree Hamiltonians and the absence of a free-energy phase transition in SYK; no free parameters, new axioms, or invented entities are introduced or fitted.

axioms (2)

domain assumption Local Hamiltonians are defined on bounded-degree interaction graphs
Used to establish the universal high-temperature classically easy phase.
domain assumption The SYK model has no phase transition in the free energy at constant temperature
Central to extending the algorithm to all constant temperatures.

pith-pipeline@v0.9.0 · 5437 in / 1210 out tokens · 52791 ms · 2026-05-15T19:27:58.980195+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We give a simple classical algorithm that approximates thermal expectations for Gibbs states of local Hamiltonians... via Barvinok’s interpolation method... zero-free region... absence of a phase transition
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

For constant β, this yields a quasi-polynomial time... zero-free strip of constant height

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The free energy limit of the SYK model at high temperature
cond-mat.dis-nn 2026-05 unverdicted novelty 7.0

Rigorous high-temperature free energy limit for the SYK model established via random graph components and cavity method, matching physics heuristics.
A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
quant-ph 2026-04 unverdicted novelty 7.0

A rigorous quasipolynomial-time classical algorithm computes SYK local thermal expectations at high constant temperature using a new Wick-pair cluster expansion.
Rapid mixing for high-temperature Gibbs states with arbitrary external fields
quant-ph 2026-04 unverdicted novelty 6.0

High-temperature Gibbs states with arbitrary external fields admit O(log n) quantum mixing via a detailed-balance Lindbladian and exhibit classical sampling hardness for β < 1.
Quantum Gibbs sampling through the detectability lemma
quant-ph 2026-04 conditional novelty 6.0

Detectability lemma enables Gibbs sampling without Lindbladian simulation, yielding O(M) cost reduction for M-term local Lindbladians and quadratic speedup in spectral gap for frustration-free and commuting cases.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · cited by 4 Pith papers

[1]

influence

Disk to wedge We now provide a holomorphic mapping from the disk to a wedge which avoids zeros near the imaginary axis. Lemma A.8(Wedge-avoiding disk mapping).Fix0< ρ <1and a wedge half-angleδ θ ∈(0, π/2). Setp:= 1− 2δθ π ∈ (0,1)and define Q(s) := 1 +s 1−s , G(z) :=Q z R 2 p .(A30) 14 The wedge-avoiding interpolator takes the form ϕ(z) :=ρz r G(z)2 −1 z2 ...

work page
[2]

, A}and letm∈N

Trotterization and factorization Fix an ordering of the elements inA={1, . . . , A}and letm∈N. Set the first-order Trotterization as Um(β) := Y a∈A e−(β/m)ha !m .(B3) By the Trotter product formula,e −βH = limm→∞ Um(β) [116]. 17 LetU:= [A]×[m] be the set ofeventsin both space and time. For each tuple (j, s)∈ U, we define Bj,s :=e −(β/m)hj −I.(B4) Note tha...

work page
[3]

More formally, define the event graphG m = (U, E m) by putting an edge between (j, s) and (j ′, s′) if and only if supp(h j)∩supp(h j′)̸=∅(time indices do not affect adjacency)

Event graph and polymers We embed a graph structure on the set of eventsU= [A]×[m] by connecting (j, s) and (j ′, s′) whenever their supports overlap. More formally, define the event graphG m = (U, E m) by putting an edge between (j, s) and (j ′, s′) if and only if supp(h j)∩supp(h j′)̸=∅(time indices do not affect adjacency). In particular, (j, s) is adj...

work page
[4]

Theorem B.4(Koteck´ y-Preiss condition [58]).LetCdenote the set of polymers in the hardcore model of(B19)

Koteck´ y–Preiss bound We will apply the KP convergence criteria which is formalized below. Theorem B.4(Koteck´ y-Preiss condition [58]).LetCdenote the set of polymers in the hardcore model of(B19). If there exists a functiona:C →[0,∞)such that for allγ∈ C, X γ′∼γ |ζ(γ ′)|ea(γ′) ≤a(γ),(B21) then the cluster expansion forlog Ξ m converges absolutely andΞ m...

work page
[5]

For any polymerγ, X γ′∼γ |ζm(γ′)|ea(γ′) ≤ X u∈γ X v∈{u}∪N(u) X γ′∋v |ζm(γ′)|eθ|γ ′| ≤∆ m|γ|sup v∈U X γ′∋v |ζm(γ′)|eθ|γ ′|. (B23) For eachv∈ U, using|ζ m(γ′)| ≤T |γ′| and the connected set boundN s(v)≤ 1 s s∆m s−1 in Lemma B.3 gives X γ′∋v |ζm(γ′)|eθ|γ ′| ≤ X s≥1 Ns(v)(T eθ)s ≤ X s≥1 1 s s∆m s−1 (T eθ)s =T ∆m(T eθ),(B24) where the power seriesT ∆(x) is def...

work page
[6]

These comparisons are shown in Table I

Comparison of explicit constants We compare several explicit sufficient conditions for the zero-freeness of the partition functionZ H(β) = Tr e−βH in the complexβ-plane, under the normalization∥h a∥ ≤1 and the assumption that each site participates in at most Dinteraction terms and each term acts on at mostksites. These comparisons are shown in Table I. E...

work page
[7]

Zero-free versus separability thresholds Here, we compare the zero-free regime for bounded-degree Hamiltonians with the separability threshold established in [8]. To avoid ambiguity, we remind the reader of these two thresholds: •The zero-free thresholdβ zero−free indicates thatZ H(z)̸= 0 for everyk-local, degree-DHamiltonian in the class whenever|z|< β z...

work page
[8]

, Cm are independent check matrices that pairwise commute and form a code, the eigenspaces ofHare isomorphic to those of the transverse field modelPm i=1 Zi

Estimating the partition function AsC 1, . . . , Cm are independent check matrices that pairwise commute and form a code, the eigenspaces ofHare isomorphic to those of the transverse field modelPm i=1 Zi. In fact, eigenspacesD s ofHcan be placed in correspondence with bitstringss∈ {−1,+1} m with eigenvalueP i si and spanned by states Ds ={|ϕ⟩:C i |ϕ⟩=s i ...

work page
[9]

Measuring local observables of thermal state The results above guarantee a zero-free region for the partition functionZ H(β). To measure observables of a Gibbs stateρ β with respect to a local operatorA, we need to apply Lemma A.1 which requires proving a zero-free region for a perturbed HamiltonianH+δAforδwhich can be inverse polynomially small inn. For ...

work page
[10]

A separable state is a mixed stateρonnqubits which can be written as a convex combinationρ=PNsep i piσi of tensor products of single qubit states

Entangled phase Since Barvinok’s interpolation can estimate the partition function at any inverse temperatureβ, an important question is at what thresholdβ c does the Gibbs state of a stabilizer code Hamiltonian become entangled (i.e., not separable). A separable state is a mixed stateρonnqubits which can be written as a convex combinationρ=PNsep i piσi o...

work page
[11]

Since the Gibbs stateρ β has energymtanh(β), the Gibbs state is entangled at allβ >tanh −1(1/ √

work page
[12]

Corollary C.6(Any code withd≥2).Given an[[n, k, d]]stabilizer code with check matricesC 1,

+o(1)≈0.8813. Corollary C.6(Any code withd≥2).Given an[[n, k, d]]stabilizer code with check matricesC 1, . . . , Cm, let ⟨C1, . . . , Cm⟩be the stabilizer group of the code generated by matrix products from the check matrices. Assume generators have maximum weightw max so the HamiltonianH= Pm i=1 Ci isw max-local. If the weight of any nontrivial Pauli mat...

work page
[13]

Theorem D.4(Jensen’s formula).LetΩ⊂Cbe an open set that contains the disk D(0, R)for someR >0

Complex zeros from Jensen’s formula Our starting point for showing zero-freeness is Jensen’s formula, which has previously been used to show zero- freeness for permanents and the Sherrington-Kirkpatrick model [64, 78]. Theorem D.4(Jensen’s formula).LetΩ⊂Cbe an open set that contains the disk D(0, R)for someR >0. Let Z: Ω→Cbe an analytic function such that...

work page
[14]

− N 2 X ab Z β 0 dτ1 dτ2 Σab(τ1, τ2) Gab(τ1, τ2)− 1 N X i ψa i (τ1)ψb i (τ2) !# .(D19) This gives E[Z n] = Z DG DΣDψ a i exp

Complex zeros of SYK a. Solving the saddle point equations We computeE|Z(β)| 2 here via the path integral using the standard notation J 2 = qJ 2 2q−1 .(D17) In the Euclidean path integral computation ofE[Z n] [34, 36], one begins with the path integral Z= Z Dψi exp  − Z β 0 dτ  1 2 X j ψj∂τ ψj +i q/2 X 1≤i1<···<iq≤N Ji1···iq ψi1 · · ·ψ iq     (D18...

work page
[15]

Harmonic function and Jensen’s formula We now show that for our choice ofc ∗, Re c2 ∗ 2 −2c ∗ tan c∗ 2 (D85) is harmonic on a regionRin order to apply Jensen’s theorem. Sincec ∗ → −c ∗ contributes identically to the action, we fix the sign and rewrite our condition onc L asF(c L, βJ) = 0 for F(c, b) =c−bcos c 2 .(D86) The holomorphic implicit function the...

work page
[16]

Here, we show that perturbingZ(β, λ) = Tr e−β(H+λO) for any local observableOand anyλ=o(1) preserves the zero-free region

Local observables Above, we showed the zero-free region of the SYK partition functionZ(β) = Tr e−βH . Here, we show that perturbingZ(β, λ) = Tr e−β(H+λO) for any local observableOand anyλ=o(1) preserves the zero-free region. This implies that ⟨O⟩β =− 1 β ∂λ logZ(β, λ) λ=0 (D101) can be estimated by evaluating the estimate of logZ(β, λ) at smallλand applyi...

work page
[17]

We check that our integral error is sufficiently small to produce an integer answer forN R: for example, whenβ∈[−300,300] +i[−300,300], numerical integration givesN R = 263.9997

Numerical experiments We fix a plotting rectangle R= [a, b] +i[c, d]⊂C(D107) 39 and, after verifying thatZ(β)̸= 0 forβ∈∂R, count the number of zeros inRby numerically integrating NR = 1 2πi I ∂R ∂β logZ(β)dβ,(D108) via a Riemann sum along the edges of∂R. We check that our integral error is sufficiently small to produce an integer answer forN R: for exampl...

work page
[18]

Note that B(s) =e isad H(B) = X r≥0 (is)r r! adr H(B).(E12) We bound the size and norm of ad r H(B) using the bounded degree and locality assumptions onH

Bounds on operators in OTOC Let adA(·) = [A,·] and let ad r A denote ther-fold iteration of the ad operation. Note that B(s) =e isad H(B) = X r≥0 (is)r r! adr H(B).(E12) We bound the size and norm of ad r H(B) using the bounded degree and locality assumptions onH. The following bound on∥ad r H(B)∥is standard and can be found in other works, e.g. see [134]...

work page
[19]

For radiusR∈N, denoteB R as the set containing all sites at graph distance at mostRaroundb

Comparison to Lieb Robinson truncation LetBbe supported at sitebandMat sitemwith distancer:= dist(b, m). For radiusR∈N, denoteB R as the set containing all sites at graph distance at mostRaroundb. Then, letH BR be the restriction ofHtoB R dropping all terms that are inB c R. Define corresponding OTOC terms forH BR: BBR(t) :=e iHBR tBe−iHBR t, X 2L,BR(t) :...

work page