Paper: arXiv 2602.08120

Authors: Yihang Sun, Guanyang Wang, Jose Blanchet

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.

Complexity vs Empirical Score

  • Math Complexity: 9.0/10
  • Empirical Rigor: 1.5/10
  • Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper presents rigorous mathematical proofs establishing optimal quantum speedups for repeatedly nested expectation estimation, a core problem in derivative pricing and optimal stopping. While technically sophisticated and highly novel, it is entirely theoretical with no empirical backtests, empirical datasets, or implementation code provided.

Research Flowchart

  flowchart TD
    A["Research Goal: Optimal Quantum Speedup<br>for Repeatedly Nested Expectations (RNE)"] --> B["Input: RNE Problems<br>(e.g., Optimal Stopping, Option Pricing)"]
    B --> C["Core Method: Derandomize Classical<br>Randomized Multilevel Monte Carlo (rMLMC)"]
    C --> D["Process: Apply Quantum Phase Estimation &<br>Amplitude Estimation (Avoids Variable-Time Issue)"]
    D --> E["Outcome: Near-Optimal Cost Õ(ε⁻¹)<br>Quadratic Speedup over Classical O(ε⁻²)"]

Cited References (20)

  1. Optimal randomized multilevel Monte Carlo for repeatedly nested expectations — → 2301.04095
  2. Quantum speedup of non-linear M onte C arlo problems (2026)
  3. Quadratic Speed-up in Infinite Variance Quantum Monte Carlo (2024) — link
  4. Mean estimation when you have the source code; or, quantum Monte Carlo methods (2023)
  5. Unbiased optimal stopping via the MUSE (2023)
  6. Reflected solutions of backward SDE’s, and related obstacle problems for PDE’s (1997)
  7. A brief review of the Deep BSDE method for solving high-dimensional partial differential equations (2025) — link
  8. Quantum speedups for stochastic optimization (2023)
and 12 more
  1. On Nesting M onte C arlo Estimators (2018) — link
  2. Unbiased estimation with square root convergence for SDE models (2015)
  3. Variable time amplitude amplification and quantum algorithms for linear algebra problems (2012)
  4. Inequalities for the rth absolute moment of a sum of random variables (1965)
  5. Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance (2021)
  6. Quantum speedup of Monte Carlo methods (2015)
  7. A fast quantum mechanical algorithm for database search (1996)
  8. Quantum Algorithm for Stochastic Optimal Stopping Problems with Applications in Finance (2022)
  9. Logical reversibility of computation (1973)
  10. Valuing American options by simulation: A simple least-squares approach (2001)
  11. The quantum query complexity of approximating the median and related statistics (1999)
  12. Quantum Sub-Gaussian Mean Estimator (2021) — link

1 of 20 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.