SYK Gibbs-state copies on the learner's register, Majorana-pair measurements, and the normalized coupling error
DefinitionSYKCavity_Supplement_PairLearnerFor even the Majorana operators of the mission (Jordan–Wigner generators) act on qubits. This file connects them to the published copy-learner model and fixes the objects of Theorem 19.
- The Gibbs state of Section 3's SYK Hamiltonian is
It is transported to the learner's register by identifying each qubit's basis with . 2. A perfect matching of the sites is a set of pairwise disjoint pairs covering all sites. The pair algebra of is the complex span of the strings , . Since the pair operators , , commute and , it is the algebra these pair operators generate. 3. A learner measures only Majorana pairs when each round consumes exactly one copy and, for every record of outcomes, the probability of the round's outcome is for an effect in the pair algebra of some perfect matching. The matching may depend on earlier outcomes and on the round's own random bits. 4. The normalized error of an estimate is . The estimate is read from the learner's output bits with the published dyadic block decoder.
These objects express Theorem 19: a learner that sees only copies of , measures one copy at a time in a joint eigenbasis of commuting Majorana pairs (as Lemma 25 does), and outputs couplings with small normalized error.
Formalization Note The learner is the published StationarityTest.GibbsLearner on nq N qubits; nq N = N/2 for even N. The 4-subsets are enumerated by Fintype.equivFin for decoding.
import Mathlib
import Definitions.Def_SYKCavity_Majorana
import Definitions.Def_StationarityTest_Learner
open MeasureTheory
namespace SYKCavity.Supplement
/-!
# Copies of the SYK Gibbs state on the learner's register, Majorana-pair measurements, the
# normalized coupling error
A. Schmidhuber, A. 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;
Gibbs state `ρ_β = e^{βH}/Tr e^{βH}` with Section 3's `H = √(3/(8N³)) Σ_A J_A Γ_A`, p.20;
Lemma 25, pp.56–57 (each copy undergoes a joint measurement of `N/2` commuting Majorana pairs).
**Formalization Note.**
* The learner is the published `StationarityTest.GibbsLearner` on the `nq N = ⌈N/2⌉`-qubit register
(`= N/2` for even `N`). Its basis states are `QAlgorithms.Qubits n = Fin n → Bool`, those of the
base Majoranas are `FermiCap.Gaussian.Qubits n = Fin n → Fin 2`; `qubitEquiv` identifies them
qubit by qubit through `Fin 2 ≃ Bool` (`0 ↦ false`, `1 ↦ true`), and `toReg` transports an
operator along it.
* `gibbs β N J = e^{βH}/Tr e^{βH}` with the base `expH` (Section 3's `H = Hgamma N J`, plus sign).
* A perfect matching of the sites is a set of pairwise disjoint 2-subsets covering `Fin N`.
`pairAlgebra N M` is the complex span of the strings `Γ_{∪S}` for `S ⊆ M`; since the pair
operators `Γ_{a,b} = iψ_aψ_b` of `M` commute and `∏_{P∈S} Γ_P = ±Γ_{∪S}`, it is the algebra
generated by the pair operators of `M`.
* `MeasuresOnlyPairs L`: every round consumes exactly one copy, and in every round, for every
record of outcomes, the probability of the round's outcome is `Re Tr(ρ F)` for an effect `F`
in the pair algebra of some perfect matching (which may depend on the earlier outcomes and on
the round's own outcome bits, i.e. on classical randomness). This is "the quantum computer only
measures expectations of pairs of Majorana" (Theorem 19, last sentence; Lemma 25).
* `normErr N Ĵ J = ‖Ĵ − J‖₂ / √C(N,4)`; `estimate` reads the learner's output bits with the
published decoder `StationarityTest.decodeBlocks`, 4-subsets enumerated by
`Fintype.equivFin`.
-/
open SYKCavity
/-- The identification of the learner's basis states `Fin n → Bool` with the base register's basis
states `Fin n → Fin 2`, qubit by qubit (`false ↦ 0`, `true ↦ 1`). -/
def qubitEquiv (n : ℕ) : QAlgorithms.Qubits n ≃ FermiCap.Gaussian.Qubits n :=
Equiv.arrowCongr (Equiv.refl (Fin n)) finTwoEquiv.symm
/-- An operator on the base register, transported to the learner's register. -/
noncomputable def toReg {N : ℕ} (X : MOp N) :
Matrix (QAlgorithms.Qubits (nq N)) (QAlgorithms.Qubits (nq N)) ℂ :=
Matrix.reindex (qubitEquiv (nq N)).symm (qubitEquiv (nq N)).symm X
/-- The SYK Gibbs state `ρ_β = e^{βH}/Tr e^{βH}` for Section 3's Hamiltonian `H = Hgamma N J`. -/
noncomputable def gibbs (β : ℝ) (N : ℕ) (J : Quad N → ℝ) : MOp N :=
((expH β N J 1).trace)⁻¹ • expH β N J 1
/-- `M` is a perfect matching of the sites: pairwise disjoint 2-subsets covering `Fin N`. -/
def IsPerfectMatching {N : ℕ} (M : Finset (Finset (Fin N))) : Prop :=
(∀ P ∈ M, P.card = 2) ∧ (∀ P ∈ M, ∀ Q ∈ M, P ≠ Q → Disjoint P Q) ∧
∀ i : Fin N, ∃ P ∈ M, i ∈ P
/-- The algebra generated by the commuting pair operators `iψ_aψ_b`, `{a, b} ∈ M`: the span of
the strings `Γ_{∪S}`, `S ⊆ M`. -/
noncomputable def pairAlgebra (N : ℕ) (M : Finset (Finset (Fin N))) : Submodule ℂ (MOp N) :=
Submodule.span ℂ ((fun S : Finset (Finset (Fin N)) => Gamma N (S.biUnion id)) '' {S | S ⊆ M})
/-- The learner only measures Majorana pairs: one copy per round, and every outcome of every
round has an effect operator in the pair algebra of some perfect matching. -/
def MeasuresOnlyPairs {N out : ℕ} (L : StationarityTest.GibbsLearner (nq N) out) : Prop :=
(∀ k, L.copies k = 1) ∧
∀ (z : (k : Fin L.R) → QAlgorithms.Qubits (L.copies k * nq N + L.anc k)) (k : Fin L.R),
∃ M : Finset (Finset (Fin N)), IsPerfectMatching M ∧
∃ F ∈ pairAlgebra N M, ∀ ρ : MOp N, L.roundProb (toReg ρ) z k = (ρ * F).trace.re
/-- The normalized error `‖Ĵ − J‖₂ / √C(N,4)`. -/
noncomputable def normErr (N : ℕ) (Jhat J : Quad N → ℝ) : ℝ :=
Real.sqrt (∑ A, (Jhat A - J A) ^ 2) / Real.sqrt (N.choose 4 : ℝ)
/-- The coupling estimate `Ĵ ∈ ℝ^{C([N],4)}` written by the output bits `x`, read with the
published block decoder. -/
noncomputable def estimate (N len wp : ℕ) (x : Fin (Fintype.card (Quad N) * (len + 1)) → Bool) :
Quad N → ℝ :=
StationarityTest.decodeBlocks (Fintype.equivFin (Quad N)) len wp x
end SYKCavity.Supplement