§2.3, proof of Theorem 5 — recombination identity
ProvedQuantumMC.MeanEst.theorem_5_recombinationmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
For an integrable output , positive , any real , and , let and retain on the indicated half-lines and output zero elsewhere. Then
This is the expectation identity behind Algorithm 3's final combination.
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: recombination of the negative and positive parts. -/
theorem theorem_5_recombination {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hX : Integrable X P)
(σ m : ℝ) (hσ : 0 < σ) :
(∫ ω, X ω ∂P) = σ *
(m - (∫ ω, -(truncLt 0 (alg3B σ m X) ω) ∂P) +
(∫ ω, truncGe 0 (alg3B σ m X) ω ∂P)) := 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.