Theorem 19 — SYK couplings from Gibbs-state copies by Majorana-pair measurements
OpenSYKCavity.Supplement.theorem_19Fix . Let be the SYK Hamiltonian with independent standard Gaussian couplings , and its Gibbs state. There are constants , () and a polynomial such that the following holds for all sufficiently large even and all , with integers .
- There is a quantum algorithm that uses
independent copies of , and polynomially many elementary quantum gates and classical bit operations in . Its output satisfies, for every fixed ,
Here covers measurement outcomes and classical randomness. 2. In particular, for fixed and and all sufficiently large even , the algorithm uses samples (6.3). With probability at least over , it outputs, with probability at least , an estimate with
- 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 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 . The pair-measurement clause is MeasuresOnlyPairs of the PairLearner file. The polynomial is .
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
import Mathlib import Definitions.Def_SYKCavity_Supplement_PairLearner open MeasureTheory
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