Quantum speedup of non-linear Monte Carlo problems
Jose Blanchet, Yassine Hamoudi, Mario Szegedy, Guanyang Wang
Abstract
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.
BibTeX
@inproceedings{
blanchet2025quantum,
title={Quantum speedup of non-linear Monte Carlo problems},
author={Jose Blanchet and Yassine Hamoudi and Mario Szegedy and Guanyang Wang},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=IkfBLlYuHA}
}