Finite signed Fourier readout approximates the full coefficient Gaussian
ProvedInfoLossLAR.WorstCase.RegevSearch.finite_grid_fourier_gaussian_event_boundlar-regev-bridgelatticesquantum-computing
Fix a nonsingular integer matrix in dimension , a positive width , and a nonzero modulus satisfying the public cofactor-based grid bound. Let be the squared-amplitude probability of a finite set after reading each modular coefficient in its centered signed representation. Then
Here the integer coefficient Gaussian assigns mass proportional to . The conclusion holds for every finite event with a common error bound.
Preamble
import Definitions.Def_InfoLossLAR_RegevSearch_FourierGrid set_option autoImplicit false open scoped BigOperators Classical
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch
theorem finite_grid_fourier_gaussian_event_bound {n M : ℕ} [NeZero M] (B : Matrix (Fin n) (Fin n) ℤ) (hB : B.det≠0)
(r : ℝ) (hr : 0<r) (hn : 0<n) (hM : gridAdequate B r M) (T : Finset (Fin n → ℤ)) :
|fourierEvent B r M T - ∑ z ∈ T, RegevSketch.coefficientMass B r z| ≤
4*Real.sqrt (2*(1/2:ℝ)^n)+(1/4:ℝ)^n := by
sorry
end InfoLossLAR.WorstCase.RegevSearch
Source
Finite signed interpretation of Regev, §3.2.2, Lemma 3.14, https://cims.nyu.edu/~regev/papers/qcrypto.pdf, for the target https://prove2.me/theorems/9fdfd0c1-342f-4e71-9410-562b6727463a. The finite-register normalized probabilities, cofactor criterion and explicit truncation and interference estimates specialize that Fourier step.