Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation

Yihang Sun, Guanyang Wang, José Blanchet

TL;DR

This paper introduces a new quantum algorithm for estimating Repeatedly Nested Expectations (RNEs)—a mathematical structure central to complex tasks like financial optimal stopping. By developing a novel "derandomized" version of the classical Multilevel Monte Carlo method, the authors achieve a near-quadratic speedup, reaching the theoretical quantum limit of $\tilde{O}(\varepsilon^{-1})$ complexity for an $\varepsilon$-error.

What Problem Does This Paper Address?

Many real-world problems require calculating an expectation of a function that itself contains another expectation. When this happens multiple times, you get Repeatedly Nested Expectations (RNEs). A classic example is the "optimal stopping" problem in finance (e.g., deciding the best time to sell a stock option), which uses the Snell envelope—a recursive chain of expectations.

The challenge is that RNEs are computationally expensive. Classically, the best algorithms (like randomized Multilevel Monte Carlo, or rMLMC) require $O(\varepsilon^{-2})$ samples to achieve an error of $\varepsilon$. While quantum computing is famous for providing a quadratic speedup for simple expectations (turning $\varepsilon^{-2}$ into $\varepsilon^{-1}$), applying this to nested structures is notoriously difficult. Direct "quantization" of classical randomized algorithms often fails because their runtimes are variable, which interferes with the way quantum amplitude amplification works.

Methods

The authors bridge the gap between classical Monte Carlo and quantum acceleration using three main steps:

  1. De-randomization: The core innovation is moving away from the randomized truncation levels used in classical rMLMC. Instead, they develop a version with a deterministic level schedule. This ensures the algorithm's runtime is predictable—a prerequisite for efficient quantum acceleration.
  2. Quantum-Accelerated Monte Carlo (QAMC): They utilize standard quantum mean-estimation subroutines (based on Grover’s algorithm) to estimate the differences between levels in the multilevel scheme.
  3. Recursive Error Control: Because the expectations are nested, errors from the "inner" levels can propagate and blow up the "outer" levels. The authors use a recursive backwards induction proof to show that by carefully choosing truncation points ($B_d$) and sample sizes ($M_d$), they can keep the total Root Mean Squared Error (RMSE) within $\varepsilon$.

Datasets

Not discussed in the paper. As a theoretical work in algorithmic complexity, the paper focuses on proving mathematical bounds rather than benchmarking against specific empirical datasets.

Key Insights and Ideas

  • The Variable-Time Bottleneck: The authors highlight a subtle but critical issue: quantum amplitude amplification (the engine of quantum speedup) loses its efficiency if the subroutine it's amplifying has a random runtime. By derandomizing the classical rMLMC, they "smooth out" the runtime, making it "quantum-ready."
  • Bypassing the "$\delta$ Deficiency": Classical rMLMC algorithms often suffer from a small efficiency loss (represented by an $\varepsilon^{-\delta}$ term). Interestingly, the authors found that the quantum version actually simplifies some of these intricacies, replacing that power-law deficiency with much smaller logarithmic factors.
  • Optimal Scaling: The resulting complexity of $\tilde{O}(\varepsilon^{-1})$ is essentially the "speed limit" for quantum expectation estimation. Since simple mean estimation cannot be done faster than $\varepsilon^{-1}$, this algorithm is theoretically optimal for the nested case as well.

Key Results

  • Quadratic Speedup: The algorithm achieves an $\varepsilon$-error with a cost of $\tilde{O}(\varepsilon^{-1})$, compared to the classical optimal cost of $O(\varepsilon^{-2})$.
  • Complexity Bound: For a constant number of nestings $D$, the sample complexity is bounded by $O(\varepsilon^{-1} \log^{3(D-d)+1}(\varepsilon^{-1}))$.
  • Generalization: Unlike previous quantum methods that only worked for a single nesting (like estimating the value of a single option), this framework handles an arbitrary (but constant) number of nestings, making it applicable to multi-step decision processes.

Limitations and Future Work

  • Constant Horizon ($D$): The current proof assumes the number of nestings ($D$) is a fixed constant. If the number of nestings grows as the error $\varepsilon$ shrinks (a "large horizon" problem), the logarithmic factors in the complexity could grow significantly.
  • Smoothness Requirements: The results rely on the "Last-component Bounded Lipschitz" (LBL) condition. If the functions involved are not sufficiently smooth, the error bounds might not hold.
  • Hardware Realities: This is a high-level algorithmic complexity paper. It does not address the challenges of implementing such an algorithm on current Noisy Intermediate-Scale Quantum (NISQ) hardware, where gate errors and decoherence would be significant factors. Future work could involve optimizing these circuits for near-term devices.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sun2026optimal,
  author = {Yihang Sun and Guanyang Wang and José Blanchet},
  title = {{Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=Yd1jFl0jBt},
}
Figure