One coefficient Gaussian sample from bounded-distance decoding with a shared pool
ProvedInfoLossLAR.WorstCase.RegevSearch.shared_pool_bdd_to_gaussian_eventsFix an infinite set of positive dimensions and a uniform quantum decoder equipped with CoherentPoolBDDBudget on . Construct a single uniform circuit family and a negligible . For every sufficiently large , nonsingular integer basis , positive rational at least dgsThreshold B, and unary accuracy , run on the count-one input. With probability exactly one the measured word begins with the encoding of some signed coefficient vector. For every finite set , the probability of a prefix encoding a member of differs from the ideal Gaussian coefficient mass of by at most .
The proof must supply the broad initial samples, coherent decoder calls and uncomputation, and a width schedule reaching the requested rational width. The budget measures failure on a fixed reference query after averaging one shared Gaussian pool. A proof must justify its use on the ideal query superposition and the replacement of intermediate pools while preserving the joint computation. Every measured output of positive probability must have a valid signed-vector prefix, including outcomes of any truncated or fallback branch. Circuit output may carry padding after that prefix.
import Definitions.Def_InfoLossLAR_RegevSearch_SharedPoolBDD set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch open scoped BigOperators Classical
namespace InfoLossLAR.WorstCase.RegevSearch
theorem shared_pool_bdd_to_gaussian_events
(S : Set ℕ) (hS : S.Infinite) (hpos : ∀ n ∈ S, 1 ≤ n)
(C : MFamily) (hC : IsMQPT C) (P : Polynomial ℕ) (N : ℕ)
(hbudget : CoherentPoolBDDBudget C P N S) :
∃ H : MFamily, IsMQPT H ∧ ∃ e : ℕ → ℝ, Negligible e ∧
∃ N' : ℕ, ∀ n ∈ S, N' ≤ n →
∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
∀ r : ℚ, 0 < r → dgsThreshold B ≤ (r : ℝ) →
∀ k : ℕ,
let w := dgsInput B r 1 k
outputProb H w (fun out => ∃ z : Fin n → ℤ, encVec encI z <+: out) = 1 ∧
∀ T : Finset (Fin n → ℤ),
|outputProb H w (fun out => ∃ z ∈ T, encVec encI z <+: out) -
∑ z ∈ T, coefficientMass B r z| ≤ (e n + 1 / ((k : ℝ) + 1)) / 2 := by
sorry
end InfoLossLAR.WorstCase.RegevSearch