# Quantum speedup of non-linear Monte Carlo problems

arXiv: https://arxiv.org/abs/2502.05094 · HTML: https://mlsanity.com/paper/2502.05094/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 38 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 11 of 11)

- [On Nesting Monte Carlo Estimators](https://mlsanity.com/paper/1709.06181/) (2017)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [Quantum Chebyshev's Inequality and Applications](https://mlsanity.com/paper/1807.06456/) (2018)
- [Mean estimation when you have the source code; or, quantum Monte Carlo methods](https://mlsanity.com/paper/2208.07544/) (2022)
- [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023)
- [Optimal randomized multilevel Monte Carlo for repeatedly nested expectations](https://mlsanity.com/paper/2301.04095/) (2023)

## Abstract (arXiv)

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.