Theorem 5, p. 12 — Algorithm 3 has additive error ε with probability at least 2/3
ProvedQuantumMC.MeanEst.theorem_5mean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let have variance at most , where , and let . Algorithm 3 samples from the law of , applies Algorithm 2 to the negative and nonnegative parts of divided by four at accuracy , and combines the estimates. If each Algorithm 2 run fails with probability at most , its output satisfies
The constant in Algorithm 2 may depend only on the universal Algorithm 1 constant ; it is chosen before the output law and accuracy. Formalization Note The theorem assumes to state the variance faithfully. The quantum circuit and the asymptotic resource counts are outside this probability-space statement.
Preamble
import Mathlib import Definitions.Def_QuantumMC_MeanEst_Setting
Formal statement
namespace QuantumMC.MeanEst
open MeasureTheory ProbabilityTheory
universe u v
/-- Theorem 5, p. 12: Algorithm 3 has additive error ϵ with probability at least 2/3. -/
theorem theorem_5 (C : ℝ) (hC : 0 < C) : ∃ D : ℝ, 0 < D ∧
∀ (Ω₀ : Type u) [MeasurableSpace Ω₀] (P₀ : Measure Ω₀) [IsProbabilityMeasure P₀]
(X : Ω₀ → ℝ) (σ ε : ℝ), Measurable X → MemLp X 2 P₀ →
variance X P₀ ≤ σ ^ 2 → 0 < σ → 0 < ε → ε < 4 * σ →
∀ (Ω : Type v) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(m : Ω → ℝ) (μneg μpos : Ω → ℕ → ℝ),
Measurable m → P.map m = P₀.map (fun x => X x / σ) →
P {ω | ¬ Alg2Succeeds C D (ε / (32 * σ)) P₀
(alg3NegQuarter σ (m ω) X) (μneg ω)} ≤ (1 / 9 : ENNReal) →
P {ω | ¬ Alg2Succeeds C D (ε / (32 * σ)) P₀
(alg3PosQuarter σ (m ω) X) (μpos ω)} ≤ (1 / 9 : ENNReal) →
(2 / 3 : ENNReal) ≤ P {ω |
|alg3Output σ (m ω) (alg2K (ε / (32 * σ)))
(μneg ω) (μpos ω) - ∫ x, X x ∂P₀| ≤ ε} := by sorry
end QuantumMC.MeanEst
Source
Montanaro, Quantum speedup of Monte Carlo methods, arXiv:1504.06987v3, Theorem 5 and Algorithm 3, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.