Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One coefficient Gaussian sample from bounded-distance decoding with a shared pool

Proved
InfoLossLAR.WorstCase.RegevSearch.shared_pool_bdd_to_gaussian_events

by BoomShaKaLaaaKa · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

lar-regev-bridgelatticesquantum-computing

Fix an infinite set SSS of positive dimensions and a uniform quantum decoder equipped with CoherentPoolBDDBudget on SSS. Construct a single uniform circuit family HHH and a negligible eee. For every sufficiently large n∈Sn\in Sn∈S, nonsingular integer basis BBB, positive rational rrr at least dgsThreshold B, and unary accuracy kkk, run HHH 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 T⊂ZnT\subset\mathbb Z^nT⊂Zn, the probability of a prefix encoding a member of TTT differs from the ideal Gaussian coefficient mass of TTT by at most (e(n)+1/(k+1))/2(e(n)+1/(k+1))/2(e(n)+1/(k+1))/2.

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.

Preamble
import Definitions.Def_InfoLossLAR_RegevSearch_SharedPoolBDD

set_option autoImplicit false
open QAlgorithms.Complexity InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch
open scoped BigOperators Classical
Formal statement
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
Source
Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, https://cims.nyu.edu/~regev/papers/qcrypto.pdf, Theorem 3.1, Lemma 3.3 and §3.2.2, Lemma 3.14. These motivate iteration and the quantum conversion from dual decoding to Gaussian sampling. The shared-pool error analysis, exact prefix validity, coefficient readout, arbitrary promised rational widths and the stated finite-event accuracy are additional formalization obligations.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me