Cook TM lift and quantized DP/rejection PPT slot machine for p6b_6_3_algo_witness
OpenCritWinSpin.p6b_6_3_tm_implgadgetpptspin-systemstm
Explicit polynomial-time TM computing the lifted Hamiltonian instance with û and quantized DP/rejection PPT slot machine within exp(-2n^2) L1 error of idealSlot.
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
theorem p6b_6_3_tm_impl (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₂ : ℕ) (û_fn : ℕ → ℚ),
CookPvsNP.PolyTimeComputable liftF ∧
(∀ n : ℕ, n₂ ≤ n → IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) (û_fn 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 →
liftF (encInst H) =
tupleCode [encInst (liftInst S p Ac Cc H (û_fn n)), encRat (û_fn n)] ∧
∀ (û : ℚ), IsUhat S ((thetaQ p Ac Cc n : ℚ) : ℝ) (cloudSize p Cc n) û →
∀ y : BinCfg n,
IsDistribution (slotKernel S p Cc slotM H û y) ∧
∃ (nuT aT : Config S (Fin n × Fin (cloudSize p Cc n)) → ℝ),
(∀ σ, 0 ≤ nuT σ) ∧ ∑ σ, nuT σ = 1 ∧ (∀ σ, 0 ≤ aT σ ∧ aT σ ≤ 1) ∧
(∀ σ, slotKernel S p Cc slotM H û y (some σ) = nuT σ * aT σ) ∧
(∀ σ, 0 < slotKernel S p Cc slotM H û y (some σ) →
0 < idealSlot S (((tauQ S + thetaQ p Ac Cc n : ℚ) : ℝ))
(castM H.1) (castV H.2) (û : ℝ) y (some σ)) ∧
∑ σ : Config S (Fin n × Fin (cloudSize p Cc n)),
|nuT σ - nuProd S (((tauQ S + thetaQ p Ac Cc n : ℚ) : ℝ)) y σ| ≤
(1 / 2 : ℝ) * Real.exp (-(2 * (n : ℝ) ^ 2)) ∧
(∀ σ, 0 < nuT σ →
|aT σ - ay (castM H.1) (castV H.2) (û : ℝ) y σ| ≤
(1 / 2 : ℝ) * Real.exp (-(2 * (n : ℝ) ^ 2))) := by sorry
end CritWinSpinSource
CritWinSpin