TM2 randomized sampler witness for p4c_4_4_randmachine
OpenCritWinSpin.p4c_4_4_tm2_samplerrandmachinespin-systemstm2
Explicit RandMachine TM2 construction running discretized ULA with Hubbard-Stratonovich rejection trials in the critical window and quantized exact Gibbs enumeration outside.
Preamble
import Mathlib import Definitions.Def_IsingLTL_BeliefProp_TVDist import Definitions.Def_QAlgorithms_ClassicalBinaryEncoding import Definitions.Def_QuantumPRC_IsPolyFamily import Definitions.Def_CritWinSpin_encInst import Definitions.Def_CritWinSpin_RandMachine import Definitions.Def_CritWinSpin_Wpot open QAlgorithms.LocalHamiltonian QuantumPRC IsingLTL.BeliefProp set_option autoImplicit false open MeasureTheory IsingLTL.BeliefProp
Formal statement
namespace CritWinSpin
theorem p4c_4_4_tm2_sampler :
∀ (S : SpinLaw) (p : ℕ), IsGHS S → IsTypeP S p →
(∀ (S' : SpinLaw) (_hS' : IsGHS S'), ∃ M₀ Cₖ : ℝ, 0 < M₀ ∧ 0 < Cₖ ∧
∀ (N : ℕ) (L : Matrix (Fin N) (Fin N) ℝ) (s α : ℝ) (h : Fin N → ℝ),
tau S' < s → s ≤ 2 * tau S' + 1 →
(s • (1 : Matrix (Fin N) (Fin N) ℝ) - L * L.transpose).PosSemidef →
0 < α → α ≤ 1 →
(∀ᵐ z : Fin N → ℝ,
DifferentiableAt ℝ (fderiv ℝ (Wpot S' s L h)) z ∧
DifferentiableAt ℝ (fderiv ℝ (Ualpha S' s α L h)) z ∧
∀ v : Fin N → ℝ,
0 ≤ fderiv ℝ (fderiv ℝ (Wpot S' s L h)) z v v ∧
fderiv ℝ (fderiv ℝ (Wpot S' s L h)) z v v ≤ normSq v ∧
α * normSq v ≤ fderiv ℝ (fderiv ℝ (Ualpha S' s α L h)) z v v ∧
fderiv ℝ (fderiv ℝ (Ualpha S' s α L h)) z v v ≤ (1 + α) * normSq v) ∧
(Integrable (fun z : Fin N → ℝ => Real.exp (-Wpot S' s L h z)) ∧
Integrable (fun z : Fin N → ℝ => normSq z * Real.exp (-Wpot S' s L h z)) ∧
Integrable (fun z : Fin N → ℝ => Real.exp (-Ualpha S' s α L h z)) ∧
Integrable (fun z : Fin N → ℝ => normSq z * Real.exp (-Ualpha S' s α L h z)) ∧
max (∫ z : Fin N → ℝ, normSq z * normDens (Wpot S' s L h) z)
(∫ z : Fin N → ℝ, normSq z * normDens (Ualpha S' s α L h) z) ≤ M₀ * (N : ℝ) ∧
(1 / 2) * (∫ z : Fin N → ℝ,
|normDens (Ualpha S' s α L h) z - normDens (Wpot S' s L h) z|) ≤
α * M₀ * (N : ℝ) / 2) ∧
(∀ z w : Fin N → ℝ,
tvDist (kernelK S' s L h z) (kernelK S' s L h w) ≤
Cₖ * Real.sqrt (N : ℝ) * Real.sqrt (normSq (z - w)))) →
∀ (C₄₂ : ℝ), 0 < C₄₂ →
(∀ {N : ℕ} (J L : Matrix (Fin N) (Fin N) ℝ) (h : Fin N → ℝ) (s : ℝ),
tau S < s → J.PosSemidef → J = L * L.transpose →
Integrable (fun z : Fin N → ℝ => Real.exp (-Wpot S s L h z)) →
(∀ z : Fin N → ℝ,
0 ≤ hsV S L h z - Wpot S s L h z ∧
hsV S L h z - Wpot S s L h z ≤ (N : ℝ) * (C₄₂ * (s - tau S) ^ ((p : ℝ) / ((p : ℝ) - 1)))) ∧
0 < ∫ z : Fin N → ℝ, Real.exp (-Wpot S s L h z) ∧
Real.exp (-((N : ℝ) * (C₄₂ * (s - tau S) ^ ((p : ℝ) / ((p : ℝ) - 1))))) ≤
1 - ∫ z : Fin N → ℝ, normDens (Wpot S s L h) z * kernelK S s L h z none ∧
(∀ x : Config S (Fin N),
(∫ z : Fin N → ℝ, normDens (Wpot S s L h) z * kernelK S s L h z (some x)) /
(1 - ∫ z : Fin N → ℝ, normDens (Wpot S s L h) z * kernelK S s L h z none) =
gibbs S J h x)) →
∃ (M : RandMachine) (C_poly C_exp : ℝ) (k_poly : ℕ), 0 < C_poly ∧ 0 < C_exp ∧
∀ (N : ℕ) (I : Inst N) (m : ℕ) (δ : ℝ),
I.1.IsSymm → (castM I.1).PosSemidef → 0 ≤ δ →
((tau S * (1 + δ)) • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef → 5 ≤ m →
∃ (e lhat : ℝ), 0 < e ∧ e ≤ 1 / 8 ∧ 0 ≤ lhat ∧
3 * e / 2 ≤ 1 / ((max 1 N : ℝ) ^ (((p : ℝ) - 1) / (p : ℝ))) ∧
(lhat • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef ∧
(lhat ≤ e / 2 ∨ ¬ (((lhat - e / 2) • (1 : Matrix (Fin N) (Fin N) ℝ) - castM I.1).PosSemidef)) ∧
(max 0 (lhat / tau S - 1) ≤ 1 →
∃ (M_mat : Matrix (Fin N) (Fin N) ℝ) (x₀ : Config S (Fin N))
(P : Option (Config S (Fin N)) → ℝ) (p_acc : ℝ) (Q_trials : ℕ)
(T_law : ℕ → Option (Config S (Fin N)) → ℝ) (F_law : Option (Config S (Fin N)) → ℝ),
(∀ v : Fin N → ℝ, |v ⬝ᵥ (M_mat - castM I.1).mulVec v| ≤ e * normSq v) ∧
4 * ((N : ℝ) * e / 2) ≤ 1 ∧ 2 * ((N : ℝ) * e / 2) ≤ 1 / (4 * (m : ℝ)) ∧
((e / 2) • (1 : Matrix (Fin N) (Fin N) ℝ) -
(M_mat - (castM I.1 + (e / 2) • 1))).PosSemidef ∧
IsDistribution P ∧ 0 ≤ p_acc ∧ p_acc ≤ 1 ∧
(T_law 0 none = 1 ∧ ∀ x, T_law 0 (some x) = 0) ∧
(∀ t, T_law (t + 1) none = P none * T_law t none ∧
∀ x, T_law (t + 1) (some x) = P (some x) + P none * T_law t (some x)) ∧
(F_law none = 0 ∧ ∀ x, F_law (some x) = T_law Q_trials (some x) +
(if x = x₀ then T_law Q_trials none else 0)) ∧
outLaw M (tupleCode [encInst I, encBin m]) (decConfig S N) = F_law ∧
(Q_trials : ℝ) * tvDist P (fun y => Option.elim y (1 - p_acc) (fun x => p_acc * gibbs S M_mat (castV I.2) x)) +
(1 - p_acc) ^ Q_trials ≤ 3 / (4 * (m : ℝ)) ∧
(M.time (tupleCode [encInst I, encBin m]) : ℝ) ≤
C_poly * ((N : ℝ) + (bitLen I : ℝ) + (m : ℝ)) ^ k_poly *
Real.exp (C_exp * (N : ℝ) *
(tau S * (1 + max 0 (lhat / tau S - 1)) + e - tau S) ^ ((p : ℝ) / ((p : ℝ) - 1)))) ∧
(1 < max 0 (lhat / tau S - 1) →
∃ (wtilde : Config S (Fin N) → ℝ) (ε : ℝ),
0 ≤ ε ∧ ε ≤ 1 / 2 ∧ 2 * ε ≤ 1 / (m : ℝ) ∧
(∀ x : Config S (Fin N),
(1 - ε) * gibbsWeight S (castM I.1) (castV I.2) x ≤ wtilde x ∧
wtilde x ≤ (1 + ε) * gibbsWeight S (castM I.1) (castV I.2) x) ∧
outLaw M (tupleCode [encInst I, encBin m]) (decConfig S N) =
(fun y => Option.elim y 0 (fun x => wtilde x / ∑ z, wtilde z)) ∧
(M.time (tupleCode [encInst I, encBin m]) : ℝ) ≤
C_poly * ((N : ℝ) + (bitLen I : ℝ) + (m : ℝ)) ^ k_poly *
Real.exp ((C_exp * (1 / 2 : ℝ) ^ ((p : ℝ) / ((p : ℝ) - 1))) * (N : ℝ))) := by sorry
end CritWinSpinSource
CritWinSpin