Lemma 12, p. 11 — truncated Fourier integral approximates 1/x
ProvedQuantumLinSys.Fourier.lemma_12fourier-analysisp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-linear-systemsuniform-approximation
Let and . With , there are cutoffs and , with absolute constants in both two-sided bounds, such that the integral of (21) satisfies
The lemma converts the infinite Fourier integral for into one with finite integration limits.
Formalization Note The constants in are chosen before and . The condition-number convention and Corollary 10's range make the domain and logarithmic scales nondegenerate. The displayed supremum is prose for the pointwise bound; Lean states the bound for each .
Preamble
import Mathlib import Definitions.Def_QuantumLinSys_Fourier_Setting
Formal statement
namespace QuantumLinSys.Fourier
/-- Lemma 12, p. 11: a truncated Gaussian Fourier integral approximates 1/x. -/
theorem lemma_12 :
∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∀ κ ε : ℝ,
1 ≤ κ → 0 < ε → ε < 1 / 2 →
∃ yJ zK : ℝ,
c * (κ * Real.sqrt (Real.log (κ / ε))) ≤ yJ ∧
yJ ≤ C * (κ * Real.sqrt (Real.log (κ / ε))) ∧
c * Real.sqrt (Real.log (κ / ε)) ≤ zK ∧
zK ≤ C * Real.sqrt (Real.log (κ / ε)) ∧
∀ x ∈ QuantumLinSys.Chebyshev.Dκ κ, ‖gTrunc yJ zK x - ((1 / x : ℝ) : ℂ)‖ ≤ ε := by sorry
end QuantumLinSys.Fourier
Source
Childs, Kothari and Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, arXiv:1511.02306v2, p. 11, Lemma 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.