Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for μ = E[y] that with high probability satisfies , where σ = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse . Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.07544
Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for μ = E[y] that with high probability satisfies , where σ = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse . Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.07544
In this study, we give an extension of Montanaro's arXiv/archive:1504.06987 quantum Monte Carlo method, tailored for computing expected values of random variables that exhibit infinite variance. This addresses a challenge in analyzing heavy-tailed distributions, which are commonly encountered in various scientific and engineering fields. Our quantum algorithm efficiently estimates means for variables with a finite (1+δ)th moment, where δ lies between 0 and 1. It provides a quadratic speedup over the classical Monte Carlo method in both the accuracy parameter ε and the specified moment of the distribution. We establish both classical and quantum lower bounds, showcasing the near-optimal efficiency of our algorithm among quantum methods. Our work focuses not on creating new algorithms, but on analyzing the execution of existing algorithms with available additional information about the random variable. Additionally, we categorize these scenarios and demonstrate a hierarchy in the types of supplementary information that can be provided.
We present a new quantum algorithm for estimating the mean of a real-valued random variable obtained as the output of a quantum computation. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples needed to estimate the mean of a heavy-tailed distribution with a sub-Gaussian error rate. This result subsumes (up to logarithmic factors) earlier works on the mean estimation problem that were not optimal for heavy-tailed distributions [BHMT02,BDGT11], or that require prior information on the variance [Hein02,Mon15,HM19]. As an application, we obtain new quantum algorithms for the (ϵ,δ)-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.
We present a new quantum algorithm for estimating the mean of a real-valued random variable obtained as the output of a quantum computation. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples needed to estimate the mean of a heavy-tailed distribution with a sub-Gaussian error rate. This result subsumes (up to logarithmic factors) earlier works on the mean estimation problem that were not optimal for heavy-tailed distributions [Brassard et al., 2002; Brassard et al., 2011], or that require prior information on the variance [Heinrich, 2002; Montanaro, 2015; Hamoudi and Magniez, 2019]. As an application, we obtain new quantum algorithms for the (ε,δ)-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
The mean of a random variable can be understood as a linear functional on the space of probability distributions. Quantum computing is known to provide a quadratic speedup over classical Monte Carlo methods for mean estimation. In this paper, we investigate whether a similar quadratic speedup is achievable for estimating non-linear functionals of probability distributions. We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems, including nested conditional expectations and stochastic optimization. Our algorithm improves upon the direct application of the quantum multilevel Monte Carlo algorithm introduced by An et al. (2021). The existing lower bound indicates that our algorithm is optimal up polylogarithmic factors. A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.
In this work, we present an efficient algorithm for multivariate mean value estimation. Our algorithm outperforms previous work by polylog factors and nearly saturates the known lower bound. More formally, given a random vector X of dimension d, we find an algorithm that uses O(nlogδd) samples to find a mean estimate that μ~ that differs from the true mean μ by ntr Σ in ℓ∞ norm and hence nd tr Σ in ℓ2 norm, where Σ is the covariance matrix of the components of the random vector. We also presented another algorithm that uses smaller memory but costs an extra d41 in complexity. Consider the Grover operator, the unitary operator used in Grover's algorithm. It contains an oracle that uses a ±1 phase for each candidate for the search space. Previous work has demonstrated that when we substitute the oracle in Grover operator with generic phases, it ended up being a good mean value estimator in some mathematical notion. We used this idea to build our algorithm. Our result remains not exactly optimal due to a logδd term in our complexity, as opposed to something nicer such as logδ1; This comes from the phase estimation primitive in our algorithm. So far, this primitive is the only major known method to tackle the problem, and moving beyond this idea seems hard. Our results demonstrates that the methodology with generalized Grover operator can be used develop the optimal algorithm without polylog overhead for different tasks relating to mean value estimation.