Theorem 7.2 (p.27, eq. (40)) — bridge from theorem_6_3
OpenCritWinSpin.p7b_theorem_7_2_from_theorem_6_3critical-windowp2o-v1reductionspin-systems
Assuming the statement of Theorem 6.3 (pp.24–25, eq. (37)), the full conclusion of Theorem 7.2 (p.27, eq. (40)) 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 open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
namespace CritWinSpin
/-- Bridge lemma for Theorem 7.2 (p.27, eq. (40)): the target conclusion given Theorem 6.3 (pp.24–25, eq. (37)). -/
theorem p7b_theorem_7_2_from_theorem_6_3 (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) (hP : ∀ (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p), ∃ 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)))) :
(∃ (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)) := 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 7.2 (p.27, eq. (40))