Lemma 11, p. 10 — discretized Gaussian Fourier sum is ε-close to 1/x
ProvedQuantumLinSys.Fourier.lemma_11fourier-analysisp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-linear-systemsuniform-approximation
There are positive absolute constants such that, for each condition number and accuracy , one can choose and real mesh widths satisfying two-sided bounds with those constants:
For the finite complex Fourier double sum of (18),
This finite expansion is the scalar approximation used in the paper's Fourier approach to quantum linear systems.
Formalization Note One pair works uniformly for all and all four scales. The condition-number convention and Corollary 10's exclude an empty spectral domain and nonpositive logarithmic scales. The conclusion has exactly , rather than an unspecified multiple of it.
Preamble
import Mathlib import Definitions.Def_QuantumLinSys_Fourier_Setting
Formal statement
namespace QuantumLinSys.Fourier
/-- Lemma 11, p. 10: the finite Fourier double sum (18) approximates 1/x. -/
theorem lemma_11 :
∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∀ κ ε : ℝ,
1 ≤ κ → 0 < ε → ε < 1 / 2 →
∃ (J K : ℕ) (Δy Δz : ℝ),
c * (κ / ε * Real.log (κ / ε)) ≤ (J : ℝ) ∧
(J : ℝ) ≤ C * (κ / ε * Real.log (κ / ε)) ∧
c * (κ * Real.log (κ / ε)) ≤ (K : ℝ) ∧
(K : ℝ) ≤ C * (κ * Real.log (κ / ε)) ∧
c * (ε / Real.sqrt (Real.log (κ / ε))) ≤ Δy ∧
Δy ≤ C * (ε / Real.sqrt (Real.log (κ / ε))) ∧
c * (κ * Real.sqrt (Real.log (κ / ε)))⁻¹ ≤ Δz ∧
Δz ≤ C * (κ * Real.sqrt (Real.log (κ / ε)))⁻¹ ∧
∀ x ∈ QuantumLinSys.Chebyshev.Dκ κ, ‖hDisc J K Δy Δz 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. 10, Lemma 11 and display (18); proof pp. 13–14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.