Spectral and width bounds for the lifted spin instance (Theorem 6.3(i))
ProvedCritWinSpin.p6b_6_3_lift_propscritical-windowp2o-v1spin-systems
For a GHS spin law , there exists a constant \rho > 0, sufficiently large of width at most ^w\hat{u}, the width is at most \rho implies zero lifted external field.
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
/-- Spectral, width, and zero-external-field properties of the lifted spin instance (Theorem 6.3, part (i)). -/
theorem p6b_6_3_lift_props (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) :
∃ Cρ : ℝ, 0 < Cρ ∧
∀ (w ε : ℝ) (Ac Cc : ℕ), 1 ≤ w → 0 < ε → ε < dExp p → GadgetParams p w ε Ac Cc →
∃ n₀ : ℕ, ∀ (n : ℕ) (H : Inst n), n₀ ≤ n → H.1.IsSymm → (∀ i, H.1 i i = 0) →
width (castM H.1) (castV H.2) ≤ (n : ℝ) ^ w →
∀ û : ℚ, 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) := by sorry
end CritWinSpinSource
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)