§2.2, proof of Lemma 4 — dyadic Cauchy–Schwarz bound
ProvedQuantumMC.MeanEst.lemma_4_cauchy_schwarzmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
For a nonnegative output , write . For every natural , both steps of the displayed bound hold:
This is the sum bound used in Lemma 4. Formalization Note is written as .
Preamble
import Mathlib import Definitions.Def_QuantumMC_MeanEst_Setting
Formal statement
namespace QuantumMC.MeanEst
open MeasureTheory ProbabilityTheory
/-- §2.2, proof of Lemma 4, p. 11: both inequalities in the Cauchy–Schwarz display. -/
theorem lemma_4_cauchy_schwarz {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hX : MemLp X 2 P)
(hpos : ∀ ω, 0 ≤ X ω) (k : ℕ) :
(∑ ℓ ∈ Finset.Icc 1 k,
Real.sqrt ((2 : ℝ) ^ ℓ) *
Real.sqrt (∫ ω, truncIco ((2 : ℝ) ^ (ℓ - 1)) ((2 : ℝ) ^ ℓ) X ω ∂P)) ≤
Real.sqrt (k : ℝ) *
Real.sqrt (∑ ℓ ∈ Finset.Icc 1 k, (2 : ℝ) ^ ℓ *
(∫ ω, truncIco ((2 : ℝ) ^ (ℓ - 1)) ((2 : ℝ) ^ ℓ) X ω ∂P)) ∧
Real.sqrt (k : ℝ) *
Real.sqrt (∑ ℓ ∈ Finset.Icc 1 k, (2 : ℝ) ^ ℓ *
(∫ ω, truncIco ((2 : ℝ) ^ (ℓ - 1)) ((2 : ℝ) ^ ℓ) X ω ∂P)) ≤
Real.sqrt (2 * (k : ℝ)) * l2norm P X := by sorry
end QuantumMC.MeanEst
Source
Montanaro, Quantum speedup of Monte Carlo methods, arXiv:1504.06987v3, §2.2, proof of Lemma 4, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.