§2.3, proof of Theorem 5 — centered norm bound
ProvedQuantumMC.MeanEst.theorem_5_l2_boundmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let have variance at most with . If the sampled value obeys , then the centered output satisfies
This is the bounded-norm condition used when Algorithm 2 is applied to the two parts of .
Preamble
import Mathlib import Definitions.Def_QuantumMC_MeanEst_Setting
Formal statement
namespace QuantumMC.MeanEst
open MeasureTheory ProbabilityTheory
/-- §2.3, proof of Theorem 5, p. 12: the centered output has L² norm at most four. -/
theorem theorem_5_l2_bound {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hXm : Measurable X)
(hX : MemLp X 2 P) (σ : ℝ) (hvar : variance X P ≤ σ ^ 2)
(hσ : 0 < σ) (m : ℝ) (hm : |m - ∫ x, X x / σ ∂P| ≤ 3) :
l2norm P (alg3B σ m X) ≤ 4 := by sorry
end QuantumMC.MeanEst
Source
Montanaro, Quantum speedup of Monte Carlo methods, arXiv:1504.06987v3, §2.3, proof of Theorem 5, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.