15.3 Monte Carlo speedup
Leveraging on the speedup provided by the QPE, Montanaro [231] devised a Monte Carlo scheme providing quantum speedup compared to the classical one.
15.3.1 Classical Monte Carlo
Monte Carlo techniques represent a wide array of methods to simulate statistics of random processes. We refer the interested reader to the excellent monograph [115] for a full description and analysis. Consider a one-dimensional random variable X and a function ϕ : ℝ →[0,1] such that both 𝔭 := 𝔼[ϕ(X)] and σ2 := 𝕍[ϕ(X)] are well defined. By the Central Limit Theorem, given an iid collection of random variables (X1,…,XN) distributed as X, then
converges to a centered Gaussian with unit variance N(0,1) as N tends to infinity, where
is the empirical mean. This implies that, for any 𝜀 > 0, we can estimate
so that, for any z > 0 and δ ∈ (0,1), in order to get an...
