Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 19 — SYK couplings from CβN5ε−2log⁡(N/δ)C_\beta N^5\varepsilon^{-2}\log(N/\delta)Cβ​N5ε−2log(N/δ) Gibbs-state copies by Majorana-pair measurements

Open
SYKCavity.Supplement.theorem_19

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

bit-complexityising-modelp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-learningspin-glassessyk-model

Fix 0<β<∞0<\beta<\infty0<β<∞. Let H=3/(8N3)∑A∈([N]4)JAΓAH=\sqrt{3/(8N^3)}\sum_{A\in\binom{[N]}4}J_A\Gamma_AH=3/(8N3)​∑A∈(4[N]​)​JA​ΓA​ be the SYK Hamiltonian with independent standard Gaussian couplings JAJ_AJA​, and ρβ=eβH/Tr⁡eβH\rho_\beta=e^{\beta H}/\operatorname{Tr}e^{\beta H}ρβ​=eβH/TreβH its Gibbs state. There are constants CβC_\betaCβ​, Cβ,pC_{\beta,p}Cβ,p​ (p≥2p\ge2p≥2) and a polynomial such that the following holds for all sufficiently large even NNN and all ε=2−b\varepsilon=2^{-b}ε=2−b, δ=2−r\delta=2^{-r}δ=2−r with integers b,r≥1b,r\ge1b,r≥1.

  1. There is a quantum algorithm that uses
S≤CβN5ε−2log⁡Nδ(6.1)S\le C_\beta N^5\varepsilon^{-2}\log\frac N\delta\qquad(6.1)S≤Cβ​N5ε−2logδN​(6.1)

independent copies of ρβ\rho_\betaρβ​, and polynomially many elementary quantum gates and classical bit operations in N,ε−1,log⁡(δ−1)N,\varepsilon^{-1},\log(\delta^{-1})N,ε−1,log(δ−1). Its output J^∈R([N]4)\hat J\in\mathbb R^{\binom{[N]}4}J^∈R(4[N]​) satisfies, for every fixed p≥2p\ge2p≥2,

Pr⁡J[Pr⁡alg[∥J^−J∥2(N4)>ε ∣ J]>δ]≤Cβ,p(Nε)−p+2e−N2.(6.2)\Pr_J\Big[\Pr_{\mathrm{alg}}\Big[\frac{\|\hat J-J\|_2}{\sqrt{\binom N4}}>\varepsilon\ \Big|\ J\Big]>\delta\Big]\le C_{\beta,p}(N\varepsilon)^{-p}+2e^{-N^2}.\qquad(6.2)JPr​[algPr​[(4N​)​∥J^−J∥2​​>ε ​ J]>δ]≤Cβ,p​(Nε)−p+2e−N2.(6.2)

Here Pr⁡alg\Pr_{\mathrm{alg}}Pralg​ covers measurement outcomes and classical randomness. 2. In particular, for fixed a>0a>0a>0 and 0<c<10<c<10<c<1 and all sufficiently large even NNN, the algorithm uses S≤CβN5+2clog⁡(N/δ)S\le C_\beta N^{5+2c}\log(N/\delta)S≤Cβ​N5+2clog(N/δ) samples (6.3). With probability at least 1−N−a1-N^{-a}1−N−a over JJJ, it outputs, with probability at least 1−δ1-\delta1−δ, an estimate with

∥J^−J∥2(N4)≤N−c.(6.4)\frac{\|\hat J-J\|_2}{\sqrt{\binom N4}}\le N^{-c}.\qquad(6.4)(4N​)​∥J^−J∥2​​≤N−c.(6.4)
  1. The quantum computer only measures expectations of pairs of Majoranas on the Gibbs state.

This is the learning application of the paper's expansion. It recovers all (N4)\binom N4(4N​) couplings to vanishing normalized error from polynomially many copies, using only single-copy measurements of commuting Majorana pairs.

Formalization Note The algorithm is a published GibbsLearner that receives only copies of ρβ\rho_\betaρβ​. The pair-measurement clause is MeasuresOnlyPairs of the PairLearner file. The polynomial is Ct(N2br)dC_t(N2^br)^dCt​(N2br)d.

Differences from the source:

  • encoding: Majoranas ψ_i with {ψ_i, ψ_j} = 2δ_ij and Section 3's H = √(3/(8N³)) Σ_A J_A Γ_A → the base Jordan–Wigner Majoranas on nq N = N/2 qubits and Hgamma N J, transported to the learner's register by the qubitwise bijection Bool ≃ Fin 2; reason: standard representation (unique up to equivalence for even N); gate counts need a fixed representation
  • encoding: an algorithm using S copies of ρ_β and polynomially many elementary quantum gates and classical bit operations in N, ε⁻¹, log(δ⁻¹) → a StationarityTest.GibbsLearner chosen after β, N, b, r, with copiesUsed ≤ C_β N⁵ (2^b)² log(N·2^r) and time ≤ C_t (N·2^b·r)^d, C_t and d depending on β only; reason: published copy-learner model; log δ⁻¹ = r log 2 and N, 2^b, r ≥ 1, so every polynomial in N, ε⁻¹, log δ⁻¹ is bounded by such a monomial
  • reading: The quantum computer only measures expectations of pairs of Majorana on the Gibbs state → MeasuresOnlyPairs L: every round uses exactly one copy, and every outcome of every round has an effect operator in the algebra generated by the commuting pair operators iψ_aψ_b of some perfect matching; reason: Lemma 25 (pp.56–57): each copy undergoes a joint measurement of N/2 commuting Majorana pairs of a random perfect matching. The other reading, that the output law depends on the state only through the pair expectations Tr(ρ iψ_aψ_b), contradicts the proof, which estimates the quartic Tr(ρ Γ_A) from these joint measurements
  • generalization: for every fixed p ≥ 2 → for every real p ≥ 2, with constants C_{β,p} given by one function of p chosen after β; reason: covers every integer p ≥ 2 and specializes to it
  • encoding: Pr_alg[‖Ĵ − J‖₂/√C(N,4) > ε | J] and Pr_J → L.successProb (toReg (gibbs β N J)) of the output event, and the outer measure gaussLaw N of the set of J; reason: successProb is the learner's outcome law; outer measure needs no measurability
  • encoding: output Ĵ ∈ ℝ^{C([N],4)} → the output bits decoded by StationarityTest.decodeBlocks (sign and magnitude blocks, dyadic values), the format len, wp chosen with the learner; reason: a learner outputs bits
  • encoding: log N/δ → Real.log (N · 2^r); reason: δ = 2^{−r}; the base of the logarithm only changes C_β
  • reading: C_β in (6.1) and in (6.3); polynomially many operations in the 'in particular' clause → the same existential C_β in both clauses, and the same C_t, d with time ≤ C_t (N²·r)^d in the second clause; reason: the second clause runs the theorem's algorithm at 2^{−b} ≤ N^{−c}, 2^b ≤ 2N^c < 2N; enlarging the existential constants makes both clauses hold with one set of constants
  • reading: In particular … succeeds with probability at least 1 − N^{−a} over J, and with probability at least 1 − δ … outputs Ĵ with error ≤ N^{−c} → for every a > 0, 0 < c < 1 there is N₁ such that for even N ≥ N₁ and every r ≥ 1 some learner obeys the copy and time bounds and gaussLaw N {J : successProb(error ≤ N^{−c}) < 1 − 2^{−r}} ≤ N^{−a}; reason: literal content of (6.3)–(6.4), with δ = 2^{−r} as in the theorem's first sentence
Preamble
import Mathlib
import Definitions.Def_SYKCavity_Supplement_PairLearner

open MeasureTheory
Formal statement
namespace SYKCavity.Supplement

open SYKCavity

/-- **Theorem 19 (Learning from an SYK Gibbs state)**, pp.48–49 of A. Schmidhuber, A. Zlokapa,
*Polynomial-time algorithms for mean-field models up to the glass transition*, arXiv:2610.06807
(held version, sha256 25d817ba…cfc5), (6.1)–(6.4).

Fix `0 < β < ∞`. For all sufficiently large even `N` and `ε = 2^{−b}`, `δ = 2^{−r}` with integers
`b, r ≥ 1`, there is an algorithm using `S ≤ C_β N⁵ ε^{−2} log(N/δ)` independent copies of
`ρ_β = e^{βH}/Tr e^{βH}` and polynomially many elementary quantum gates and classical bit operations
in `N, ε^{−1}, log(δ^{−1})`, whose output `Ĵ ∈ ℝ^{C([N],4)}` satisfies, for every fixed `p ≥ 2`,
`Pr_J[Pr_alg[‖Ĵ − J‖₂/√C(N,4) > ε | J] > δ] ≤ C_{β,p}(Nε)^{−p} + 2e^{−N²}`. In particular, for
every fixed `a > 0` and `0 < c < 1`, the algorithm uses `S ≤ C_β N^{5+2c} log(N/δ)` samples and,
with probability at least `1 − N^{−a}` over `J`, outputs with probability at least `1 − δ` an
estimate with `‖Ĵ − J‖₂/√C(N,4) ≤ N^{−c}`. The quantum computer only measures expectations of
pairs of Majoranas on the Gibbs state.

**Formalization Note.**
* `H` is Section 3's `Hgamma N J = √(3/(8N³)) Σ_A J_A Γ_A`, `J ~ gaussLaw N`; the learner receives
  only copies of `toReg (gibbs β N J)` on the `nq N = N/2`-qubit register (Jordan–Wigner).
* The algorithm is a `StationarityTest.GibbsLearner`, chosen after `β, N, b, r` and before `J`.
  Its output bits are decoded by `estimate`. `Pr_alg[E | J]` is `L.successProb (toReg (gibbs β N J)) E`.
* "Polynomially many … in `N, ε^{−1}, log(δ^{−1})`": `time ≤ C_t (N·2^b·r)^d` (`log δ^{−1} = r log 2`);
  `C_t, d` depend on `β` only. In the second clause `2^b ≤ 2N^c < 2N`, written `C_t (N²·r)^d`.
* `C_β, C_t, d, N₀` and the function `p ↦ C_{β,p}` (real `p ≥ 2`) are chosen after `β` only; the
  same learner serves every `p`. `N₁` may depend on `a, c`.
* The last sentence is `MeasuresOnlyPairs L` (one copy per round, every round's effects lie in the
  algebra generated by the commuting Majorana pair operators of a perfect matching). -/
theorem theorem_19 (β : ℝ) (hβ : 0 < β) :
    ∃ Cβ : ℝ, 0 < Cβ ∧ ∃ Cp : ℝ → ℝ, ∃ Ct : ℝ, ∃ d : ℕ, ∃ N₀ : ℕ,
      (∀ N : ℕ, Even N → N₀ ≤ N → ∀ b r : ℕ, 1 ≤ b → 1 ≤ r →
        ∃ len wp : ℕ,
        ∃ L : StationarityTest.GibbsLearner (nq N) (Fintype.card (Quad N) * (len + 1)),
          MeasuresOnlyPairs L ∧
          (L.copiesUsed : ℝ) ≤
            Cβ * (N : ℝ) ^ 5 * ((2 : ℝ) ^ b) ^ 2 * Real.log ((N : ℝ) * (2 : ℝ) ^ r) ∧
          (L.time : ℝ) ≤ Ct * ((N : ℝ) * (2 : ℝ) ^ b * (r : ℝ)) ^ d ∧
          ∀ p : ℝ, 2 ≤ p →
            gaussLaw N {J | ((2 : ℝ) ^ r)⁻¹ < L.successProb (toReg (gibbs β N J))
                (fun x => ((2 : ℝ) ^ b)⁻¹ < normErr N (estimate N len wp x) J)} ≤
              ENNReal.ofReal (Cp p * ((N : ℝ) * ((2 : ℝ) ^ b)⁻¹) ^ (-p) +
                2 * Real.exp (-((N : ℝ) ^ 2)))) ∧
      ∀ a c : ℝ, 0 < a → 0 < c → c < 1 → ∃ N₁ : ℕ, ∀ N : ℕ, Even N → N₁ ≤ N →
        ∀ r : ℕ, 1 ≤ r → ∃ len wp : ℕ,
        ∃ L : StationarityTest.GibbsLearner (nq N) (Fintype.card (Quad N) * (len + 1)),
          MeasuresOnlyPairs L ∧
          (L.copiesUsed : ℝ) ≤ Cβ * (N : ℝ) ^ (5 + 2 * c) * Real.log ((N : ℝ) * (2 : ℝ) ^ r) ∧
          (L.time : ℝ) ≤ Ct * ((N : ℝ) ^ 2 * (r : ℝ)) ^ d ∧
          gaussLaw N {J | L.successProb (toReg (gibbs β N J))
                (fun x => normErr N (estimate N len wp x) J ≤ (N : ℝ) ^ (-c)) <
              1 - ((2 : ℝ) ^ r)⁻¹} ≤ ENNReal.ofReal ((N : ℝ) ^ (-a)) := by sorry

end SYKCavity.Supplement
Source
Schmidhuber–Zlokapa, Polynomial-time algorithms for mean-field models up to the glass transition, arXiv:2610.06807 (held version, sha256 25d817ba…cfc5), Theorem 19, pp.48–49, (6.1)–(6.4); Lemma 25, pp.56–57

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me