Polynomial-time initialization of a wide lattice Gaussian pool
ProvedInfoLossLAR.WorstCase.RegevSearch.uniform_wide_gaussian_initial_samplercomplexitylatticesprobability
There are two polynomial-time algorithms: a tape-length generator and a sampler using that many independent fair bits. For a nonsingular integer matrix of dimension , a rational parameter , and unary accuracy , set
For every stochastic postprocessing of the sampled coefficient vector into a finite space, the total variation distance from applying the same postprocessing to the ideal discrete Gaussian of width on the lattice generated by is at most
The same algorithms work for all bases, accuracies, and postprocessings. They supply the first pool in the iterated Fourier sampler.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_InfoLossLAR_RegevSearch_FourierGrid import Definitions.Def_InfoLossLAR_FirstBridgeBundle_02 set_option autoImplicit false set_option maxHeartbeats 900000
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch
open QAlgorithms.Complexity RegevSketch AFT AFT.RationalNumerics
open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic
open scoped BigOperators Classical
theorem uniform_wide_gaussian_initial_sampler :
∃ (bits : (List (List ℤ) × ℚ) × List Unit → List Unit)
(draw : ((List (List ℤ) × ℚ) × List Unit) × List Bool → List ℤ), Poly bits ∧ Poly draw ∧
∀ {n : ℕ} {O : Type} [Fintype O] (D : Matrix (Fin n) (Fin n) ℤ), D.det≠0 → 1≤n →
∀ (r : ℚ) (a : List Unit) (post : (Fin n→ℤ) → FiniteDist O),
let W : ℚ := max ((n+1:ℕ)*(1+∑ i,∑ j,|(D i j:ℚ)|)) (r*(famσ n:ℚ))
let cfg := ((List.ofFn (fun i=>List.ofFn (fun j=>D i j)), W),a)
let actual := (FiniteDist.uniform (Fin (bits cfg).length → Bool)).mix
(fun tape => post (fun i => (draw (cfg,List.ofFn tape))[i.val]?.getD 0))
∃ ideal : FiniteDist O, (∀ o, ideal.weight o=∑' z,coefficientMass D W z*(post z).weight o) ∧
FiniteDist.TVBound actual ideal
(n*(2/(2:ℝ)^a.length+6*Real.exp (-Real.pi*((a.length:ℝ)+2)^2/2))+
4*((n:ℝ)*(4/(2:ℝ)^(4*(n+1))))) := by sorry
end InfoLossLAR.WorstCase.RegevSearchSource
InfoLossLAR formalization of the wide Gaussian initialization in the coherent shared-pool Fourier sampler. https://prove2.me/theorems/23174e03-6b1d-4113-b6b9-4dab17fa850a