Bounded-distance decoding with a shared Gaussian pool from fixed-family LWE search
ProvedInfoLossLAR.WorstCase.RegevSearch.search_to_shared_pool_bddSuppose a uniform quantum circuit recovers each fixed secret with probability at least on a fresh polynomial-size table of the prescribed Gaussian LWE samples, for all sufficiently large in an infinite set . Construct a single uniform quantum circuit family , a polynomial , a negligible function , and a threshold. For every promised dimension beyond the threshold, fix a nonsingular integer basis , a positive rational width , a unary accuracy , and a rational query . Whenever a rational dual point satisfies and , the circuit must return the signed vector as a prefix with failure probability at most .
The probability averages the quantum measurement and the independent coefficient vectors in one fresh Gaussian pool. The query is fixed before the pool is drawn. Each decoder execution can reuse the same pool throughout. A proof must connect the generated search tables to the discrete fixed-family noise law in SearchOn, justify the joint error under that reuse, and realize the public input and output encodings with a uniform circuit. A suffix after a complete signed-vector encoding is allowed.
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 search_to_shared_pool_bdd
(S : Set ℕ) (hS : S.Infinite) (hpos : ∀ n ∈ S, 1 ≤ n)
(A : MFamily) (hA : IsMQPT A) (samples : Polynomial ℕ) (cutoff : ℕ)
(hsearch : SearchOn A samples cutoff S) :
∃ C : MFamily, IsMQPT C ∧ ∃ P : Polynomial ℕ, ∃ error : ℕ → ℝ,
Negligible error ∧ ∃ N : ℕ, SharedPoolBDD C P error N S := by
sorry
end InfoLossLAR.WorstCase.RegevSearch