Uniform PPT instance sampler and prefix-sampling combinators
OpenCritWinSpin.p4c_1_1_ii_ppt_combcombinatorpptspin-systems
Uniform PPT instance sampler matching keyLiftLaw within 2^{-d} L1 error above threshold d1, together with uniform prefix-sampling PPT combinators A'_ext and A'_amp.
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.Complexity QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
namespace CritWinSpin
theorem p4c_1_1_ii_ppt_comb :
(∀ (S : SpinLaw) (p Ac Cc : ℕ) (F : BilinearFamily) (src : BinarySource F)
(liftF : Str → Str), CookPvsNP.PolyTimeComputable liftF →
∀ (û : (d : ℕ) → (desc : Str) → WatersKey F desc d → ℚ) (d₁ : ℕ), 1 ≤ d₁ →
(∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
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)]) →
∃ Fam : PPT,
(∀ d, 1 ≤ d → d < d₁ → ∀ ω : Fin (Fam.coins.eval (unary d).length) → Bool,
Fam.alg (tupleCode [List.ofFn ω, unary d]) =
encInst ((0 : Matrix (Fin (src.n d * cloudSize p Cc (src.n d))) (Fin (src.n d * cloudSize p Cc (src.n d))) ℚ),
(0 : Fin (src.n d * cloudSize p Cc (src.n d)) → ℚ))) ∧
(∀ d ≥ d₁,
(∀ ω : Fin (Fam.coins.eval (unary d).length) → Bool,
∃ desc key, GenSupport F.gen d desc ∧
Fam.alg (tupleCode [List.ofFn ω, unary d]) =
encInst (liftInst S p Ac Cc (src.ham d desc key) (û d desc key))) ∧
(let Pi₀ := keyLiftLaw F d fun desc key => liftInst S p Ac Cc (src.ham d desc key) (û d desc key)
let Pi₁ := famLaw Fam (src.n d * cloudSize p Cc (src.n d)) d
(∀ M ∈ Pi₁.supp, 0 ≤ Pi₁.prob M) ∧
Pi₁.supp ⊆ Pi₀.supp ∧
(∀ M ∈ Pi₀.supp, M ∉ Pi₁.supp → Pi₁.prob M = 0) ∧
∑ M ∈ Pi₀.supp, |Pi₁.prob M - Pi₀.prob M| ≤ 1 / (2 : ℝ) ^ d))) ∧
(∀ (S : SpinLaw) (Nf k D : ℕ → ℕ),
(∀ d, 1 ≤ k d) → ∀ (hkD : ∀ d, k d ≤ D d), PolyBounded D → ∀ (A : PPT),
∃ (A'_ext A'_amp : PPT) (w : ℕ → ℝ)
(R_ext : (d : ℕ) → Inst (Nf d) → (Fin (D d) → Config S (Fin (Nf d))) → Option (Config S (Fin (Nf d))) → ℝ)
(R_amp : (d : ℕ) → Inst (Nf d) → (Fin (D d) → Config S (Fin (Nf d))) → Option (Fin (D d + 1) → Config S (Fin (Nf d))) → ℝ),
(∀ d, 1 / (2 * (D d : ℝ)) ≤ w d ∧ w d ≤ 1) ∧
(∀ d M X o, 0 ≤ R_ext d M X o) ∧ (∀ d M X, ∑ o, R_ext d M X o = 1) ∧
(∀ d M X o, 0 ≤ R_amp d M X o) ∧ (∀ d M X, ∑ o, R_amp d M X o = 1) ∧
(∀ d M X o,
A'_ext.prob (tupleCode [encInst M, encSamples X]) (fun s => decConfig S (Nf d) s = o) =
w d * A.prob (tupleCode [encInst M, encSamples (fun j : Fin (k d) => X ⟨j.1, lt_of_lt_of_le j.2 (hkD d)⟩)])
(fun s => decConfig S (Nf d) s = o) + (1 - w d) * R_ext d M X o) ∧
(∀ d M X o,
A'_amp.prob (tupleCode [encInst M, encSamples X]) (fun s => decTuple S (Nf d) (D d + 1) s = o) =
w d * (∑ y : Option (Fin (k d + 1) → Config S (Fin (Nf d))),
(if Option.map (fun Y (j : Fin (D d + 1)) =>
if h : j.1 < k d + 1 then Y ⟨j.1, h⟩ else X ⟨k d + (j.1 - (k d + 1)), by have := hkD d; omega⟩) y = o
then (1 : ℝ) else 0) *
A.prob (tupleCode [encInst M, encSamples (fun j : Fin (k d) => X ⟨j.1, lt_of_lt_of_le j.2 (hkD d)⟩)])
(fun s => decTuple S (Nf d) (k d + 1) s = y)) +
(1 - w d) * R_amp d M X o)) := by sorry
end CritWinSpinSource
CritWinSpin