Rejection-sampling TV amplification bound for LhatMu (Theorem 6.3(ii))
ProvedCritWinSpin.p6b_6_3_lhat_ampcritical-windowp2o-v1spin-systems
For a GHS spin law , there exist constants {\mathrm{cap}}, C_v > 0, instances , admissible magnetizations , and any slot Markov kernel within total variation distance of that decodes under , running for \ge \lceil C_{\mathrm{cap}}(k + n^2)\rceil in total variation distance.
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
/-- Rejection-sampling total variation bound for from Lemma 6.2 and Lemma 6.1 (Theorem 6.3, part (ii)). -/
theorem p6b_6_3_lhat_amp (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) :
∃ Ccap Cv : ℝ, 0 < Ccap ∧ 0 < Cv ∧
∀ (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 →
∀ (û : ℚ) (κ : BinCfg n → Option (Config S (Fin n × Fin (cloudSize p Cc n))) → ℝ),
IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) û →
(∀ y o, 0 ≤ κ y o) → (∀ y, ∑ o, κ y o = 1) →
(∀ y : BinCfg n,
tvDist (κ y) (idealSlot S (((tauQ S + thetaQ p Ac Cc n : ℚ) : ℝ))
(castM H.1) (castV H.2) (û : ℝ) y) ≤ Real.exp (-(2 * (n : ℝ) ^ 2))) →
LhatDecodes κ →
∀ k T : ℕ, 1 ≤ k → ⌈Ccap * ((k : ℝ) + (n : ℝ) ^ 2)⌉₊ ≤ T →
tvDist (LhatMu κ (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 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)