Polynomial-time lift map and slot sampling PPT algorithm for Theorem 6.3
OpenCritWinSpin.p6b_6_3_algo_witnesscritical-windowp2o-v1spin-systems
For a GHS spin law and all admissible gadget parameters \mathrm{liftF}\mathrm{slotM} of width at most ^w\mathrm{liftF}(\mathrm{encInst}(H))\hat{u}\mathrm{liftInst}(H, \hat{u})\mathrm{slotKernel}(H, \hat{u}, y)\mathrm{idealSlot}\exp(-2n^2)\mathrm{LhatDecodes}$.
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
/-- Polynomial-time lifting reduction and rejection-sampling slot machine for Theorem 6.3. -/
theorem p6b_6_3_algo_witness (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) :
∀ (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 →
(∃ û : ℚ, IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) û ∧
liftF (encInst H) = tupleCode [encInst (liftInst S p Ac Cc H û), encRat û]) ∧
(∀ û : ℚ, 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 û)) := 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)