Theorem 6.3 (pp.24–25, eq. (37)) — bridge from lemma_6_2
OpenCritWinSpin.p6b_theorem_6_3_from_lemma_6_2critical-windowp2o-v1reductionspin-systems
Assuming the statement of Lemma 6.2 (p.22, eqs. (32)–(33)), the full conclusion of Theorem 6.3 (pp.24–25, eq. (37)) holds. This isolates the constructions of that section from the prerequisite estimate.
Preamble
import Mathlib import Definitions.Def_IsingLTL_BeliefProp_TVDist import Definitions.Def_CritWinSpin_Lhat import Definitions.Def_CritWinSpin_nuPm open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
namespace CritWinSpin
/-- Bridge lemma for Theorem 6.3 (pp.24–25, eq. (37)): the target conclusion given Lemma 6.2 (p.22, eqs. (32)–(33)). -/
theorem p6b_theorem_6_3_from_lemma_6_2 (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) (hP : ∀ (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p), ∃ θ₀ Cₛ : ℝ, 0 < θ₀ ∧ 0 < Cₛ ∧
∀ (n r : ℕ) (J₀ : Matrix (Fin n) (Fin n) ℝ) (h₀ : Fin n → ℝ) (θ : ℝ) (û : ℚ) (L : ℝ),
1 ≤ n → 1 ≤ r → J₀.IsSymm → (∀ i, J₀ i i = 0) → 0 < θ → θ ≤ θ₀ → IsUhat S θ r û →
(n : ℝ) ≤ L →
(r : ℝ) * θ * (û : ℝ) ^ 2 ≥
Cₛ * (n : ℝ) * (max 1 (width J₀ h₀)) ^ 2 *
((n : ℝ) * Real.log ((r : ℝ) + 1) + L + 1) →
∀ y : BinCfg n,
(∑ σ : Config S (Fin n × Fin r), nuProd S (tau S + θ) y σ *
(open Classical in if ∃ i, cloudSum σ i = 0 then (1 : ℝ) else 0)) ≤ Real.exp (-L) ∧
(∑ σ : Config S (Fin n × Fin r), nuProd S (tau S + θ) y σ *
(Real.exp |Dy J₀ h₀ (û : ℝ) y σ| *
(if 1 < |Dy J₀ h₀ (û : ℝ) y σ| then (1 : ℝ) else 0))) ≤ Real.exp (-L) ∧
Real.exp (-1) * (1 - Real.exp (-L)) ≤
(∑ σ : Config S (Fin n × Fin r), nuProd S (tau S + θ) y σ *
Real.exp (Dy J₀ h₀ (û : ℝ) y σ)) ∧
(∑ σ : Config S (Fin n × Fin r), nuProd S (tau S + θ) y σ *
Real.exp (Dy J₀ h₀ (û : ℝ) y σ)) ≤ Real.exp 1 + Real.exp (-L)) :
∃ Cρ Ccap Cv : ℝ, 0 < Cρ ∧ 0 < Ccap ∧ 0 < Cv ∧
∀ (w ε : ℝ) (Ac Cc : ℕ), 1 ≤ w → 0 < ε → ε < dExp p → GadgetParams p w ε Ac Cc →
∃ (liftF : Str → Str) (slotM : PPT) (n₀ : ℕ), CookPvsNP.PolyTimeComputable liftF ∧
∀ (n : ℕ) (H : Inst n), n₀ ≤ n → H.1.IsSymm → (∀ i, H.1 i i = 0) →
width (castM H.1) (castV H.2) ≤ (n : ℝ) ^ w →
-- (i), for every admissible `û`
(∀ û : ℚ, IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) û →
(castM (liftInst S p Ac Cc H û).1).PosSemidef ∧
((tau S * (1 + ((n * cloudSize p Cc n : ℕ) : ℝ) ^ (-dExp p + ε))) •
(1 : Matrix (Fin (n * cloudSize p Cc n)) (Fin (n * cloudSize p Cc n)) ℝ) -
castM (liftInst S p Ac Cc H û).1).PosSemidef ∧
width (castM (liftInst S p Ac Cc H û).1) (castV (liftInst S p Ac Cc H û).2) ≤ Cρ ∧
(H.2 = 0 → (liftInst S p Ac Cc H û).2 = 0)) ∧
-- (i), the polynomial-time computation
(∃ û : ℚ, IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) û ∧
liftF (encInst H) = tupleCode [encInst (liftInst S p Ac Cc H û), encRat û]) ∧
-- (ii)
(∀ û : ℚ, IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) û →
(∀ y : BinCfg n,
tvDist (slotKernel S p Cc slotM H û y)
(idealSlot S (((tauQ S + thetaQ p Ac Cc n : ℚ) : ℝ)) (castM H.1) (castV H.2)
(û : ℝ) y) ≤
Real.exp (-(2 * (n : ℝ) ^ 2))) ∧
LhatDecodes (slotKernel S p Cc slotM H û) ∧
∀ k T : ℕ, 1 ≤ k → ⌈Ccap * ((k : ℝ) + (n : ℝ) ^ 2)⌉₊ ≤ T →
tvDist (LhatMu (slotKernel S p Cc slotM H û) (muH (castM H.1) (castV H.2)) T k)
(gibbsTupleOpt S (castM (liftJQ S p Ac Cc H û)) (castV (liftHQ p Cc H û)) k) ≤
Cv * (T : ℝ) * Real.exp (-((n : ℝ) ^ 2))) := by sorry
end CritWinSpin
Source
Liu, Zhang, Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission (manuscript sha256 f77584da…), Theorem 6.3 (pp.24–25, eq. (37))