Theorem 1.1(ii) (pp.2–3, eq. (3)) — bridge from theorem_7_2
OpenCritWinSpin.p4c_theorem_1_1_ii_from_theorem_7_2critical-windowp2o-v1reductionspin-systems
Assuming the statement of Theorem 7.2 (p.27, eq. (40)), the full conclusion of Theorem 1.1(ii) (pp.2–3, eq. (3)) holds. This isolates the constructions of that section from the prerequisite estimate.
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_BilinearFamily import Definitions.Def_CritWinSpin_errExt import Definitions.Def_CritWinSpin_Lhat open QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp
Formal statement
namespace CritWinSpin
/-- Bridge lemma for Theorem 1.1(ii) (pp.2–3, eq. (3)): the target conclusion given Theorem 7.2 (p.27, eq. (40)). -/
theorem p4c_theorem_1_1_ii_from_theorem_7_2 (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) (hP : ∀ (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p)
(F : BilinearFamily) (src : BinarySource F) (C : ℝ) (hC : 0 < C) (hsrc : SourceProps F src C)
(w ε : ℝ) (Ac Cc : ℕ) (hw : 1 ≤ w) (hε : 0 < ε) (hεd : ε < dExp p)
(hpar : GadgetParams p w ε Ac Cc)
(Ccap : ℝ) (hCcap : 0 < Ccap)
(liftF : Str → Str) (hliftF : CookPvsNP.PolyTimeComputable liftF) (slotM : PPT)
(û : (d : ℕ) → (desc : Str) → WatersKey F desc d → ℚ) (d₁ : ℕ)
(hlift : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
IsUhat S ((thetaQ p Ac Cc (src.n d) : ℚ) : ℝ) (cloudSize p Cc (src.n d)) (û d desc key) ∧
liftF (encInst (src.ham d desc key)) =
tupleCode [encInst (liftInst S p Ac Cc (src.ham d desc key) (û d desc key)),
encRat (û d desc key)])
(hdec : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
LhatDecodes (slotKernel S p Cc slotM (src.ham d desc key) (û d desc key)))
(k T : ℕ → ℕ) (hk : EffPoly k) (hk₁ : ∀ d, 1 ≤ k d) (hT : EffPoly T)
(hTk : ∀ d, ⌈Ccap * ((k d : ℝ) + 1 + (src.n d : ℝ) ^ 2)⌉₊ ≤ T d)
(v₁ v₂ : ℕ → ℝ)
(hv₁ : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
tvDist (LhatMu (slotKernel S p Cc slotM (src.ham d desc key) (û d desc key))
(muH (castM (src.ham d desc key).1) (castV (src.ham d desc key).2)) (T d) (k d))
(gibbsTupleOpt S (castM (liftJQ S p Ac Cc (src.ham d desc key) (û d desc key)))
(castV (liftHQ p Cc (src.ham d desc key) (û d desc key))) (k d)) ≤ v₁ d)
(hv₂ : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
tvDist (LhatMu (slotKernel S p Cc slotM (src.ham d desc key) (û d desc key))
(muH (castM (src.ham d desc key).1) (castV (src.ham d desc key).2)) (T d) (k d + 1))
(gibbsTupleOpt S (castM (liftJQ S p Ac Cc (src.ham d desc key) (û d desc key)))
(castV (liftHQ p Cc (src.ham d desc key) (û d desc key))) (k d + 1)) ≤ v₂ d)
(A : PPT), (∃ (B : PPT) (d₀ : ℕ), ∀ d ≥ d₀,
1 - C * (T d : ℝ) * Real.sqrt (d : ℝ) * cdhAdv F B d -
((T d : ℝ) + ((T d).choose 2 : ℝ)) * (1 / (2 : ℝ) ^ d) -
2 * (T d : ℝ) * Real.exp (-((src.n0 d : ℝ) ^ 2)) - v₁ d - v₂ d ≤
errExt S (keyLiftLaw F d fun desc key =>
liftInst S p Ac Cc (src.ham d desc key) (û d desc key)) A (k d)) ∧
(∃ (B : PPT) (d₀ : ℕ), ∀ d ≥ d₀,
1 - C * (T d : ℝ) * Real.sqrt (d : ℝ) * cdhAdv F B d -
((T d : ℝ) + ((T d).choose 2 : ℝ)) * (1 / (2 : ℝ) ^ d) -
2 * (T d : ℝ) * Real.exp (-((src.n0 d : ℝ) ^ 2)) - v₁ d - v₂ d ≤
errAmp S (keyLiftLaw F d fun desc key =>
liftInst S p Ac Cc (src.ham d desc key) (û d desc key)) A (k d))) :
(∃ Cρ : ℝ, 0 < Cρ ∧ ∀ ε : ℝ, 0 < ε → ε < dExp p → ∀ F : BilinearFamily, CDH F →
∃ (Fam : PPT) (Nf : ℕ → ℕ),
(∀ d, d ≤ Nf d) ∧ PolyBounded Nf ∧
(∀ d, 1 ≤ d → ∀ ω : Fin (Fam.coins.eval (unary d).length) → Bool,
∃ I : Inst (Nf d), Fam.alg (tupleCode [List.ofFn ω, unary d]) = encInst I ∧
I.1.IsSymm ∧ I.2 = 0 ∧ (castM I.1).PosSemidef ∧
((tau S * (1 + (Nf d : ℝ) ^ (-dExp p + ε))) •
(1 : Matrix (Fin (Nf d)) (Fin (Nf d)) ℝ) - castM I.1).PosSemidef ∧
width (castM I.1) (castV I.2) ≤ Cρ) ∧
∀ (A : PPT) (k : ℕ → ℕ), (∀ d, 1 ≤ k d) → PolyBounded k →
(∀ c : ℕ, ∃ d₀ : ℕ, ∀ d ≥ d₀,
1 - errExt S (famLaw Fam (Nf d) d) A (k d) ≤ 1 / (Nf d : ℝ) ^ c) ∧
(∀ c : ℕ, ∃ d₀ : ℕ, ∀ d ≥ d₀,
1 - errAmp S (famLaw Fam (Nf d) d) A (k d) ≤ 1 / (Nf d : ℝ) ^ c)) := 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 1.1(ii) (pp.2–3, eq. (3))