Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform Fourier sampling from a shared pool

Definition
InfoLossLAR_RegevSearch_UniformFourierRow

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

latticesprobabilityquantum-computing

This interface specifies a single coherent Fourier readout from a shared pool of integer coefficient vectors. It fixes the finite query amplitudes before the old pool is supplied, records the canonical signed-vector prefix in the output, and bounds the discrepancy on finite events using the preparation error, the decoder failure on the old pool, and the Fourier-grid error. It also specifies how a uniform parser and a polynomial-time table of independent query lengths describe the circuit family.

Definition code
import Definitions.Def_InfoLossLAR_FirstBridgeBundle_02
import Definitions.Def_InfoLossLAR_FirstBridgeBundle_05
import Definitions.Def_InfoLossLAR_FirstBridgeBundle_08
import Definitions.Def_InfoLossLAR_IntegerBasis_Core
import Definitions.Def_InfoLossLAR_LoadedBatchBundle_01
import Definitions.Def_InfoLossLAR_RegevSearch_CoherentCopy
import Definitions.Def_InfoLossLAR_RegevSearch_FourierGrid
import Definitions.Def_InfoLossLAR_RegevSearch_SharedPoolBDD
import Definitions.Def_InfoLossLAR_RegevSketch_DGS
import Definitions.Def_InfoLossLAR_RuntimeBundle_01
import Definitions.Def_InfoLossLAR_RuntimeBundle_03
import Definitions.Def_LARLLL_CurrentData
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime
import Definitions.Def_ShorAlgorithms_QFT_Circuit

set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option maxHeartbeats 1100000

section

open scoped BigOperators Classical ENNReal

open Filter

namespace InfoLossLAR.WorstCase.RegevSearch.GaussianIteration

noncomputable section

variable {X Y : Type*}

def finiteMass (p : PMF X) (T : Finset X) := ∑ x ∈ T, (p x).toReal

end

end InfoLossLAR.WorstCase.RegevSearch.GaussianIteration

end

section

open scoped BigOperators Classical ENNReal

namespace InfoLossLAR.WorstCase.RegevSearch.GaussianIteration

open QAlgorithms.Complexity

noncomputable section

def measuredBits (F : MFamily) (w : Str) : PMF (Bits (w.length+(F.anc w.length+1))) :=
  PMF.ofFintype (fun x => ENNReal.ofReal (Complex.normSq (runLayered (F.circ w.length) (basisInput (toBits w)) x)))
    (by rw [←ENNReal.ofReal_sum_of_nonneg (fun _ _ => Complex.normSq_nonneg _),runLayered_mass,basisInput_mass];simp)

def measuredWord (F : MFamily) (w : Str) : PMF Str :=
  (measuredBits F w).map (fun x => List.ofFn (fun j => x (F.outW w.length j)))

end

end InfoLossLAR.WorstCase.RegevSearch.GaussianIteration

end

section

namespace InfoLossLAR.WorstCase.RationalInverse

open RationalGramSchmidt AFT.RationalNumerics

open scoped BigOperators

noncomputable section

def dualHeight (n H : ℕ) : ℕ := 2*((n+H)*n)

end

end InfoLossLAR.WorstCase.RationalInverse

end

section

namespace InfoLossLAR.WorstCase.RationalGramSchmidt.Native

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open AFT.RationalNumerics

open scoped BigOperators

/-- Unary size reflection materializes the exact actual binary encoding
length; it never enumerates a Gaussian window or a numerical magnitude. -/
def rationalTicks (value : ℚ) : List Unit :=
  List.replicate 7 ()++(value.num.natAbs.bits.flatMap (fun _ => [(),()]))++
    value.den.bits.map (fun _ => ())

end InfoLossLAR.WorstCase.RationalGramSchmidt.Native

end

section

open scoped BigOperators Classical

namespace GridReadout

open InfoLossLAR.WorstCase GaussianPoissonSeries IntegerBasis RegevLWE.GaussConv

open CoherentDecoder FiniteLatticeFourier

noncomputable section

variable {n M : ℕ} [NeZero M]

def gridError (n : ℕ) : ℝ := 4*Real.sqrt (2*(1/2:ℝ)^n)+(1/4:ℝ)^n

end

end GridReadout

end

section

open QAlgorithms.Complexity InfoLossLAR.WorstCase InfoLossLAR.WorstCase.RegevSketch

open InfoLossLAR.WorstCase.RegevSearch RegevLWE.GaussConv

open scoped BigOperators Classical

namespace SharedPoolCoherence

noncomputable section

variable {n : ℕ}

def failureMass {m : ℕ} {I : Type} [Fintype I] (C : MFamily) {B : Matrix (Fin n) (Fin n) ℤ} {R : ℚ}
    (precision : ℕ) (pool : Fin m → Fin n → ℤ) (q : I → Query B R) (a : I → ℂ) : ℝ :=
  ∑ i, ‖a i‖^2 * outputProb C (word precision pool (q i)) (fun out => ¬ encVec encI (q i).answer <+: out)

end

end SharedPoolCoherence

end

section

open scoped BigOperators Classical

namespace InfoLossLAR.WorstCase.RegevSearch.PhysicalFourier

open RegevLWE.GaussConv GaussianPoissonSeries

open GaussianProjection.CosetGeometry

open GaussianProjection GaussianLatticeTransport

noncomputable section

variable {n M : ℕ} [NeZero M]

abbrev PointSpace (n : ℕ) := EuclideanSpace ℝ (Fin n)

abbrev Separated (L : Submodule ℤ (PointSpace n)) (R : ℝ) := ∀ x : L, x ≠ 0 → 2*R ≤ ‖(x : PointSpace n)‖

end

end InfoLossLAR.WorstCase.RegevSearch.PhysicalFourier

end

section

namespace InfoLossLAR.WorstCase.RegevSearch.OracleTable

open QAlgorithms.Complexity Turing

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open Integration9_9 Integration9_9.TM2PlatformSerialization Integration9_9.TM2StockLists QMCNumericRuntime

open Integration9_9.LARPlatformEncoding (readS readBinaryList)

noncomputable section

def unpack (w : Str) := readBinaryList readS w

def lookup (u : Str×ℕ) : Str := (unpack u.1).2[u.2]?.getD []

end

end InfoLossLAR.WorstCase.RegevSearch.OracleTable

end

section

open scoped BigOperators Classical

namespace GridReadout.Axis

open InfoLossLAR.WorstCase QAlgorithms.Complexity FiniteGateTransport

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open Integration9_9 QMCNumericRuntime

noncomputable section

def powTwo (s : Str) : ℕ := bitValue (s.map (fun _ => false) ++ [true])

@[fun_prop] theorem powTwo_poly : Poly powTwo := by unfold powTwo; fun_prop

def signedRow (s : Str) : ℤ :=
  let v := bitValue s.reverse
  if 2*v < powTwo s then -(v:ℤ) else (powTwo s:ℤ)-(v:ℤ)

@[fun_prop] theorem signedRow_poly : Poly signedRow := by
  unfold signedRow
  fun_prop

def rowSlices (x : List Unit × (List Unit × Str)) : List Str :=
  (List.range x.1.length).map (fun i => (x.2.2.drop (i*x.2.1.length)).take x.2.1.length)

@[fun_prop] theorem rowSlices_poly : Poly rowSlices := by
  unfold rowSlices
  apply Poly.list_map
  · change Poly (fun t : (List Unit × (List Unit × Str)) × ℕ => (t.1.2.2.drop (t.2*t.1.2.1.length)).take t.1.2.1.length)
    have hd : Poly (fun t : (List Unit × (List Unit × Str)) × ℕ => t.1.2.2.drop (t.2*t.1.2.1.length)) :=
      Poly.comp (f:=fun s : Str × ℕ => s.1.drop s.2) (g:=fun t : (List Unit × (List Unit × Str)) × ℕ => (t.1.2.2,t.2*t.1.2.1.length)) parser_drop_poly (by fun_prop)
    exact Poly.comp (f:=fun s : Str × ℕ => s.1.take s.2) (g:=fun t : (List Unit × (List Unit × Str)) × ℕ => (t.1.2.2.drop (t.2*t.1.2.1.length),t.1.2.1.length)) parser_take_poly (Poly.pair hd (by fun_prop))
  · exact Poly.comp (f:=fun t : List Unit => List.range t.length) (g:=Prod.fst) Poly.list_indices Poly.fst

def encodeSlices (x : List Unit × (List Unit × Str)) : Str :=
  TM2NativeAffineEmitter.serializeVector ((rowSlices x).map signedRow)

@[fun_prop] theorem encodeSlices_poly : Poly encodeSlices := by unfold encodeSlices; fun_prop

end

end GridReadout.Axis

end

section

open scoped BigOperators Classical

namespace GridReadout

open InfoLossLAR.WorstCase RegevSearch

variable {n : ℕ}

def gridBits (n H K : ℕ) : ℕ := 2 + (2*n + (n+H)*n + 1) + n + (K+1)

end GridReadout

end

section

namespace InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.SignedSlot

open QAlgorithms QAlgorithms.Complexity FiniteGateTransport

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open Integration9_9.TM2PlatformSerialization GridReadout.Axis PhysicalFourier

open TM2Boolean TM2Boolean.PolyProgramCircuit

open scoped Classical BigOperators

noncomputable section

def read (ws : Str) : Str := let r := (readUnary ws).2; encodeSlices (unarySlots ws,unarySlots r,(readUnary r).2)

@[fun_prop] theorem read_poly : Poly read := by
  have hr : Poly (fun ws : Str => (readUnary ws).2) := Poly.comp Poly.snd readUnary_poly
  exact Poly.comp (f:=encodeSlices) (g:=fun ws : Str => (unarySlots ws,unarySlots (readUnary ws).2,(readUnary (readUnary ws).2).2)) encodeSlices_poly (Poly.pair unarySlots_poly (Poly.pair (Poly.comp (f:=unarySlots) (g:=fun ws : Str => (readUnary ws).2) unarySlots_poly hr) (Poly.comp (f:=fun ws : Str => (readUnary ws).2) (g:=fun ws : Str => (readUnary ws).2) hr hr)))

def prefixWord (nt bt : List Unit) := lengthToken nt ++ lengthToken bt

def program := Integration9_9.LARCoinLayout.rawPolyProgram read_poly

end

end InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.SignedSlot

end

section

namespace InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.SignedSlot

open QAlgorithms QAlgorithms.Complexity

open FiniteGateTransport

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open TM2Boolean TM2Boolean.PolyProgramCircuit TM2Boolean.CodeGenerator

open Integration9_9.TM2PlatformSerialization

open scoped Classical BigOperators

noncomputable section

abbrev Sizes := List Unit×List Unit

def digits (s : Sizes) := s.1.flatMap (fun _ => s.2)

def inputTape (s : Sizes) := (prefixWord s.1 s.2).map (fun _ => ())++digits s

def clock (s : Sizes) := (inputTape s).map (fun _ => true)

def slot (s : Sizes) := (request program (clock s)).2.1

end

end InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.SignedSlot

end

section

namespace InfoLossLAR.WorstCase.GaussianPoissonSeries

open RationalInverse

open scoped BigOperators

noncomputable section

/-- This exponent depends only polynomially on the original basis height. -/
def dualColumnBudgetBits (dimension bits : ℕ) : ℕ := dualHeight dimension bits+2*dimension+2

end

end InfoLossLAR.WorstCase.GaussianPoissonSeries

end

section

open scoped Classical BigOperators

namespace InfoLossLAR.WorstCase.RegevSearch.PhysicalGrid

open GaussianPoissonSeries RationalInverse GridReadout

noncomputable section

def bits (n H K d : ℕ) :=
  max (gridBits n H K) (dualColumnBudgetBits n H + (K+1) + (n+2*d+8) + (d+2))

end

end InfoLossLAR.WorstCase.RegevSearch.PhysicalGrid

end

section

open scoped BigOperators Classical

namespace InfoLossLAR.WorstCase.RegevSearch.PhysicalGrid

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic AFT.RationalNumerics

open GaussianPoissonSeries RationalInverse RationalGramSchmidt.Native GridReadout

abbrev Setup := List (List ℤ) × (ℚ × List Unit)

def gridCount (s : Setup) : ℕ :=
  bits s.1.length (integerMatrixTicks s.1).length (rationalTicks s.2.1).length s.2.2.length

def slots (s : Setup) : List Unit :=
  s.1.map (fun _ => ()) ++ integerMatrixTicks s.1 ++ rationalTicks s.2.1 ++ s.2.2 ++ [()]

def capacity (s : Setup) : List Unit :=
  (slots s).flatMap (fun _ => (slots s).flatMap (fun _ => List.replicate 64 ()))

def gridTape (s : Setup) : List Unit := (capacity s).take (gridCount s)

noncomputable def setup {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) (r : ℚ) (d : ℕ) : Setup :=
  (Native.inputRows B,r,List.replicate d ())

end InfoLossLAR.WorstCase.RegevSearch.PhysicalGrid

end

section

open scoped BigOperators Classical

namespace InfoLossLAR.WorstCase.RegevSearch.GaussianIteration

open QAlgorithms.Complexity SharedPoolCoherence CoherentDecoder RegevSketch

noncomputable section

abbrev Vec (n : ℕ) := Fin n→ℤ

abbrev Rows (n m : ℕ) := Fin m→Vec n

end

end InfoLossLAR.WorstCase.RegevSearch.GaussianIteration

end

section

open scoped Classical BigOperators

namespace InfoLossLAR.WorstCase.RectangularSource.Public

open QAlgorithms QAlgorithms.Complexity OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open GaussianRandomizedRounding.Wide GaussianRandomizedRounding.Wide.Coherent

open RegevLWE.GaussConv GaussianPoissonSeries GaussianProjection

open FiniteGateTransport RegevSearch.PhysicalFourier

open RegevSearch.PhysicalGrid

noncomputable section

def physics (r : ℚ) : ℝ :=1/(Real.sqrt 2*(r:ℝ))

end

end InfoLossLAR.WorstCase.RectangularSource.Public

end

section

open scoped BigOperators Classical

namespace InfoLossLAR.WorstCase.RegevSearch.PhysicalFourier

open QAlgorithms QAlgorithms.Complexity FiniteGateTransport

open TM2Boolean.PolyProgramCircuit SharedPoolCoherence GridReadout.Axis

open IntegerBasis RegevLWE.GaussConv GaussianPoissonSeries CoherentDecoder

noncomputable section

abbrev StageL {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) (hB : B.det≠0) := dual (inputLattice B hB)

end

end InfoLossLAR.WorstCase.RegevSearch.PhysicalFourier

end

section

namespace InfoLossLAR.WorstCase.RectangularSource.Cell

open QAlgorithms QAlgorithms.Complexity OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open RegevSearch.PhysicalFourier RegevSearch.PhysicalGrid RegevSearch

open Public

open Integration9_9.TM2NativeAffineEmitter Integration9_9.TM2PlatformSerialization

noncomputable section

abbrev Stage := List (List ℤ) × (ℚ × ℚ) × List Unit × List Unit × List Unit

abbrev Input := (Stage × (List Unit×List Unit)) × (Str×Str)

end

end InfoLossLAR.WorstCase.RectangularSource.Cell

end

section

open scoped BigOperators Classical

namespace InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.SignedSlot

open QAlgorithms QAlgorithms.Complexity

open FiniteGateTransport

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open TM2Boolean GaussianIteration

noncomputable section

def decodeWord (n : ℕ) (w : Str) : Vec n := fun i => (Integration9_9.TM2NativeAffineEncoding.readVector w).2[i.val]?.getD 0

def canon (n S : ℕ) (w : Str) := ∃ z : Vec n,encVec encI z <+: w.take S

end

end InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.SignedSlot

end

section

namespace InfoLossLAR.WorstCase.RectangularSource.Cell

open QAlgorithms QAlgorithms.Complexity OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open RegevSearch.PhysicalFourier RegevSearch.PhysicalGrid RegevSearch

open IntegerBasis

open RectangularSource.Public

noncomputable section

def receipt (P : List (List ℤ)) (R r : ℚ) (copies acc oracle count width : List Unit) (tape advice : Str) : Input :=
  (((P,(R,r),copies,acc,oracle),(count,width)),tape,advice)

end

end InfoLossLAR.WorstCase.RectangularSource.Cell

end

section

open scoped Classical BigOperators

namespace InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.Outer

open QAlgorithms QAlgorithms.Complexity GaussianIteration RegevSketch SharedPoolCoherence

noncomputable section

variable {n : ℕ} {C : MFamily} {P : Polynomial ℕ} {B : Matrix (Fin n) (Fin n) ℤ} {R t : ℚ} {k m : ℕ}

structure AnalysisData (C : MFamily) (P : Polynomial ℕ) (B : Matrix (Fin n) (Fin n) ℤ) (R : ℚ) (k : ℕ) where
  grid : ℕ
  covers : gridAdequate B R (2^grid)
  I : Type
  inst : Fintype I
  inhabited : Nonempty I
  query : I→Query B R
  amp : I→ℂ
  norm : letI := inst;∑ i, ‖amp i‖^2=1
  prep : ℝ
  prep_nonneg : 0≤prep
  L : ℕ
  length_ge : k+1≤L
  source : prep≤2/(L:ℝ)+1/(2:ℝ)^n+2*Real.sqrt ((1/4:ℝ)^n)

def AnalysisData.cost (v : AnalysisData C P B R k) (z : Rows n (P.eval n)) :=
  letI := v.inst
  2*v.prep+4*Real.sqrt (failureMass C (poolBDDPrecision (((P+1)+(P+1)).eval n) k) z v.query v.amp)+
    4*Real.sqrt (2*(1/2:ℝ)^n)+1/(4*((k:ℝ)+1))+GridReadout.gridError n

end

end InfoLossLAR.WorstCase.RegevSearch.AdaptiveStages.Outer

end

section

namespace InfoLossLAR.WorstCase.RegevSearch

open QAlgorithms QAlgorithms.Complexity GaussianIteration RegevSketch AdaptiveStages RectangularSource

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open PhysicalFourier CoherentDecoder RectangularSource.Public

open scoped Classical BigOperators

noncomputable section

/-- The call length can be determined before generating the table of oracle descriptions. -/
def TableIndependent (request : Cell.Input→List Unit) := ∀ (h : Cell.Stage) (slots : List Unit×List Unit) (raw tbl : Str),
  request ((h,slots),raw,tbl)=request ((h,slots),raw,[])

/-- One uniform circuit family, run on a word parsed into a lattice, the parameters of a width
transition, a shared old pool and oracle descriptions. All justified presentations of the
same old row tuple satisfy the same finite-event bound. -/
def FourierRowGuarantee (P : Polynomial ℕ) (C F G : MFamily) (query : Cell.Input→List Unit)
    (parse : Str→Cell.Input) : Prop :=
  ∀ {n : ℕ} (B : Matrix (Fin n) (Fin n) ℤ) (hB : B.det≠0), 0<n → ∀ (R t : ℚ), 0<R → 0<t →
  ∀ c : ℝ, 0<c → (n:ℝ)*(physics t)^2 ≤ c^2 → c ≤ (n+1:ℕ)*(t.den+1:ℕ) →
  c ≤ (famσ n:ℝ)/(2*(R:ℝ)) → Separated (StageL B hB) c →
  ∀ (nt count acc oracle width : List Unit), nt.length=n → count.length=P.eval n →
     oracle.length=poolBDDPrecision (((P+1)+(P+1)).eval n) acc.length →
     (SignedSlot.slot (nt,PhysicalGrid.gridTape (PhysicalGrid.setup B t n))).length ≤ width.length →
  ∃ a : Outer.AnalysisData C P B R acc.length,
    ∀ (raw tbl w : Str) (z : Rows n (P.eval n)),
    let info := Cell.receipt (RationalInverse.Native.inputRows B) R t count acc oracle count width raw tbl
    parse w=info → OracleTable.lookup (tbl,(query info).length)=F.encAt (query info).length →
    (∀ u,encVec encI (z u) <+: (raw.drop (u.val*width.length)).take width.length) →
    outputProb G w (SignedSlot.canon n width.length)=1 ∧
      ∀ T : Finset (Vec n), |finiteMass ((measuredWord G w).map (SignedSlot.decodeWord n)) T-
        ∑ v∈T,coefficientMass B t v| ≤ a.cost z

def UniformFourierRow (C : MFamily) (P : Polynomial ℕ) : Prop :=
  ∃ F : MFamily, IsMQPT F ∧ ∃ query : Cell.Input→List Unit, Poly query ∧ TableIndependent query ∧
  ∀ parse : Str→Cell.Input, Poly parse → ∃ (G : MFamily) (desc : Str→Str), Poly desc ∧
    (∀ j,desc (unary j)=G.encAt j) ∧ FourierRowGuarantee P C F G query parse

end

end InfoLossLAR.WorstCase.RegevSearch

end
Source
InfoLossLAR formalization of the single-coefficient Gaussian reduction, coherent shared-pool Fourier sampling, https://prove2.me/theorems/23174e03-6b1d-4113-b6b9-4dab17fa850a

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