PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial-time classical algorithms for mean-field models up to the glass transition

Alexander Schmidhuber, Alexander Zlokapa

arXiv:2610.06807v1quant-phcond-mat.dis-nncs.DSmath-phmath.MP

TL;DR

Estimating local thermal expectations in SYK had been shown to be possible in quasipolynomial time only at sufficiently high temperatures, while polynomial-time algorithms at constant temperatures remained unresolved. This paper develops a rigorous quantum cavity method and uses it for polynomial-time thermal-expectation algorithms and Gibbs-state Hamiltonian learning. The approach also yields classical Ising p-spin thermal expectations up to the static transition.

  • Problem

    Earlier rigorous SYK algorithms estimated local thermal expectations in quasipolynomial time at sufficiently high temperatures, leaving polynomial time at constant temperatures unresolved.

    Source: §1 · pp. 3–4

  • Method

    A rigorous quantum cavity method controls concentration around the disorder-averaged solution, enabling an expansion around the saddle point at the target temperature.

    Source: §1 · p. 4

  • Results

    Polynomial-time classical algorithms estimate SYK thermal expectations at arbitrary constant temperatures and Ising p-spin thermal expectations up to β*.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The quantum cavity method supports polynomial-time thermal-expectation algorithms and Gibbs-state learning from SYK Gibbs states at constant temperature.

    Source: §1 · pp. 4–5

    It remains open whether the related real-time technique extends to times that grow with system size.

    Source: §1.2 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The paper develops a rigorous quantum cavity method to obtain polynomial-time algorithms for thermal expectations in SYK at constant temperatures and in classical Ising p-spin models up to the static transition. It also applies the method to Gibbs-state Hamiltonian learning and discusses further directions for mean-field models.

1 Introduction

  • Prior rigorous SYK thermal-expectation algorithms achieved quasipolynomial time at sufficiently high temperatures, leaving polynomial time at constant temperatures unresolved.For Ising p-spin, efficient estimation all the way to the static transition also remained open.Source: §1 · pp. 3–4
  • Polynomial-time classical algorithms estimate SYK thermal expectations at arbitrary constant temperatures and Ising p-spin expectations up to the static transition β*.For fixed observable degree, the Ising p-spin theorem also estimates the log partition function with inverse-polynomial error.Source: §1 · p. 4

1.1 Technical contributions

  • The quantum cavity method controls concentration of typical SYK instances around the large-N saddle point while retaining instance-to-instance fluctuations.It expands around the disorder-averaged solution at β itself, rather than around infinite temperature.Source: §1 · p. 4, §1.1 · p. 5
  • After cavity-based concentration is established, thermal-expectation algorithms expand around the saddle point by inverting its Hessian; for SYK this resums ladder diagrams.For Ising p-spin, p=2 requires resummation, while p≥3 has a trivial Hessian and a simpler algorithm; both require cavity-based concentration.Source: §1.1 · p. 8
  • A polynomial-time algorithm learns SYK Hamiltonians from Gibbs-state copies at constant temperature by measuring terms and correcting their leading 1/N mean-field contribution.The cavity method bounds the higher-order remainder.Source: §1 · p. 5, §1.1 · p. 8

1.2 Discussion

  • The authors focus on mean-field models beyond locality-based methods and identify growing-time real-time dynamics as an open direction for the quantum cavity method.It remains open whether the related technique extends to times that grow with system size.Source: §1.2 · pp. 8–9

2 SYK Preliminaries

The preliminaries define the fermionic expectation framework and the SYK saddle around which the algorithm expands. They introduce the ladder kernel used to make that expansion.

2 SYK Preliminaries

  • The notation sets the normalized trace and Gibbs state, and names canonically ordered Majorana strings ΓA.Source: §2 · p. 10

2.1 Free fermions

  • Free-fermion expectations are defined by Wick’s rule, with SYK expectations represented through ratios of free-fermion expectations.The Grassmann variables are antiperiodic around the thermal circle.Source: §2.1 · pp. 10–12

2.2 SYK saddle point equations

  • The algorithm expands around the time-translation-invariant saddle solution G*, which the paper computes through a convex optimization problem.Source: §2.2 · pp. 12–13

2.3 SYK ladder kernel

  • Perturbing the saddle defines the ladder kernel K; the expansion requires inverting Lβ = I − K, and each ladder diagram contributes 1/N independently of rung count.Source: §2.3 · p. 14

3 Quantum cavity method

The quantum cavity method uses concentration of an empirical two-point field around the SYK saddle to justify expansion. It adapts cavity reasoning with weak measurements, spectral rounding, and detailed-balance control.

3 Quantum cavity method

  • Concentration of the empirical two-point field around G* is the proof’s main technical step and justifies expansion around the saddle.Source: §3 · p. 14
  • The cavity construction adds a fermion with fresh disorder, then approximates its contribution by coupling it to a free-fermion bath.This iterative reduction is intended to decompose correlators into two-point functions.Source: §3 · p. 15
  • Unlike classical conditioning, conditioning on a quantum energy eigenstate need not concentrate the observables; weak measurements instead provide conditional concentration while controlling disturbance.Source: §3 · p. 17
  • Random-offset spectral rounding makes the Gibbs state blockwise compatible with measurements, and a projector restores detailed balance for the transitions used in the cavity step.Source: §3 · pp. 17–18
  • After G concentrates around G*, the method performs the expansion by inverting Lβ constructed from the ladder kernel.Source: §3 · p. 18

4 Estimating thermal expectations of the SYK model

The section estimates SYK thermal expectations by expanding around a saddle point and recursively estimating moments with an invertible ladder kernel. For fixed parameters, the resulting algorithm achieves inverse-power error and failure bounds with a number of operations linear in N.

4 Estimating thermal expectations of the SYK model

  • The method expands the observable around the saddle point G* and estimates its coefficients through correlators of inserted Majorana operators.The coefficients are estimated using ratios of Majorana-inserted terms.Source: §4 · pp. 18–19
  • The moment recursion uses the inverse ladder kernel Lβ, which is invertible for every constant β ≥ 0.The recursion is solved starting from μ0 = 1.Source: §4 · pp. 19–20
  • Concentration of μp improves with moment order, permitting truncation of the recursion at a chosen order K.At fixed K, the recursion remainder is bounded by O(N^-θK).Source: §4 · pp. 20–21

4.1 Correctness and cost

  • The correctness proof controls coefficient, recursion-truncation, and saddle-estimation errors using Hermite orthogonality and numerical-stability bounds.The saddle estimate is obtained by convex optimization; the proof also bounds the error from recursion truncation.Source: §4.1 · pp. 22–24
  • N^-c error tolerance is violated with probability at most N^-a, and the algorithm uses at most NCβ,a,c,w operations for fixed parameters.The theorem fixes β, a, c, and an even weight w.Source: §4.1 · pp. 21–23

5 Concentration at the saddle point

This section develops tools to control the posterior mean and complete the main moment-bound proof, combining spectral and measurement arguments with extensions of the cavity approximation and concentration estimates.

5.1 Spectral rounding

  • For every shift u, spectral rounding changes βH by at most δE, while averaging the rounded Gibbs states gives (e^δE−1)e^βH exactly.The moment approximation uses δE=N^−ε, with 0<2ε<c; its error bounds decay with the odd moment m.Source: §5.1 · p. 25

5.2 Measurements and the posterior mean

  • After measurements in a randomly chosen forward or reverse order, forgetting the outcomes exactly preserves ρ(u) and yields concentration inequalities analogous to those for spectral rounding.The posterior state conditioned on the outcomes is ρx.Source: §5.2 · p. 26

5.3 Conditional detailed balance

  • Conditioning can spoil detailed balance, but a weighted detailed-balance bound controls the deviation for each fixed odd m≥1 and integer q≥1.The conditional transition law’s symmetrized measure preserves the distribution of |ω| and satisfies detailed balance.Source: §5.3 · p. 27
  • A fixed integer r≥1, independent of m, suffices for the posterior-mean recovery bound, with the Hamiltonian-rounding contribution bounded by 2|t|δE.The rounding contribution follows from the bound on the difference between real-time evolutions under H and the rounded Hamiltonian.Source: §5.3 · pp. 29–30

5.4 Adding a noninteracting cavity fermion

  • For disjoint Majorana strings, imaginary-time correlators can be rewritten in terms of G functions up to small error under the stated time and parameter conditions.The construction adds a fermion ψN+1 decoupled from H and restricts its couplings to mutually disjoint sets Te, with each site appearing exactly twice.Source: §5.4 · pp. 30–31
  • For positive simplex targets h, analytic continuation bounds |cA,π(h) − ℓA,π(h)| by e^{λ(s−1)}|f(h)|.The passage specifies targets with hj>0 and sum_j hj=1.Source: §5.4 · p. 34

5.5 Adding the cavity interaction

  • Lemma 17 constructs a quadratic free-fermion bath whose two-point function realizes the cubic self-energy Gσ(t)=β²G(t)³.The construction chooses nonnegative couplings xj and vj.Source: §5.5 · p. 35
  • For each fixed odd m, Lemma 18 gives a concentration estimate for the posterior mean a=Tr(ρxB) and kernel G with b>0 independent of m.Theorem 80 replaces cA,π by ℓA,π after bounding errors from truncation and restricting the set of Te; Theorem 78 replaces B by B+ with the same form of error.Source: §5.5 · p. 37

5.6 Completing the proof

  • Theorem 4’s proof establishes a main moment bound with δ>0 and integer r≥1 independent of the moment index for each fixed odd m, then extends the result to arbitrary j.The extension chooses the next odd m at least j.Source: §5.6 · pp. 38–39

6 Learning the SYK Hamiltonian

The section develops an algorithm to learn SYK couplings from Gibbs-state copies, using the expansion underlying the thermal-expectation algorithm. For every fixed positive temperature, the theorem gives polynomial quantum and classical resources and permits vanishing inverse-polynomial normalized Hilbert-Schmidt error.

6 Learning the SYK Hamiltonian

  • For every fixed β > 0, learning from SYK Gibbs-state copies uses polynomial resources and can achieve vanishing inverse-polynomial normalized Hilbert-Schmidt error.The theorem specifies polynomially many quantum gates and classical operations, with success guarantees over couplings, classical randomness, and measurement outcomes.Source: §6 · pp. 39–40

6.1 Preliminaries

  • The learning algorithm expands around SYK coefficients, with first- and second-order terms involving αβJA and bβQA(J).The section states that the expansion used for thermal expectations is the basis for recovering Hamiltonian couplings from Gibbs-state copies.Source: §6 · p. 39, §6.1 · p. 40

6.2 Hermite truncation

  • Truncating the Hermite expansion controls the approximation error, while its higher-order components decay with N and the coefficients are efficiently computable.For fixed degree d, the supplied bound gives ∥gI,d∥L2(J) ≤ Cβ,dN^−d/2; the coefficients aβ and bβ can be computed in time polynomial in τ^−1.Source: §6.2 · pp. 42, 44

6.3 Learning from quartic expectations

  • The algorithm recovers couplings from estimated quartic Gibbs expectations, and the coupling-recovery computation can be approximated in time polynomial in N and ε^−1.The recovery result assumes sufficiently large N and ∥T(J)∥ ≤ 16N.Source: §6.3 · pp. 45–46

6.4 Measuring all quartic expectations

  • Random perfect matchings let the algorithm estimate quartic expectations by jointly measuring disjoint Majorana pairs.In the Jordan–Wigner representation, measuring N/2 commuting pairs costs O(N^2) gates per copy.Source: §6.4 · pp. 47–48

6.5 Correctness and cost of learning

  • The final correctness and cost analysis combines quartic-expectation estimation with coupling recovery to establish polynomial learning complexity.The section attributes the overall complexity to the measurement and recovery procedures.Source: §6.5 · pp. 48–49

7 Estimating thermal expectations of Ising spin glasses

This section develops a deterministic polynomial-time classical method for estimating local thermal expectations and the partition function of Ising mixtures with interactions of order at least three, below the static transition. It establishes correctness and cost bounds, including uniform expected-error control across a temperature interval and an explicit count of the Hermite indices used.

7 Estimating thermal expectations of Ising spin glasses

  • The algorithm uses a finite Hermite expansion and concentration to truncate a classical cavity recursion, avoiding the inverse-operator step used for the SYK recursion.For interactions of order at least three, the Hessian is the identity, so the algorithm can omit the L^-1 step.Source: §7 · p. 49

7.1 Models and main result

  • For fixed mixtures, β < β*, and bounded observable degree, a deterministic classical algorithm estimates local thermal expectations and the partition function in polynomial time.Exponentiating its estimate bL approximates ZN within a factor e±N^-c; the operation count is at most N^C for fixed parameters.Source: §7.1 · p. 50

7.2 Concentration of replica observables

  • Below the static transition β*, overlap concentration and active-site-order bounds control replica observables, while monomials with any odd replica subset vanish exactly.The overlap concentration applies throughout the zero-overlap replica-symmetric phase; the active-site bounds make a fixed Hermite cutoff sufficient.Source: §7.2 · pp. 50–51

7.3 The cavity recursion at the target temperature

  • The cavity recursion expands around a decoupled active spin and terminates with fixed active-site and collision cutoffs: collision-free terms grow active-site order, while collision terms have total weight O(N^-1).Increasing the replica count alone does not provide a 1/N factor; in two-spin models a collision-free term can preserve active-site order, requiring a separate SK resummation.Source: §7.3 · pp. 51, 53, 54

7.4 Reconstructing the thermal expectations

  • Thermal expectations are reconstructed from a finite Hermite expansion whose coefficients are expressed through replica expectations, with a bounded tail and uniform coefficient control for bounded-size observables.At fixed Hermite cutoff, the initial replica monomials have bounded active-site count and replica count.Source: §7.4 · pp. 54–55

7.5 Correctness, counting, and cost

  • The chosen cutoffs are independent of N, and the resulting polynomials predict interaction monomials accurately enough to establish the theorem’s observable guarantee.Summing the error over the O(N^ℓ) targets gives an observable failure probability smaller than any required constant multiple of N^-a for sufficiently large N.Source: §7.5 · pp. 55–56
  • Uniform expected-error control along the temperature interval suffices; the analysis does not require one good event to hold for every real temperature.The stated failure-probability bound is in addition to Pr(Gc).Source: §7.5 · p. 56
  • The cost accounting uses O(NPD) Hermite indices, at most L−1 incident interactions per cavity row, and at most T = (R+1)(S+1) rows per path.These counts enter a conservative arithmetic bound for all degree-at-most-ℓ0 targets and counting.Source: §7.5 · p. 56
  • At β = 0, the algorithm returns the exact uniform-spin expectations and N log 2.For computed observables, clipping to [−1, 1] cannot increase error to a spin expectation.Source: §7.5 · p. 56

8 Estimating thermal expectations of the SK model

The SK algorithm succeeds at every fixed β < 1, using a graph expansion that retains leading chain and cycle contributions. Its graph sums can be computed in polynomial time, and the paper reports close agreement with exact collective-correlation values at β = 0.95.

8 Estimating thermal expectations of the SK model

  • For every fixed β < 1, a deterministic classical algorithm estimates SK thermal expectations and the log partition function with polynomial bit complexity.The success range is below the static transition β∗ = 1.Source: §8 · p. 57
  • 2.27% relative RMS error at β = 0.95 compares 17-edge-cutoff predictions with exact collective corrections.The 95% confidence interval is 1.43–3.26%.Source: §8 · p. 58

8.1 An exact one-site cavity identity

  • An exact one-site cavity identity yields a graph expansion, but its naive recursion is exponential, so the algorithm computes a controlled truncation instead.Independence and centering make distinct graph weights orthogonal, preserving cancellations between signed terms.Source: §8.1 · p. 59

8.2 Summing chains and cycles before truncation

  • Because chains of increasing length contribute at the same leading order, the expansion retains O(log N) edges and only a fixed amount of excess.At zero excess, graphs decompose into vertex-disjoint paths pairing marked vertices and simple cycles.Source: §8.2 · pp. 59–60

8.3 Computing the retained graph sum

  • Color-subset recurrences compute retained graph sums without enumerating every assignment of physical vertices along the chains and cycles.The deterministic color-family construction is polynomial when s = O(log N) and m = N^O(1).Source: §8.2 · p. 60, §8.3 · pp. 61–62

8.4 Correctness, counting, and cost

  • The correctness and cost analysis combines orthogonal truncation errors with polynomial-cost graph evaluation to establish polynomial bit complexity.The construction uses k = Oβ(log(N + 2)) and sums over polynomially many boundaries and support sizes.Source: §8 · p. 57, §8.4 · pp. 62–63

A Fourier truncation error of the saddle solution

This section addresses numerical approximation of the saddle solution and its Fourier truncation. It gives polynomial-time procedures for finding coordinates with small saddle residual and for stable numerical inversion under stated regularity conditions.

A Fourier truncation error of the saddle solution

  • Coordinates with saddle residual at most M^-2 can be computed in time polynomial in M.The coordinates are restricted to an explicit box for the objective FM.Source: A Fourier truncation error of the… · p. 70
  • Stable numerical inversion uses an approximate input with gradient norm at most M^-2 and a certified finite inverse.The construction replaces the exact kernel with a finite approximation at mesh width at most M^-4.Source: A Fourier truncation error of the… · p. 72
  • For fixed dimension, mesh width M^-4 gives polynomial cost when the input functions have polynomial-cost evaluation and extend continuously to their domains' closures.The continuity condition is stated for each XF.Source: A Fourier truncation error of the… · p. 72

B Hermite truncation error

The appendix bounds Hermite truncation error by controlling degree contributions and establishing partition-function concentration; summing the contributions proves (4.4).

B Hermite truncation error

C Recursion truncation error

The recursion truncation analysis controls omitted moments and numerical errors, proving (4.20) with computation cost M_CK,j for fixed K and j.

C Recursion truncation error

D SYK saddle point equations

This section establishes existence, uniqueness, and regularity properties of the SYK saddle and develops exact commutator expansions with structural, Gaussian-moment, and source-moment bounds. It uses these tools to control physical observables and ordered products of empirical observables, including source-moment bounds transported through positive-heat factors.

D SYK saddle point equations

  • For every β ≥ 0, the saddle equations have a unique normalized positive spectral solution, with a bounded holomorphic extension on [0, 1] over compact temperature intervals.At β = 0, the representing measure is δ0; the proof also establishes existence and weak continuity of the output.Source: D SYK saddle point equations · pp. 78, 80
  • For every normalized positive spectral kernel G, the source β²G³ belongs to the specified source class, without requiring moment assumptions on G’s representing measure.Source: D SYK saddle point equations · p. 79

E Coincident times and orthogonal reconstruction

  • At coincident times, the Grassmann-product value is independently antisymmetrized within each equal-time group, equivalently obtained by averaging over independent continuous offsets.An ordered coincident-time product is a distinct prescription: fixed offsets preserve their chosen order in the limit.Source: E Coincident times and orthogonal… · p. 85
  • For N ≥ k, the exact orthogonal reconstruction identity for polynomials in collective variables applies to distinct times and both alternating and ordered coincident-time limits.Source: E Coincident times and orthogonal… · p. 87

F Physical commutators and source moments

F.1 Exact commutator expansions

  • For deterministic piecewise continuous profiles mE, the exact commutator expansions use the stated propagators.Source: §F.1 · p. 88
  • Exact two-site and rooted-tree product expansions provide formulas for commutators and nested commutators.The proof uses Clifford relations and Duhamel’s formula; iteration terminates under the stated support condition.Source: §F.1 · pp. 89–90

The data satisfy

  • The expansion hypotheses allow bounded piecewise-continuous profiles independent of J and a special finite-product leaf W; the resulting constant is independent of s.The special leaf has the form W = eil0βHP1eil1βH · · · PseilsβH, with Pν = ΓAν and |Aν| ≤ p.Source: The data satisfy · pp. 91, 95

F.2 Gaussian integration and moment bounds

  • Duhamel differentiation and Schatten Hölder establish Gaussian derivative bounds for matrix products, including products containing propagator factors.The identities apply to the full matrix product, including every factor Umν(tν, sν).Source: §F.2 · pp. 96–97
  • For the connected incidence graph in quartet-label counting, rank D = b + f and dim ker D = 3b − f.The connectedness hypothesis yields the stated incidence-matrix rank and kernel dimension.Source: §F.2 · p. 98
  • The Gaussian-expectation summation lemma has constants independent of N, s, F, T, and qλ.The lemma’s hypotheses require measurable parameters and coefficient functions independent of J at fixed e, i, u.Source: §F.2 · pp. 99–100
  • High-moment estimates hold for nested physical commutators and their adjoints, with constants independent of N, s, and T.The constants may depend on β, the fixed degree and other fixed parameters; the estimates also extend to words with static factors.Source: §F.2 · pp. 101–102

F.3 Curvature and commutators of powers

  • Physical source estimates bound commutators of powers using moments of B, with fixed-duration local factors affecting only prefactors.The section also bounds products with nonzero total real time by the source term ΦN([F, [−βH, F]]) times C(|t| + t^2).Source: §F.3 · pp. 103, 105

F.4 Ordered products of empirical observables

  • Ordered moment inequalities control words of length 2m in empirical observables, with time dependence confined to an additive constant.For times in [−T, T], that constant is at most C(1 + T)^C e^{C(1+T)^2}; ordering errors are handled by adjacent exchanges.Source: §F.4 · pp. 106–108

F.5 Transport through positive-heat factors

  • Source-moment bounds extend to positive-half-heat words, with constants independent of the number of factors, site labels, and individual times.The result also holds with the source on the right and with a fixed number of fixed-duration real-time local factors.Source: §F.5 · pp. 108–109

F.6 Physical estimates after energy pinching

This section develops physical estimates after energy pinching, including exact reordering and analytic continuation bounds for chronological collective moments. It also establishes a uniform supremum estimate across endpoint cases, proves the ladder operator has an inverse at every finite temperature, and outlines estimates used to prove Theorem 6.

F.6 Physical estimates after energy pinching

  • The section gives post-pinching bounds for powers and mixed products, including physical ordering errors and source-dependent measurement bounds for empirical contractions.The source B remains at fixed times while the empirical contractions have times in [−T, T].Source: §F.6 · pp. 110–112

G Concentration of the chronological collective moments

  • The chronological-moment argument exactly reorders fermionic products while retaining repeated site labels, then continues the resulting scalar bounds to imaginary time.The reordering keeps the scalar centers and produces a finite expansion with constants uniform over the displayed times and permutations.Source: G Concentration of the chronological… · p. 113, §G.1 · pp. 114–115

G.1 Reordering while retaining the scalar centers

  • The reordering expansion is finite for each fixed order, and its constants are uniform over bounded times and permutations.The site sums include repeated numerical values, and the times need not be distinct.Source: §G.1 · pp. 114–115

G.2 An analytic neighborhood independent of the number of pairs

Then the function

  • In the continuation bound, every nonzero coefficient has all quartet-intersection components meeting the selected sites S, with cancellation occurring before absolute values.The proof uses the common sign of components disjoint from S across the conjugated Hamiltonians.Source: Then the function · p. 117
  • A fixed-width neighborhood of [0, 1] supports the analytic continuation, with constants independent of the number of factors.The rectangle and initial disk cover dist(s, [0, 1]) < ηβ.Source: Then the function · p. 118
  • The supremum estimate holds uniformly at equality and endpoint time values; ordered limits and finite averages preserve the bound, and the result includes β = 0.Reversing the initially reoriented pairs changes only signs.Source: Then the function · p. 119

H Operator, covariance, and numerical estimates

H.1 Excluding a singularity of the ladder operator

  • The ladder operator has no singularity at any finite temperature, so its L2 inverse exists, is locally bounded, and yields effective estimate (4.11), including coincident-time values.The proof excludes a first singular temperature on an arbitrary compact interval. Evidence: s55.p15#5d54c7, s55.p16#557c7c.Source: §H.1 · p. 121

H.2 The operator and the covariance

The section characterizes the collective-moment operator and covariance at regular and singular temperatures. It also establishes bounded short-time tests and shows that critical vectors are determined by their behavior on any open relative-time interval.

H.2 The operator and the covariance

  • Equation (4.9) is an exact collective-moment equation whose order-one terms use μp+1, μp+2, μp+3 and whose explicit N^-1 terms use μp−1, μp−2.The equation uses the coincident-time prescriptions of Theorem 42.Source: §H.2 · p. 122
  • At a regular temperature, μ1 = Oβ(N^-1) and N(μ2 − μ1μ1) = Cβ + Oβ(N^-1), with Cβ = 2Lβ^-1.The covariance statement is made at each fixed regular temperature.Source: §H.2 · p. 123
  • At a first singular temperature β*, a subsequence yields a positive nonzero limiting operator with range in ker Lβ*; only finitely many center sectors can be singular on a compact temperature interval.The limiting operator is supported on the stated finite set of nonzero sectors.Source: §H.2 · pp. 121, 124

H.3 A physical bound on short-time tests

  • The short-relative-time physical covariance test is continuous in operator norm and locally uniformly bounded over regular real temperatures.The physical bound is uniform on compact temperature intervals, while the large-N limit is taken at each fixed regular temperature.Source: §H.3 · pp. 127–128

H.4 Analyticity of critical vectors

  • In each fixed center sector, critical vectors are analytic in relative time, so vanishing on any nonempty open subinterval forces the vector to vanish identically.Restriction to such an interval is injective on the nullspace.Source: §H.4 · pp. 128, 130

H.5 Certification and numerical stability

The section makes the scalar kernel and the fixed truncated hierarchy effectively computable with certified inverse bounds. Its approximation and error-control steps yield polynomial-time accuracy in the requested precision.

H.5 Certification and numerical stability

  • The scalar kernel admits uniform one-sided error ε in time polynomial in ε^-1, and a finite refinement search certifies an inverse-norm bound once invertibility is proved.The certification uses rational interval arithmetic and refinement terminates when the true inverse exists.Source: §H.5 · p. 130
  • With the inverse certificate, inverse operations and coincident-time evaluations for any fixed truncated hierarchy can be computed to accuracy ε in time polynomial in ε^-1.The bounds on intermediate expressions are independent of N.Source: §H.5 · pp. 130, 132
  • The computed hierarchy has error Oβ,K,j(M^-2), with polynomially many stored values and quadrature regions in fixed dimension.Choosing M proportional to ε^-1/2 gives polynomial bit cost in ε^-1.Source: §H.5 · p. 133

I.1 Scalar inequalities and energy pinching

This section develops pinching, variance, and approximation bounds alongside cavity-comparison estimates, covering evolved Majoranas, coefficient control, spectral-kernel recovery, and classical cavity estimates for normalized expectations.

I.1 Scalar inequalities and energy pinching

  • For every integer p ≥ 1, pinching controls the pth-power error under the stated scales, extending the odd-power bounds to even powers.The odd-power estimates use the stronger exponent 2c0; the proof of the all-powers result handles even p using those estimates and moment interpolation.Source: §I.1 · pp. 134–135

I.2 Integrated Gaussian identities

  • The integrated Gaussian identities yield harmonic-norm bounds, while the sequential instrument gives posterior-source and conditional-variance estimates in both measurement orders.The harmonic estimate applies to a Hermitian unitary and block-diagonal operators; the sequential estimates use a source measured first in the forward order.Source: §I.2 · pp. 135–136

I.3 Products and continuous real times

  • For bounded real times and fixed or logarithmically growing product length, conditional product approximation uses a shared polylogarithmic-size grid for all factors.The result also covers reversed factors using G(−it) = G(1 + it).Source: §I.3 · p. 138

J Changing the cavity source and bounding the omitted terms

  • The estimates for changing the cavity source use a common ambient even Clifford algebra and normalize empirical sources by 1/N, including after adding the cavity Majorana.These conventions apply to the Hamiltonians and source specified in (5.76)–(5.92).Source: J Changing the cavity source and… · p. 140

J.1 Moving and pinching the source

  • Moving and pinching the source gives an exponentially small error bound for each fixed odd power, with a1 independent of that power.The bound applies to the specified static factors and includes the source-moving and pinching errors.Source: §J.1 · p. 140

J.2 Pairing Majoranas at different real times

  • Pairing evolved Majoranas at different real times yields an exponentially small error bound whose (1 + T)^2 exponent coefficient is independent of d.The paired product follows the stated order by increasing qi, then increasing i.Source: §J.2 · p. 141

J.3 Averaging the paired site labels

  • For distinct site labels and arbitrary real times, the paired-label product can be compared with the product formed from independent labels while keeping its displayed order fixed.The joint law’s permutation invariance underlies the replacement.Source: §J.3 · p. 143

J.4 Source powers under deletion of one Majorana

  • Averaging paired site labels and deleting cavity interactions yields a bound with an exponent independent of the fixed source order, for each of four fixed sets.The deletion comparison uses the source-power estimates for the cavity interactions.Source: §J.3 · p. 143, §J.4 · p. 144

J.5 Repeated site labels and the factorial tail

  • A logarithmic cutoff PN = ⌈Cm,L0 log(N + 2)⌉ makes omitted cavity terms exponentially small in N, including terms with repeated or intersecting site labels.No distinct-label assumption is needed to bound omitted coefficients.Source: §J.5 · pp. 145–146

J.6 Summing the coefficient comparison

  • Summing the retained cavity coefficients gives a comparison uniform in t and fixed odd m, and the associated scalar series converges absolutely.The endpoint limits follow by dominated convergence because the bounds are uniform in the external insertion time.Source: §J.6 · pp. 146–147

K Recovery from a positive spectral kernel

  • The result holds with exponent ζ = min{θω0, cκ, 1/3} > 0, where θ = min{2/3, ℓκ/2} > 0, assuming both measures are probabilities and the target has an exponential moment.The result is proved first for sufficiently small positive ϵ; for larger ϵ, C is increased using |G(it) − G∗(it)| ≤ 1.Source: K Recovery from a positive spectral… · pp. 148–149

L.1 Gaussian differentiation of normalized expectations

  • For positive replica functions, Gaussian covariance interpolation bounds their expectation ratio by exp(2b²n²∥∆∥∞), without separately comparing partition functions.The differential bound is |∂tνt(f)| ≤ 2β²n²∥∆∥∞νt(f).Source: §L.1 · p. 150

L.2 The statistical input and finite-size normalization

  • Overlap estimates below the transition transfer to the distinct-site model, while its limiting pressure and static boundary agree with those of the ordered model.The transfer uses covariance interpolation; the expected log partition functions differ by O(1), and the result applies to mixtures with smallest nonzero order at least three, including odd interaction orders.Source: §L.2 · p. 151

L.3 A cavity proof of the overlap-moment upgrade

This section develops finite-input guarantees for the overlap-moment upgrade and cavity recursion, including covariance and active-site bounds, error control, Hermite reconstruction, and bit-complexity bounds. It also extends Theorem 26 to additional interaction conventions and establishes SK graph bounds with exact graph and deterministic-coloring evaluators.

L.3 A cavity proof of the overlap-moment upgrade

  • Under a uniform macroscopic-overlap estimate, cavity induction proves the overlap-moment bound (7.6) with constants uniform on a fixed temperature interval.The induction starts at M0 = 1 and absorbs the first term in its moment estimate.Source: §L.3 · pp. 151–152

L.4 Global and cavity covariance moments

  • Sufficiently high even overlap moments imply polynomially decaying moments for fixed products of off-diagonal covariances, uniformly over sites and 0 ≤ β ≤ b.The same bounds extend to local covariances and products whose replica pairs share labels.Source: §L.4 · p. 153

L.5 Proof of active-site concentration

  • Flipping spin i in every replica and relabeling Gaussian coordinates preserves the disorder law and Gibbs weights, proving an exact zero for monomials with an odd active replica subset.For nonempty even B, 0 ≤ x^|B| ≤ x^2 for x in [−1, 1].Source: §L.5 · p. 153

L.6 The local cavity remainder

  • At every fixed expansion order, the local cavity remainder is O(N^-Lκ), without requiring independence among cavity covariance factors.Hölder's inequality and the covariance moment bounds control the products in the remainder.Source: §L.6 · p. 154

L.7 Collision counting and the finite recursion

  • The finite recursion has bounded depth and replica range; fixed cutoffs yield error O(N^-Q-1) for any requested fixed precision exponent Q.Collision-free updates increase support, while collision rows have total mass O(1/N); support, collision, and local-remainder errors are controlled separately.Source: §L.7 · p. 155

L.8 The finite triangular hierarchy

  • A finite triangular hierarchy can be truncated under the stated boundedness and nilpotence conditions, with computed-block consistency error adding O(ϵ) at fixed orders.For the classical recursion, support cutoffs make the upward expansion nilpotent, and collision rows have mass O(1/N).Source: §L.8 · p. 156

L.9 Hermite reconstruction and the complete tail

  • Hermite reconstruction controls the discarded Gaussian L2 tail using derivative bounds, Bessel’s inequality, and completeness, without assuming convergence of a differentiated infinite series.The fixed-monomial cavity error transfers to the approximation, and Parseval identifies the discarded coefficient sum with squared error.Source: §L.9 · pp. 156–157

L.10 Counting, finite input, and bit complexity

  • At fixed cutoffs, the algorithm uses polynomially many operations and O(log N) fractional and integer bits for finite input and numerical computation.The input coordinates are rounded in a logarithmic-size box; scalar rounding errors can be made an arbitrarily small fixed inverse power of N.Source: §L.10 · p. 158
  • The bit-complexity argument combines exact-disorder mean-square estimates with deterministic numerical estimates on the input box and adds the box’s failure probability.It does not claim an unconditional mean-square numerical bound from the boxwise calculation alone.Source: §L.10 · p. 159

L.11 Ordered interactions and exact-variance normalization

  • Theorem 26 also holds for the ordered model, including repeated positions, and for the distinct-site model with its specified coefficients.The proof retains the exact coefficients at finite N and completes the estimates for both conventions.Source: §L.11 · pp. 159–160

M.1 Bounds for the omitted graphs

  • The omitted graph classes have orthogonal sums, and the stated graph-mass bound holds uniformly in N and the boundary A.The proof establishes the omitted-graph estimate for every fixed β < 1.Source: §M.1 · pp. 160, 162

M.2 Exact core and subset calculations

  • At fixed cutoffs and observable degree, the exact evaluator counts retained colorful simple graphs in 2^O_B,ℓ(s)N^O(1) operations.The graph estimates concern the original Gaussian disorder for 0 < β < 1; numerical approximation is treated separately.Source: M SK cavity estimates and graph… · p. 160, §M.2 · p. 164

M.3 Deterministic average-balanced colorings

  • A deterministic coloring family achieves no larger discrepancy than the randomized construction, with a conservative construction cost of m²N² poly(s)2^s operations.The construction also has polynomial bit complexity in the stated parameters.Source: §M.3 · pp. 164–165

M.4 From average color balance to simultaneous error

The proof turns average color balance into a simultaneous-error guarantee, bounds the denominator’s lower tail, and verifies that finite-precision evaluation preserves the theorem in polynomial bit complexity.

M.4 From average color balance to simultaneous error

  • Summing variance masses across support sizes proves the simultaneous-error bound without requiring a discrepancy guarantee for every individual support V.The support-size contributions are already summed, so no additional factor for their number is needed.Source: §M.4 · p. 166

M.5 A quantitative lower tail for the denominator

  • For every fixed s > 0, the denominator lower-tail probability is at most Cβe^-cβu^2 in the stated range, proving (8.33).The range restriction holds for sufficiently large N when u = s log N.Source: §M.5 · p. 168

M.6 Finite precision and the polynomial bit algorithm

  • Theorem 31 holds for the original continuous-disorder model after combining the ideal estimator guarantee with deterministic rounding-error control, and the proof has polynomial bit complexity.The algorithm rounds the edge weights for computation; the rounding is treated as a deterministic perturbation, not a replacement disorder distribution.Source: §M.6 · pp. 168, 170
Loading 2610.06807v1…