Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation

We study the estimation of repeatedly nested expectations (RNEs) with a constant horizon (number of nestings) using quantum computing. We propose a quantum algorithm that achieves $\varepsilon$-error with cost $\tilde O(\varepsilon^{-1})$, up to logarithmic factors. Standard lower bounds show this scaling is essentially optimal, yielding an almost quadratic speedup over the best classical algorithm. Our results extend prior quantum speedups for single nested expectations to repeated nesting, and therefore cover a broader range of applications, including optimal stopping. This extension requires a new derandomized variant of the classical randomized Multilevel Monte Carlo (rMLMC) algorithm. Careful de-randomization is key to overcoming a variable-time issue that typically increases quantized versions of classical randomized algorithms.

Many important problems require estimating an average whose value depends on another average, repeated several times. Estimating these repeatedly nested averages appear in areas such as finance, decision-making, and optimal stopping problems, where one must decide the best time to act. This paper shows that quantum computers do this kind of estimation much faster than standard classical methods when the number of nestings is fixed. Our algorithm reaches a desired accuracy using nearly optimal cost, giving an almost quadratic improvement over the best known classical approach. A key part of the result is a new way to derandomize a classical simulation method called Multilevel Monte Carlo so that it works well in the quantum setting. This avoids a common obstacle where directly turning a randomized classical algorithm into a quantum one can lose much of the expected speedup.