Quantum speedup of non-linear Monte Carlo problems

Jose Blanchet (Stanford University) · Guanyang Wang (Rutgers University) · Yassine Hamoudi (Université de Bordeaux, CNRS, LaBRI) · Mario Szegedy (Rutgers University)

linear functionallower bound mean estimationmultilevel monte carlomultilevel monte carlo approximationsnested expectationsnon-linear functionalsoptimality performance improvement polylogarithmic factors probability distributionsquadratic speedupquantum algorithms quantum computingquantum-acceleratedquantum-inside-quantum algorithm

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 \textit{quantum-inside-quantum} algorithm that achieves this speedup for the broad class of nonlinear estimation problems known as nested expectations. Our algorithm improves upon the direct application of the quantum-accelerated multilevel Monte Carlo algorithm introduced by An et. al.. The existing lower bound indicates that our algorithm is optimal up to 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.