Quantum speedup of non-linear Monte Carlo problems
Authors: Jose Blanchet
Yassine Hamoudi
Mario Szegedy
Guanyang Wang
Venue: NeurIPS 2025 spotlight ()
Keywords: quantum computing
Monte Carlo
multilevel Monte Carlo
nested expectation
Primary area: probabilistic_methods
TL;DR: A near-optimal quantum-accelerated Monte Carlo estimator for nested expectations

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.

Quantum speedup of non-linear Monte Carlo problems
Jose Blanchet
Yassine Hamoudi
Stanford University
Université de Bordeaux, CNRS, LaBRI ys hamoudi
jose. blanchet@stanfort ord. edu
Aammoud@@gmall.. @gmail com
Mario Szegedy
Guanyang Wang
Rutgers University szegedy6cs.. rrggedyycsrrutgers.coo
Rutgers University
guanyang wangerutgers.ed.
Abstract
The mean of random variable be understood linear functional on the space of probability distributions. Quantum computing is known to provide 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 quantum-instee 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 aaantum-accelerated multilevel Monte Carlo algorithm introduced by An et al. (2021). The existing lower bound indicates that our algorithm is optimal up to polylogarithmic factors. A key innovation of our approach a new sequence multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.
1 Introduction
From classic problems like Buffon's needle (Ramaley 1969) to modern Bayesian computations (Martin et al. 2023), Monte Carlo methods have proven to be powerful tools for estimating the expected value of given function. Specifically, the classical Monte Carlo method involves estimating fx) dx)(x) by sampling. where the samples are drawn from IP. Assuming f has finite variance, the number of independent and identically distributed (i.id.) samples required to produce an estimate of [ with additive error of and given degree (say 95%) of confidence In the quantum computing setting, using a Grover-type algorithm, it is known (Heinrichl 2002 Montanaro| 2015 Hamoudi and Magniez] 2019 Hamoudi] 2021 Kothari and O' Donnell 2023
[x[f(X)]
is ((1/e2) [1
that a -aaanuum-ccceerateed version of the Monte Carlo technique achieves a quadratic speedup, resulting in cost of O(1/c) for the same task. For broader links between quantum algorithms and classical stochastic simulation, see Blanchet et al. (2025).
A typical expectation E5 [X) functions as linear functional on the space of distributions, map- ping one distribution IP to corresponding expected value. However, many important quantities cannot be written such linear functionals. For instance, the standard deviation maps distribu- tion PP to sd(P) E X (Ep [ This mapping is nonlinear because the expectations are subsequently transformed by quadratic and square-root operations.
'Troougoou this paper, we use fn) = Og((n) to mean f(n) & MM(nn) for all n and some constant M. We write (n) (gg(n) ignore polylogarithmic factors, meaning f((m) = (g((n) log* g(n)) for some
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This work addresses settings where the target quantity is non-linear functional of IP. Our goal to estimate the nested expectation introduced the next section. Our main contribution qucantum-insdee iinsidd-quanuuun algorithm that achieves a near-optimal cost of O(1/e).
1.1 Nested expectation
We now establish the notation that will be used throughout the rest of the paper. Let IP denote a probability distribution on X' x V. Define a function é X y + R and another function
X' R IR. Let (X.Y) X' x y be pair of random variables with joint distribution IP. Our paper addresses the estimation of the nested expectation, which takes the form:
Ex (xx, xx [Ø(X, Y))]
(I)
Equation (1) defines a non-linear function of IP. with the non-linearity arising from the non-linear nature of g. If we set (xx) == (0(r Y)] and (xx) == g(x, r(z)), the expression (1 can be written more simply as [[}(X)]. However, it is more challenging than the standard mean estimation problem as A(x) further depends
conditional expectation 7xx) that needs to be estimated.
Consequently, a standard Monte Carlo method-wirh depends on computing À exactly is not
directly applicable in this context.
The phrase "nested expectation". referring to an expectation taken inside another expectation, was formally introduced and defined by |Rainforth et al. (2018). It also represents the simplest nontrivial case of "repeated nested expectation" " (Zhou et al. 2023 Syed and Wang 2023 Haji-Ali and Spence
2023 Some concrete applications are as follows:
In Bayesian experiment design (Lindley 1956 Hironaka and Goda 2023). the expected information loss of the random variable is Ex log (E [Pr[X] YI). Ey y [Pr(( YDJ. Here, a nested expectation appears in the first term. In typical scenarios, the conditional probability Pr[X Y] has a closed-form expression, making easy to evaluate, unlike Pr[X].
Given fi..... fa which can be understood as treatments, the expected value of partial perfect information (EVPPI) (Giles and Goda 2019), is Ex [max [f (X, Y)Il - max; fi (X, Y)), which captures the beneft of knowing X. Here, a nested expectation appears also in the first term.
In financial engineering, financial derivatives are typically evaluated using expectations and, therefore, Monte Carlo methods are often the method of choice in practice. One of the most popular derivatives is the so-called call option, whose value (in simplified form) can be evaluated as
E [max(Y 0) X].
Here, & is the strike price, Y is the price of the underlying asset future date, and X represents the available information on the underlying. For instance, the value a Call on a Call (CoC) option (a call in which the underlying is also a call option with the same strike price) is
Ex [max Mmax(Eyyxx [Ey]x [max(Y - k; 0) X] k. 0)]-
The objective function in conditional stochastic optimization (CSO) (Hu et al. 2020 He and Kasiviswanathan 2024) is formulated as a nested expectation, i.e.,
min F(x) = min (1.,
Numerous methods are available for estimating nested expectations. The most natural way is by nesting Monte Carlo estimators. This method works by first sampling i.i.d. ....... X,m For each X,, one further samples Yr,,, Yi.,.... Yt.. i.i.d. from Pr(Y X2]. Then (Xx)) can be estimated by 7(x)) Σj= Φ(X,, Yzz)/n, n, and the final estimator of the form
Σ ((x,,,(()) g(x,
y (X Yos)/n)
m
m
Under different smoothness assumptions on y. this nested estimator costs nm 0 to O(1/e4) samples to achieve mean square error (MSE) of up e2 (Hong and Juneja 2009 Rainforth et al. 2018). The Multilevel Monte Carlo (MLMC) technique further improves efficiency to O or
O é) log(L/))?), as outlined in Section 9.1 of Giles 2015) and Blanchet and Glynn 2015

---

If users have access to quantum computer, An et al. (202)) proposed a QA-MLMC algorithm that improves upon the classical MLMC algorithm. The improvement ranges from quadratic to sub-quadratic-or or can even be nonexistent-depeeeee detailed in Sections 2.1 2.2
on the parameters of the MLMC framework,
Under the standard Lipschitz assumptions, directly applying the QA-MLMC of An et al. 2021 to our non-linear nested expectation problem incurs a cost of (1/²²). This represents no improvement over the classical cost! technical analysis explaining the loss of the quadratic speed-up provided in Section 3.1
1.2 Our contribution
Our main algorithmic contribution of this paper is a crrantum-insid-quuee estimate nested expectations. Under standard technical assumptions, the algorithm achieves cost of ((1/e) to produce an estimator with e-accuracy, which is proven to be optimal among all quantum algorithms up to logarithmic factors. As such, our algorithm provides quadratic speedup compared to the classical MLMC algorithm, making it more efficient than the direct adaptation of the quantum algorithm proposed in An et al. (2021). The comparison between our algorithm and existing methods
MLMC algorithm to
summarized in Table
Table 1: Cost of estimating with c-accuracy using different methods.
We provide brief ex- planation of the basis of our improvement and the term "quantum-inside- quantum", with more comprehensive explana- tions to follow in later sections. For given target
Method
Cost
Nested estimator (Eq. (2 Rainforth et al. (2018)
O(c
Classical MLMC (Thm 2.1 Giles (2015)
QA-MLMC (Thm 2.2
An et al. 2021
Q-NESTEXPECT (Ours)
Ō(c-1)
quantity and an error budget e, every classical MLMC algorithm consists of two components: (1) decomposing the estimation problem into the task of separately estimating the expectations of different parts; and (2) distributing the total error budget among these parts to minimize the overall computational cost, followed by using (classical) Monte Carlo to estimate each expectation. The QA-MLMC algorithm (An et al. 202 1) replaces step (2) with quantum- accelerated Monte Carlo methods. However, observed that there multiple ways to perform the decomposition in step (1). Notably, the most natural decomposition for classical MLMC is not optimal for quantum algorithms in our nested expectation problem. To address this, we developed new decomposition strategy based on a different sequence of quantum quantum-accellrated Monte Carlo subroutines, ultimately achieving the desired quadratic speedup. Thus, the "outside quantum" refers the quantum -acellrmaccelerated Monte Carlo algorithm in Step (2). while the "inside quantum" denotes the quantum subroutines used in Step (1).
Besides addressing the nested expectation problem, we show that quantum computing introduces new flexibility to MLMC. By redesigning the MLMC subroutines to leverage quantum algorithms, additional gains can be achieved. As MLMC is widely applied in computational finance, uncertainty quantification, and engineering simulations, we believe that our strategy can also improve algorithmic efficiency in many of these applications.
Finally, stress that quantum-acceleratee accelerated Monte Carlo method uses quantum-compuite algorithms to speed up the estimation of classical stochastic problems; it should not be conflated with Quantum Monte Carlo (QMC) methods, which are separate class of classical algorithms developed for simulating quantum many-body systems (see, for example, Foulkes et al. (200))
The remainder of the paper is organized as follows. Section rreview the fundamentals of MLMC and QA-MLMC. Section 3 Juulines the limitations of existing methods, motivates our approach, and presents the new algorithm together with proof sketch. Section shows how our method accelerates several practical problems that involve nested expectations. Section summarizes the work, notes its limitations, and suggests directions for future research. Detailed proofs are provided in the Appendix.
3

---

2 Multilevel Monte Carlo
2.1 Classical MLMC
MLMC methods are designed to estimate specific statistics of a target distribution, such as the expectation of a function of Stochastic Differential Equation (SDE) (Giles) 2008), a function of an expectation (Blanchet and Glynn 2015), or solutions to stochastic optimization problems, quantiles, and steady-state expectations (Blanchet al. 2019). Users typically have access sequence of approximations, with each successive level offering reduced variance but increased computational cost. The following theorem provides theoretical guarantees for classical MLMC.
Theorem 2.1 (Theorem in Giles (2015). Let denote quantity that we want to estimate. Suppose for each integer 2 0, we have an algorithm Ai that outputs a random variable D with
variance Vi and computational cost C. Define st := Σ -k= E| [R] and assume for some (a,3, (373. with a 2 1/ max } that the following holds: (i) |st μl S O(2-al); (ii) Vi S 0(2 (iii) Ci S (2 Then any fixed e < 1/e, one can choose positive integers L, No...., Nr, depending
on (a, 8),), and construct the estimator = -t N., Ei A satisfying E[ n² e² with cost:
1(cc 3)
when 3 ?
Ea-M-
OlE (logg)) O 0(6-2-(9-9)/a)) (-/1)))/a),
when ?
when 71
here A A are i.i.d. copies of Du for each
The MLMC estimator described in Theorem 2.1 can be rewritten as Ā = Et= 8. with each
: 4 /Nr acting as a Monte Carlo estimator for [[[A)..
The design and analysis of the sequence At are central to apply Theorem 2.1 in every MLMC application. In the nested expectation problem, follow Section 9.1 of Giles (2015) and provide
possible MLMC solution here. We define An as: 1) simulate X; 2) simulate given X; 3) output o()) When / 2 1, A is defined in Algorithm
Under Assumptions 1-4 given in Section 3 one can
Algorithm 1 Classical MLMC for nested expectation: A (1 1)
check that the sequence
1: Generate X.
of algorithms A satisfies
2: Generate Yi.... Yg conditional on X.
a = 0.5, 3 = 7 in The- orem 2.1 with proof given in Appendix B Therefore
3: Set So = Eiols o(X, Y.), S. = Eieren o(X, Y;).
4: Output: g(X,2 2X,,2-(Ss + S.)) o(X,2 -11)) (1- (1-)))) (Se
2
Theorem 2.1 applies and one can estimate the nested expectation with cost O ((e=e(loge)))
2.2 Quantum-accelerater MLMC in An et al. (021)
In An et al. (001)), the authors propose quantum- acceleercceeeeerteed MLMC (QA-MLMC) algorithm that improves upon the classical MLMC from Theorem 2.1 in certain parameter regimes. The key insight is as follows: recall that 8, := EA
/N, is a classical Monte Carlo estimator for E[Ar]. meaning i= A estimates EE [[] through i...d. sampling and then takes the average. This process can be accelerated Monte Carlo (QA-MC) techniques, such as those discussed in
by applying
Montanaro (2015). By replacing the classical Monte Carlo estimator & with its quantum counterpart, the following result shown:
Theorem 2.2 (Theorem 2 in An al. 202 (02I)) ). With the same assumptions as in Theorem 2.1 there is a quantum algorithm that estimates up to additive error e with probability at least ö, and with cost
C log(6-1)),
when / > 27
Ō -17--11- log(6 when B < 2yy
Comparing QA-MLMC (Theorem 2.2 with classical MLMC (Theorem 2.1 shows only a quadratic speed-up-up to polylogarithmic factors-wher 3 > 2y. In typical scenario where 3 1

---

and a 2 0.5, classical MLMC costs O whereas QA-MLMC costs Ö(e-1-0.//), In particular, QA-MLMC has cost O for the nested expectation problem, using the sequence of algorithms A defined in Algorithm |
(where a = 0.5). The loss of any quantum speedup prompts consideration of be improved. In general, the answer is no, as we show in Appendix CCta the QA-MLMC algorithm An et al. (2021) obeys the following lower bound.
whether the algorithm
Proposition 2.3 (Lower bound for the general QA-MLMC), For any (ax, B,7), there is no quantum algorithm that can solve the problem stated in Theorem 2.7 for all sequences of algorithms {Ar]120 using fewer operations than !)( (when B 2 27) ? (111-111008)) (when B s 27y)
The rest of the paper is dedicated to showing that the nested expectation problem does not suffer from this lower bound, by presenting faster quantum algorithm with cost Ö(e but tailored to this problem.
3 Main Algorithm
The nested expectation Ex (x(, By ((XX))))) depends g and Φ. We define: Definition 3.1. A function X x R + R is uniformly K K-LLppscitzz in the second component if there exists positive real number K such that for all x X and 12 E IR
1g( g(x, S K|yn 3/2/-
We pose five assumptions:
1. The function g is uniformly K K-Lipschitz in its second component.
2. There is number V known to the users satisfying fy]== Y) S V for every X.
3. There is a number S known to the users satisfying Varx [g Ey xx (Ø(X, Y)I] S.
4. We assume that users query both @ and and that each query incurs unit cost.
5. We have access to the following two randomized classical algorithms Genx and Geny, and every call of either one incurs a unit cost:
(a) Genx outputs samples from the distribution of X without requiring any input.
(b) Geny (x) accepts an input z from X' and generates sample of Y based on the conditional distribution Pr[Y X = z².
We briefly review the five assumptions. The first assumption is critical for achieving the Ō(1/c) upper bound in Theorem 3.2 This assumption holds in many practical problems of interest, particularly for functions like g y) := max(æ; x y or x + y. The second and third assumptions are technical conditions to ensure the variance and conditional second moment are well-behaved. For example, the second assumption is satisfied when (X, Y) follows a regression model Y = f(X) + Noise where noise has zero mean and variance more than V. and (z, y) is taken y- fxx) The fourth assumption is commonplace and is consistently invoked- either explicitly or implicitly
related
works (Giles and Goda 2019 Rainforth et al. 2018 Syed and Wang 2023).
The final assumption requires that users have complete access to the sampling procedure itself-for instance, a Python script or pseudocode that produces the distribution- rather than relying on black-box or API that only delivers samples. This assumption is common the simulation literature, and holds in all applications we are aware of. Under Assumption 5, if we are given randomized algorithm that generates a random variable X, we can convert it into a reversible algorithm (with constant factor overhead for the time complexity) and then implement it as quantum circuit z]|x>) garbage,,) using classical Toffoli and NOT gates (Bennett 1973).
U 10) En /Pr[X V Here, ggarbage,)) denotes a work tape that stores the intermediate states of the sampling procedure, ensuring that the process remains reversible.
We show:
Theorem 3.2. With assumptions 1-5 stated above, for any 8 (0, 0.5), we can design an algorithm Q-NESTEXPECT with cost (VVV WosS//VV/////// (og(1/8)/e that estimates RXgg(X E[o(X, Y))) with an absolute error of more than and success probability of 1 8.
5

---

We highlight that the standard enror metrics differ slightly between classical and quantum algorithms. Classical algorithms are often evaluated based on their expected error or mean-squared error, whereas quantum algorithms typically ensure that the error is small with high probability. The former metric slightly stronger than the latter; however, under mild additional conditions, the two error measures become equivalent. Appendix A of An et al. (202T) has a detailed comparison between the two types of errors, Our error metric aligns with nearly all quantum algorithmss, such as Brassard et al. (2002); Montanaro (2015); Kothari and O' O'Donnell 2023); (Sifford and Zhang (2023).
3.1 Roadmap
Why the quadratic speedup is lost?
simple yet important observation is that aactulerreceeeeeeee Monte Carlo methods typically offer quadratic improvement in sample complexity compared to classical Monte Carlo methods. However, this improvement does not automatically translate to quadratic reduction in computational cost. This distinction arises because the computational cost depends not only on the sample complexity but also on the cost of executing the underlying algorithm.
Suppose the goal is to estimate the expectation of randomized algorithm A. and the cost of single execution of A is C(A). The computational cost of classical Monte Carlo requires ((a²/e²) samples, where x² represents the variance of A, and denotes the desired error tolerance. Consequently, the total computational cost becomes O(C(A)a2/e") In contrast, the QA-MC algorithm described in Kothari and O' Donnell 2 (Theorem 3.5 reduces the sample requirement to O( /e). This results in a computational cost of (C(())r//c). This implies that QA-MC achieves a nearly quadratic speedup in computational cost only if the cost of rumning the algorithm A is nearty constant, i.e. C(A) = ((), can itself be reduced quadratically by other methods.
The above quadratic reduction is possible when considering the standard nested Monte Carlo estimator for Equation ( however this estimator is not competitive with the MLMC framework. It operates by estimating the inner expectation Σy|x=> [=(, Y)] with error O(c/K) (which is sufficient by the Lipschitz property), nested withing an estimator of the outer expectation with error ((e). The product of the sample complexity of the outer estimator AA and the cost C(A) of the inner estimator results in an overall complexity of O(K*SV/e*) classically, or Ö(K /e²) quantumly. This is no better than the classical MLMC estimator with respect t.
Now, consider the MLMC framework. Instead of using a single randomized algorithm A, it uses a sequence of algorithms Ar corresponding to levels / 0, 1....,... L. The computational cost C(Ai) generally grows exponentially with 1. For example, C(A,)) ~ 2 in the MLMC solution for nested expectation problems (Algorithm]) I]. The highest level L is chosen as ((lo(1//e)) therefore the cost at the highest level is C(Art) = (poly()/e)).
The main idea from the QA-MLMC (An et al. 2021) is to replace each classical Monte Carlo estimator for E Ai] with QA-MC. While this substitution works in principle, there is critical issue as the level approaches the maximum level L: the computational cost C can grow sigmificantly, sometimes as high as O(poly
This growth undermines the quadratic speedup achieved by QA-MLMC because the total cost is no longer dominated by O(1)-coss subroutines. Instead, the increasing Cj makes the computational cost scale poorly with the desired error tolerance c, leading to a loss of efficiency. Although the algorithm in An et al. (2021) leverages Monte Carlo estimate B]A the achieved speedup less than quadratic because C(Ai) scales as O O(poly(1/e)) instead of O(1) at the highest levels. This growth in cost undermines the expected quadratic speedup.
How to recover the quadratic speedup?
We can break down Theorem 2.1 to capture its core insights, then leverage them to refine our quantum algorithm. Theorem 2.1 provides two main ideas:
1. The target quantity is written as a limit of quantities with vanishing bias, and then re- expressed as telescoping sum, μ lim ss = Ei st) + sg. The MLMC method estimates each level individually, optimizing resource allocation.
2. Estimator Variance Control: At each level 1, an estimator A, designed with expectation [[Ai] S/+1 St, and bias and variance diminishing with 1, while cost increases with I,

---

In the classical solution (Algorithm I. the sequence is
Σ o(x xx))
s.laasicaal == B X,
By the law of large numbers, it is clear that st,clasiical converges to the target. Algorithm employs standard Monte Carlo to estimate st,ciasiccal - 81- L.classical-
A key observation is that we design new sequence of quantum subroutines A qqquntum They have a computational cost similar to that of the classical A, (in the sense of the 7 parameter from Theorem 2.1p while achieving improved statistical properties (parameters and /3 in Theorem 2.1 To achieve this goal, we first define a new sequence #1.quantum that also converges to the target value. lts definition is based on using canttum-acceleatted Monte Carlo estimate the conditional expectation, with progressively higher precision as the sequence advances. Based on this new sequence, our Qqqantuu can be naturally defined to estimate 51, 51.quantum St- Lquantum- Finally, we can use existing quantum-acce
Monte Carlo algorithms again to estimate E. ||AIIqqumtuni at each level I. Together, these components achieve a quadratic speedup over MLMC, making this approach provably more efficient than a direct application of QA-MLMC.
A further distinction from An et al. (2021) is the choice of the quantum subroutine: whereas An et (201)) builds on the QA-MC algorithm in Montanaro (2015), we instead employ the newer QA-MC algorithm of Kothari and O Donnell (202)). The latter demands less priori information from the user (compared to Montanaro (2015) and removes the extra polylogarithmic factors in the error bound (compared to Hamoudi (2021)).
Proof agenda, and the median trick
The majority of our work is to show the following:
Proposition 3.3. Under the same assumption as Theorem 2.7 we can design an algorithm Q- NESTEXPECT-0.8 (Algorithm 4 with cost Ö(K /E) that estimates E[g(X,,lo(XX Y)]) with an absolute error of no more than and a success probability 0.8.
Proposition 3.3 specifies fixed success probability of 0.8, whereas Theorem 3.2 allows an arbitrary value 1 - 6. Nevertheless, once we apply the "median trick" detailed below, we can tolerate an arbitrarily small failure probability. The proof of Lemma 3.4 is Appendix [A.4
Lemma 3.4 (Median trick). Given a set of random independent random variables XI...., . Xn, and an unknown deterministic quantity suppose thut each X; satisfies Pr[X; E (=- ō, 6)] 2 0.8,
then Pr[median) (aiiaaan(X..... ( Xn) - 6, z + 8)] 2 exxp(-0.88g
By invoking Lemma
3.4
we can implement the Q-NESTEXPECT algorithm of Theorem 3.2 by:
Run Q-NESTEXPECT-ON (Algorithm independently [log(1/6)/0.15 times, and return the median of the resulting outputs.
Proving Theorem
3.2 based Proposition 3.3 is given in Appendix A.4
3.2 Our algorithm
To introduce algorithm, first define in Algorithm a sequence of auxiliary algorithms B,.
Algorithm 2 (xx when / 0
1: Input: from X.
2: Apply quantum-acceleratee Monte Carlo Theorem 3.5 on Geny (x) and & to estimate
[o]x==[((X,))
with accuracy 2-(++)) and success probability at least 1 - 22-
3: Clip the estimate into the region [- -VV vV and denote the result by (1)).
4: Output: g(2, (x)).

---

Algorithm Bi with input estimates g(x, Exxxx= Y))). Raising the value of will improve the accuracy but also elevate the computational cost. The typical way we obtain input x: for Algorithm B is by generating it according to X using Genx. We refer to this combined process as (x))). The
sequence {B (X) ))) 120 produces random variables whose expectations progressively approximate the target [g X, B ( X, Y)D] The properties of B₁ are studied in Lemma 3.6
Now we define A based on Bj. When we set Ao (X).. When 2 1, we define A in Algorithm
Algorithm 3 A when
1: Sample æ from X using Genx.
2: Apply (x to obtain g(2, (x))).
3: Apply B:-1 (ar) obtain g(ar, 91 (2:)).
4: Output: A == g(a, (x)) g( or (x)).
Algorithm At is a "coupled" difference of B₁ and B It executes B1 and Bi-1 using the same input æ. Compared to independently executing B₁ and Bi-1, this coupled implementation maintains the same expectation but ensures that the variance of A decreases to zero as increases, which is beneficial for objective. The properties of A,, and of its output Ar, are studied in Lemma 3.7
Now we are ready to describe our solution to Proposition 3.3 in Algorithm
Algorithm Q-NEESEXXP
1: Input: Accuracy level e.
2: Set T. [log, (2/e)]-
3: for (= 0 to L do
4: Apply quantum-acceelerteed Monte Carlo Theorem 3.5 on A to estimate [[[[] with accuracy
e/(2L + 2) and success probability at least - 0.1 [+] Denote the output by oz.
5: end for
6: Output: 7= Et 8.
Q-NESTEXPECT-OA is quantum-inside-quantui algorithm it uses guantum-acccelean Monte Carlo to estimate the expectation of another iteration of the for loop in Q- M-NESTEXPPET-00 we use distinct quantum-acceleraa Monte Carlo algorithm to individually estimate E Ao], E,AA]...,EEAA and then sum the results.
Monte Carlo algorithm. In each
To demonstrate that Algorithm 4 satisfies the guarantees stated in Proposition 3.3 we first prove few lemmas studying the properties B, and At. The crucial property we will use from Kothari and O' D'Dnnnell (202)) is follows:
Proof Sketch:
Theorem 3.5 (Theorem 1.1 in Kothari and O D'Donnell (023)). Given the access to an algorithm which outputs random variable with mean μ and variance a, there is quantum algorithm that makes (((a/e) (0)(1))) calls of the above algorithm, and outputs an estimate jı of μ. The estimate e-close μ4, that is j μl) S e, with probability at least 1 8.
Now we study the computational and statistical properties of B,. The formal statements of the next two lemmas can be found in Appendices A. and A.2
Lemma 3.6 (Informal). For every 1 2 0, with Bi defined in Algorithm 2 we have:
1. Cost: For all x, the cost of implementing (z)x) is at most ((2
2. Mean-squared error and Bias: For all x, the mean-squared error and the bias of the output of (x(x) with respect to g(x, Ey|x== Y))) are most, respectively, 2 21 and 2
3. Variance: The variance of the output of (x) is at most 2 + 2S.
Similarly, study the properties of A..
8

---

Lemma 3.7 (Informal). For any 1 2 O, with A defined in Algorithm we have:
1. Cost: The cost of implementing A is at most ((2'KVV).
2. Bias: The bias of Ek=0 A with respect to Equation is at most 2-!
3. Variance: The oulput Di of Ai has variance most 2S when and 10 2 when 2 1.
By applying Lemma 3.7 and ignoring lower-order terms,
sequence (Ai 120 corresponds to a = 1,3 2 I o(1 in the MLMC framework, whereas the standard classical sequence (Algorithm 1 has a 0.5, 8 1,7 1. This improvement arises from our new quantum
subroutine. It eventually yields Proposition 3.3 that result, in turn, establishes our main Theorem 3.2
demonstrating overall complexity of (11/)) when quantur-accelleatee Monte Carlo is used to estimate each B[Ar]. The complete proof of Proposition 3.3 appears in Appendix A.3
Optimality of our algorithm: Our algorithm achieves the optimal dependence on up to polylog- arithmic factors. In particular. when g(z, 2) := (which is I-Lipschitz), the nested expectation in Equation [ simplifies to K[ό]. Thus our problem includes standard Monte Carlo as a special case. Moreover, from known lower bounds on the quantum complexity of mean approximation (Nayak and
Wu 1999: Hamoudi 2021), estimating the mean with error requires at least (2(1/c operations. Our algorithm matches this dependence while extending to a broader class of problems.
Applications
We now revisit the examples from Section 1.1 and analyze the cost of applying our algorithm.
Bayesian experiment design: Recall our target is
Ex [lo Pr[[X YIII Ey [xI (log(P YJII].
The first term matches Equation with o(x, y) == Pr[X=z Y=yl and g(z, 2) := log z. Assume Pr[X=r Y=y] E [c. 1] for all (z. y) (e.g.. when is finite with strictly positive mass). Then Assumption 1 holds with K 1/c because the log function is (1/c)-Lipschitz on [c. 1]. Assumption 2 holds with V = since 0 < Pr y=yl < 1. Assumption 3 holds with $ log2(c) because g(x, = log(.) )) [log c, 0). Therefore, Theorem 3.2 implies that Q-NESTEXPECT estimates the first term within error with cost O(llog(e)lc- log(1/6)/o
EVPPI: In the EVPPI example, our target quantity is
Ex max Lkf......d
[xxx
max ke(1.....d)
This problem requires a little extra care because the inner function is vector-valued in this case: Φ(x y) = (f1 (ar, fal-..,,(((;,, y)) and g(,, 2) max(21,.... za). Ignoring the dependence on the dimension d, and adapting our estimator to the multidimensionall case, one can estimate the first term at cost of Ö(V/c) assuming, for instance, that the family of functions fx is uniformly bounded V.
CoC option pricing: We have g(a, z) max k 0} with Φ g. Then, Assumption holds with = Assuming that both X, Y are bounded between [-a, b) where a, 2 0, and the strike price is k 0, then Assumptions 2, 3 hold with S V max k a + k)). Theorem 3.2 implies that Q-NESTEXPECT estimates the CoC option price error with cost (max k; a k)a 1og(1/8)/e}
Conditional stochastic optimization: Recall that the goal is to find an x that minimizes.
F(z) [f (I {)]]]-
Assuming the decision set is finite, X' {21...., IN }. and that each nested expectation F(x;) satisfies our Assumptions 1-5, then Q-NESTEXPECT returns an additive-e estimate of at cost Ō(K v VSV /e). This provides function-value oracle for F. Using quantum minimum finding Durr and Høyer 1996), the cost to output à with F(i) < min; F(x.) + e SVKVSVN/e)

---

Limitations and Future directions
First, although our algorithm achieves near-optimal cost for estimating Equation T among quantum algorithms, our results are derived under fault-tolerance assumptions and thus remain difficult to realize on current NISQ hardware (Huang al. 2024). Second, the original QA-MLMC algorithm applies to wider range of scenarios than estimating the nested expectation. Thus, our contribution should be seen as an improvement of QA-MLMC within a specific yet critical set problems.
Nevertheless, our work highlights how quantum computing can give MLMC much more freedom to invent novel approximation sequences. In favorable scenarios, like ours, carefully crafted sequence can lead to significantly improved (and potentially optimal) algorithmn. This raises an intriguing question: which other MLMC applications could achieve similar quantum quadratic speedup?
We expect that our technique can be extended to closely related problems. For instance, with additional assumptions, classical MLMC also has ((1/22) cost when g g(=) = 1:20 is Heaviside function (Giles and Haji-Ali| 2019 Gordy and Juneja 2010). This quantity plays key role in computing Value-at-Risk (VaR) and Conditional Valuc-at-Re Risk (CVaR), which are widely used in finance. Similarly. MLMC has been shown be effective conditional stochastic optimization, bilevel optimization problems (Hu et al. 20200 2021 2024), which is an extension of our setting with additional optimization steps. We expect our approach can be adapted address these problems.
Our primary focus the dependence on which is also central to both the classical (Giles) 2015) and quantum MLMC (An al. (021)) literature. However, our problem also depends other parameters, such as the Lipschitz constant and the variance. It can readily be extended to vector-valued random variables by using quantum multivariate estimator (Cornelissen al. (022), thereby incurring dependence on the dimension as well. An interesting open question is whether our current algorithm
optimal with respect to these parameters, or whether improvements are possible.
Acknowledgement
J. Blanchet, M. Szegedy, and G. Wang acknowledge support from grants NSF-CCF-2403007 and NSF-CCCF-400008. Y. Hamoudi supported by the Maison du Quantique de Nouvelle-Aquitaing "HybQuant", as part of the HQI initiative and France 2030, under the French National Research Agency award number ANR-22- 22PPNCQ-00002.
10

---

References
An, D., N. Linden, J.-P. Liu, A. Montanaro, C. Shao, and Wang (2021). Quantum-accelern multilevel Monte Carlo methods for stochastic differential equations mathematical finance. Quantum 5, 481.
Bennett, C. H. (1973). Logical reversibility of computation. IBM journal of Research and Develop- ment 17(6), 525-532.
Blanchet, J., M. S. Squillante, M. Szegedy, and G. Wang (2025). Connecting quantum computing with classical stochastic simulation. arXiv preprint arXiv:2509. 18614.
Blanchet, J. H. and P. W. Glynn (2015). Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pp- 3656-3667. IEEE,
Blanchet, J. H., P. W. Glynn, and Y. Pei (2019). Unbiased multilevel Monte Carlo: Stochastic optimiza- tion, steady-state simulation, quantiles, and other applications. arXiv preprint arXiv: 09999..
Brassard, G., P. Hoyer, M. Mosca, and A. Tapp (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics 305, 53-74.
Cornelissen, A., Y. Hamoudi, and S. Jerbi (2022). Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pp. 33-43.
Dürr, C. and P. Høyer (1996). A quantum algorithm for finding the minimum. arXiv preprint guant-ph/600014.
Foulkes, W. M., L. Mitas, R. Needs, and G. Rajagopal (2001). Quantum Monte Carlo simulations of solids. Reviews of Modern Physics 73(1), 33.
Giles, M. B. (2008). Multilevel Monte Carlo path simulation. Operations Research 56(3), 607-617.
Giles, M. B. (2015). Multilevel Monte Carlo methods. Acta numerica 24, 259-328.
Giles, M. B. and T. Goda (2019). Decision Decision-making under uncertainty: using mlme for efficient estimation of evppi. Statistics and computing 29, 739-751.
Giles, M. B. and A.-L. Haji-Ali (2019). Multilevel nested simulation for efficient risk estimation. SIAM/ASA Journal on Uncertainty Quantification 7(2). 497-525.
Gordy, M. B. and S. Juneja (2010). Nested simulation in portfolio risk measurement. Management Science 56(10), 1833-1848.
Haji-Ali, A.-L. and J. Spence (2023), Nested multilevel Monte Carlo with biased and antithetic sampling. arXiv preprint wxXiv22388.0883.
Hamoudi, Y. (2021). Quantum gaussiansinnnn mean estimator. In Proceedings of the 29th European Symposium on Algorithms (ESA), pp. 50:1-50:17.
Hamoudi, Y. and F. Magniez (2019). Quantum Chebyshev's inequality and applications. In Proceed- ings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 69:1-69:16.
He, I.. and S. Kasiviswanathan (2024). Debiasing conditional stochastic optimization. Advances in Neural Information Processing Systems 36.
Heinrich, S. (2002). Quantum summation with an application integration. Journal of Complex- ity 18(1) 1-50.
Hironaka, T. and T. Goda (2023). An efficient estimation of nested expectations without conditional sampling. Journal of Computational and Applied Mathematics 421, 114811.

---

Hong, L. J. and S. Juneja (2009). Estimating the mean of non-linear function of conditional expectation. In Proceedings of the 2009 Winter Simulation Conference (WSC), pp. 1223-1236. IEEE.
Hu, Y., X. Chen, and N. He (2021). On the bias-variance-cost tradeoff of stochastic optimization. Advances in Neural Information Processing Systems 34, 22119-221133
Hu, Y., J. Wang, Xie, A. Krause, and D. Kuhn (2024). Contextual stochastic bilevel optimization. Advances in Neural Information Processing Systems 36.
Hu, Y. Zhang, X. Chen, and N. He (2020). Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances in Neural Information Processing Systems 33, 2759-2770.
Huang, B., Y.-T. Chen, B. Gupt, M. Suchara, Tran, S. McArdle, and G. Galli (2024). Evaluating quantum-classicaa quantum Monte Carlo algorithm with matchgate shadows. Physical Review Research 6(4), 043063.
Kothari, R. and R. O' D'onnelll (2023). Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1185-1215. SIAM.
Lindley, D. V. (1956). On a measure of the information provided by an experiment. The Annals of Mathematical Statistics 27(4), 986-1005.
Martin, G. M., D. T. Frazier, and C. P. Robert (2023). Computing Bayes: From then 'til now. Statistical Science I(1), 1-17.
Montanaro, A. (2015). Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471(2181), 20150301.
Nayak, A. and F. Wu (1999). The quantum query complexity of approximating the median and related statistics. In Proceedings of the thirty-first annual ACM symposium Theory of computing, pp. 384-393.
Rainforth, T., R. Cornish, H. Yang, A. Warrington, and F. Wood (2018). On nesting Monte Carlo estimators. In International Conference Machine Learning, pp. 4267 PMLR.
Ramaley, J. (1969). Buffon's noodle problem. The American Mathematical Monthly 76(8), 916-918.
Sidford, A. and Zhang (2023). Quantum speedups for stochastic optimization. In Proceedings of the 37th International Conference on Neural Information Processing Systems.
Syed, Y. and G. Wang (2023). Optimal randomized multilevel Monte Carlo for repeatedly nested expectations. In International Conference on Machine Learning, pp. 33343-33364. PMLR.
van Apeldoorn, J. (2021). Quantum probability oracles & multidimensional amplitude estimation. In Proceedings of the 16th Conference the Theory of Quantum Computation, Communication and Cryptography (TQC), pp. 9:1-9:11.
Zhou, Z., G. Wang, J. H. Blanchet, and P. W. Glynn (2023). Unbiased optimal stopping via the MUSE. Stochastic Processes and their Applications 166, 104088.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately state the main contributions of the paper, including both the algorithmic and theoretical contributions and its scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in the conclusion and the introduction.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
We state the results in the main text, and provide the proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA].
Justification: does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA].
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
ic for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuii wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research complies fully with the NeurIPS Code of Ethics. does not involve sensitive data, human subjects, or potentially harmful applications.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is advance the field of Quantum Computing, and Monte Carlo methods. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not introduce or release any new models or datasets that could pose risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.paaersstt
package should be provided. For popular datasets, paperswi thcode. cow/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core methods and contributions of the paper do not involve the use of LLM in any important, original, or non-standard way.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A Proofs for the Main Algorithm
A.1 Analysis of the B algorithms
Lemma (Formal statement of Lemma 3.6 The algorithm Bi defined in Algorithm for all 1 2 has the following properties:
1. (Cost) For any input the cost of implementing (x(x) is ((2)KVV).
2. (MSE) For any inpul x, the heean-squreed error (MSE) of the oulput g(a, ((())) (i
with respect g(x, Ey|x==|<(>) Y)1 is at most,
o(x (x)) g(v, Ey xxxx==l0(X, YID 2-
3. (Bias) For any input the bias of the output g(,, (x)) of Bi(x) with respect to g(z, By Bylx==lo(XX YJJ) is most,
Big(z, ((()) g(v, By|x-=
$
4. (Variance) The variance of the output of Bi when the input is sampled according to X is at most
Varx[g(X, (x)) 2
Proof of Lemma 3.6 We prove the properties separately.
Cost of Bi. Implementing Step 2-3 of Algorithm 2 incurs computational cost of Ö(2'K VV). To see this, note that it would be sufficient to take O DVV) samples to have success proba- bility 0.8 using Kothari and O'Donnel] (2023). When we increase the probability of success to Thus the
1-2 (4K" we need multiply this with factor of Ollog 4K² 22
total cost is (V2).VV).
MSE: Let (z) be the output of Step 2 in Br(r), i.e., the output of the quantum-acccelerated Monte Carlo algorithm in Kothari and O' Donnell (2023) before clipping. We claim
[z) Eyjx= (o
[)(()) Ey
i... clipping will never increase the error. To see this, notice that
Ey|x= o (x, Y)J VV
because E| < [E[Z"] for any random variable Z. Therefore, we know as a-priori that the target quantity of step 2 is between -V and V. Suppose Φi(x)) is between [-V, v]. then Φi(z) = (z)..
ie., clipping happens. Suppose (x)) V, then
[0)(x) (oxx== 2 |V Byix== Y)] = [0((x) (XX, Y)J--
Similar argument holds when σz)x) -V. Thus, the squared error either decreases remains unchanged after clipping, establishing the claim.
Since (I) has accuracy 2-(11) K with probability at least 1 1-2-(24+4+4 we know (x) has the same property. Moreover, the absolute error between (x) and Ey [y|xx= Y)] can
be no more than 2 due to clipping. Thus, the expected squared error between 27 (I) and [o is upper bounded by
E (x) - (0X,
< KK 222-(2((+ 2(+1)) x 1 + 4V x 2-1+11 (2++))
< K K-222-11
20

---

For each fixed æ, the absolute error between g(z, (z and g( ( Y)J) is not greater than
K (((((1) [ylx==1 X, Y)]
due to the Lipschitzness of g, Therefore, we have the following estimate on the mean-squared error of By with input x:
[1(2, (i()) - g(x; ( (XX,)) 2
(3)
Bias: The bias of the output of algorithm B₁ on imput æ, with respect to g(æ, ByIxx=l Y))),
is
Big(z, or g(æ, Ey]x==
E (9(21, & (x:) (0,, By Bylx== YICA
$ T. |9(0, ()(,,,(()))) - x. By Xy X)))
2
Here the first two inequalities follows from [[[[]] - al S EIX all S / a|² and the last
inequality follows from Equation 3
Variance: To simplify the notation, define G(x) as g(,, Ey ( Y)I). Then Assumption reads Varx[G(X)] S. We bound the variance of the output (X)) as:
[G(X) - Ex|G(X)) Varx[g(X, (x < Exl(o(X, (x))) [x((()))
- (
$ 2 [ (()()))((())))))))))))))))))(()) G(x)) + 2Varx (G(()]
2 + 25 < +
where the first inequality uses the fact that Var[X] min, E((X - -a) and the last inequality uses Equation
A.2 Analysis of the Ar algorithms
Lemma (Formal statement of Lemma 3.7 The algorithm Ai defined in Algorithm for all | 1> has the following properties:
1. (Cost) The cost of implementing A is
2. (Bias) The bias of the sum Ekzo As of outputs up to level is at most 2-1 with respect to Ex (X, [ Y)), Le.:
Σ B| Ex(g(X, (x, <
3. (Variance) The variance of the output A of Ai is at most 2 2 28 when 1 = 0 and 10 x 2 when > 1.
Proof of Lemma 3.7 Cost of Al. Clearly implementing A once costs around twice of the cost of B Therefore the claims follows from Lemma 3.6
Bias of Ei A.. Since the expectation of As when t 2 is the difference in expectations between the outputs of (X) and Ba (X), we know the expectation of k As is telescoping sum that is equal to the expectation of the output of the last algorithm (X). Therefore, the bias is
[[Aa] EXg(X, YODI
= [ (x)) Ey (oxxxooXXXXXX Y))]
$ E
Big(2 ( g(x Er 16 Y)D]
2-
21

---

where the last inequality follows from the bias established in Lemma 3.6
Variance of A The case 1 follows from Lemma 3.6 and the definition Ao -Bo()).
When 2 1, we can bound the second moment as follows:
B[ = E
Eg (((z,,((x)) g(x, dt- (z)))
E (1(2, 2e (x)) - g(z, By (I))) =]
< 21 x~
E (9(2, - (z)) - g By x (x r))) "]]
+ 2E x
- 2(2 21 + -2-2+22 10 x 2 2-
where the last inequality follows from the mean-squared error established in Lemma 3.6 Since the second moment always no less than the variance, our claim on Var[Ai] is proven.
A.3 Analysis of the Q-NESTEXPECT-O0. algorithm
Proof of Proposition 3.3 We claim Q-NESTEXPECTT-., (Algorithm 4 outputs an estimator that is
e-close to (X o Y)]] with probability at least 0.8.
For each our failure probability is no larger than 0.1'+1, Therefore the probability of at least one failure in the for-loop of Algorithm 4 is at most 0.1 + 0.1 + ... 0.2 by union bound. Thus there is
probability least 1 (0.1 0.1 + ...) 2 0.8 such that & is c/(2L 2)-close to E[Ai] for every 1. Under this (good) event, our final estimator has error
EAA
Σ 6,
BAJ
S (L
+2
At the same time, Lemma 3.7 shows E
[ is 2 close to Elg(X, E(O(X, Y)JJ.
Using
L = [2g])2/ we conclude our estimator has error
L
51
Elg(X, E(o(X, YIDI
Σ R(A,]
1=0
1=0
E|AI - (60X,E00( YIDI
Se.
1=0
with probability at least 0.8.
The cost of our algorithm is the summation of the costs of L 1 different quantum-accelerated Monte Carlo algorithms. For 1 = 0. since Au (X) the variance of Au is most 2 + 25 by
Lemma 3.6 Thus, Theorem 3.5 shows that the cost of estimating [[ with error c/(2L + 2) is
Ö(VSL/e) times the cost Ō K / /V of implementing (x)... which gives D(LKVSV /c). For
12 1, the variance A is at most 10 x 22 by Lemma 3.7 Hence, the cost of estimating E[A]] is Õ(2-lT./c) times the cost Õ(2 VV) of implementing A, which gives Ö /V/
Summing up all the costs together, and using that L = O(log(L/e)), yields total complexity of O(LKVSV Met/VV//++LKV//. Ö(KVSV/e).
A.4 Median trick and main theorem
Proof of Lemma 3.4 (Median trick). Let
1. if & -2
+
Yi
i 1 1.... n
otherwise,
22

---

and set Sn = Σ Y, Because each X; lies in the interval (z (6-6, 2- with probability at least 0.8,
we have Pr Pr 0.2 and hence
E
B I 0.2n.
The sample median falls outside the interval (z 6, + 8) if and only if more than half of the observations do so, i.e., Sn > z.. Consequently,
Pr[median(XX, (1,, X,) $ (2 o, + Pr Pr(s, > 1 2" < Pr(S, - E[S.] 2 0.3n].
Because the Y; are independent Bernoulli variables, Hoeffding's ' incquality gives
Pr(S, B[S,] 2 S exp(-2f" /m),
t> 0.
Taking 0.3n yields
1 Pr[S, > I"l & <xxp(-2(0.nn)/m)) = cxxp(-0.88)
Therefore,
Pr[median(X,, (X1. X,) E (2 5, 6)] = Pr[median ( (X..... X,) & (s 0, 8)]
exp(-0.18n).
claimed.
The proof of Theorem 3.2 follows immediately by applying the median trick to the algorithm given
in Proposition 3.3
Proof of Theorem 3.2
The Q-NESTEXPECT algorithm was defined as,
Run Q D-NESTEXPECT-O. (Algorithm independently [log(1/8)/0.18) times, and return the median of the resulting outputs.
Since the output of O-NESTEXPECT-O0.8 c-close Equation (I) with probability at least 0.8 (Proposition (.3). the median trick (Lemma 3.4) implies that the output of Q- Q-NESTEXPECT is - 8. The cost
e-close to Equation ( with probability at least exp(-0.16 (loo(o/))////i of Q- Q-NESTEXPECT is also [log(1/8)/00 times the cost of Q-NESTEXPECT--O. and is thus Ö(K SV log(L/ as claimed.
2 1
B Classical MLMC Parameters
Under Assumptions 1-4 in Section 3 we verify that the classical MLMC sequence defined in in the MLMC framework (Theorem 2.1 when
Algorithm corresponds to a 0.5, 3 =
K, V O1) are constant numbers. Firstly, the computational cost of A is clearly 0(2) thus 1. To analyze the variance, it useful to observe
(xx, 2 2 + +a)) 9(X, T S.) + g( S.)
K 21-1
S. -Sl
because of the Lipschitz continuity. Let Z; - o(X, 22: ò(X, Y2:). it is then clear that the Z,'s have zero mean and are conditionally independent given X. Further,
Var 74
X]
(aX, Y2--)) x Var(ø(X, X, Y2) x = 2arr (o(X,)) 2V.
Therefore
E|S. - -S Var[S, - S.] = Var
Z,
< 2V..
i=1
23

---

Thus
g(X, y(, (1 Se) + g 21-1 21-1 So)
2
K²
E g 인 (S. + Sb)
E
[
S
2
221-
K²
221-1 2'V
2K2V
2
0(2-").
Therefore 3 = L, as claimed.
Finally we study the bias, which is
b
B[AN] EX F(o(X, YJII
k=0
So)) 1xx2--(111))++0 (0
(i,,)) Y)) and A = g(x k 2 1. We obtain telescoping sum simplifying
where Do = o(X,
when
2
(Se + s.)) Σ E[|N] Ex (xxx
1
E Ex.,,.... ,(x, E ((
}
Therefore, the bias most
10(x,
E o (xx)
Byxxxx) YnD
S Ex Y2
2
(by the triangle inequality)
Σx ki
((X, Yk)
< KEx,Yi
Ex,x [xX,
(since y is K K-Lipschitz)
2
Σ I== @(X, Yv)
E Erix 16(x, Y ?
KEEx
Ey Eii..
2
(by the Cauchy-Schwarc Schwarz inequality)
K
Ex Varrix (6(X, Varrixx(((xx))) Y)]
21/2
KVV
(by Assumption in Section 3)
2//2
Thus, we have a = 0.5, as claimed.
C Lower Bound for the QA-MLMC Algorithm of An et al. (021
We demonstrate Proposition 2.3 namely that the QA-MLMC algorithm of et al. 2021 is optimal (up to polylogarithmic factors) for solving the problem stated in Theorem 2. when the sequence {Arh1i is arbitrary. We consider two parameter regimes for (a, 3,) separately.
Regime 3 27. In that regime, the complexity of the quantum MLMC algorithm of An al. (002 is Õ(e -1-(n-000,)))// We observe that most expensive part of the computation this algorithm occurs at the last level = (log(( (l)g(()c)/o), /c)/o), where the algorithm uses Õ ((c-1+0.58/a samples, each with cost Cr. Ö(e-7/a We take inspiration from this behavior to design a hard instance for the lower bound. The lower bound proceeds by a reduction to the following query problem:
24

---

Definition C.1 (COUNT" o "" Fix three integers t, n, m with t S n. Define two sets of
Boolean matrices Mo: M1 C {0, 1 jn such that:
. M Mo iff each row of M has parity 0 (i.e., Ej Ma, = mod 2 for all i E [n])
.M M1 iff exactly rows of M have parity 1.
In the COUNT o PARITY problem, one is given access to quantum oracle ji, + (-1) 1 (i. for an unknown M E Mo U U and the goal is to decide to which set M belongs to.
By composition properties of the quantum adversary method, the quantum query complexity of " COUNT PARITY" is the product the complexity of the counting problem COUNT (which
is (2( n/t))/)))))))))) and of the parity problem PARITY" TM (which is ((m)). We refer the reader to (van Apeldoorn 202T Lemma 11) for more detailed version of this argument.
Proposition C.2. Any quantum algorithm that solves the COUNT PARRITY t problem with success probability at least 2/3 must make Q1 /n/t) queries to M.
We now explain how to construct a hard instance for the MLMC problem out of an input to the 4 PARITY" problem. Fix (a;, B, 7) such that 2 1 max 3) and 3 < 2y, Choose t, n. m such that m CL = - 7/a T/a and t/n = e 2² 2-B//a, Given M M, M1 define the random variable PM E 8/a-3/ obtained by sampling E [ri] uniformly random and setting
0,
PARITY (M,) O. B/a-1,
PM =
PARITY (M, 1.
We consider the problem of estimating the expectation μ = B[Pas] with error c/2. Observe that μ . E Mo and μ = t t/nc9/o-1 if M M,. Hence, estimating μ + c/2 allows solve the " PARITY problem on M.. By Proposition C.2 this cannot be done faster than with quantum queries.
Amm n/t) -1---1000
remains to construct a sequence of random variables A with parameters (a, 3, that can approxi- mate Pa. All random variables are chosen to be zero, except A which is chosen to be Pas (where L= (1/e)//).. The cost to compute Ar. (naively) is Cr.
é - 2 The variance is Var Ar] = Var PM]] < E[ < B/ 2-9L, The cost and variance of A are zero when / * L. Finally, for any we have,
Σ
0, E = psess 2-
if L, ifl <
Hence, we have constructed a sequence of algorithms {AAr)22 satisfying the conditions listed in Theorem 2.1 but for which quantum algorithm can solve the estimation problem using fewer than Q(E (1-1- 38)/a) quantum queries.
Regime 3 27. In that regime, the complexity of the quantum MLMC algorithm of An al. 2021) is ((e-)). The most expensive part of the computation occurs at the first level = 0, where the algorithm uses Ō(c-)) samples, each with cost Ct. Ō()). This is trivial to adapt into lower bound (in fact, applies to the regime 3 < 2-y as well). We know that for standard Monte Carlo, there exists a quantum query problem (Nayak and Wu 1999; Hamoudi] 2021) for which generating certain random variable X has cost ((1) and variance Var[X] = O(1) and the quantum complexity of estimating [[X] + is ((1/e). This can be cast as MLMC problem by considering only the first level: Ao X. We have |Ek= [|Aa] E[X]] for all 4, and C₁- Vi for all > 0. Since this sequence applies any values of (a, Y),, have generic lower bound of ((1/c).
25


Reviews:
[{"review_id": "dcvO20IrXu", "reviewer": "Reviewer_hqsW", "summary": "This paper proposes a novel quantum algorithm called \"quantum-inside-quantum MLMC\" that achieves a quadratic speedup for estimating nested expectations—a class of non-linear functionals arising in various practical scenarios such as Bayesian experiment design and financial engineering. Classical Monte Carlo methods typically have a complexity of $O(\\epsilon^{-2})$, and existing quantum methods reduce this to $O(\\epsilon^{-1.5})$. The proposed approach further improves it to a nearly optimal $O(\\epsilon^{-1})$, leveraging specifically designed multilevel Monte Carlo decomposition optimized for quantum computing.", "questions": "- Can the authors comment on how the algorithm’s complexity would degrade or change if the assumptions (such as Lipschitz continuity) were weakened or violated?\n- For the application of MLMC in finance and optimization listed in Section 5, does the proposed quantum algorithm potentially preserve the quadratic speedup? Especially consider the assumed conditions in page 5.\n- The paper focuses primarily on nested expectations. Could the authors elaborate on whether and how their quantum-inside-quantum MLMC approach might extend to more general classes of nonlinear functional estimation problems?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "#### Strengths\n\n- The authors propose a novel quantum algorithm that specifically leverages quantum advantages at multiple hierarchical levels of the Monte Carlo estimation procedure, rather than merely accelerating classical MLMC subroutines individually.\n- The authors identify and address the limitation of direct quantum adaptations of classical non-linear MLMC, which clearly explain why the quadratic speedup is lost and how they recover the speedup.\n- Achieving a near-optimal complexity of $\\tilde{O}(\\epsilon^{-1})$, confirmed with known lower bounds, represents significant theoretical progress and firmly establishes quantum advantage in this domain.\n\n#### Weaknesses\n\n- The complexity analysis and algorithmic performance depend heavily on the assumptions listed in page 5. In practical scenarios, these conditions may not strictly hold or may degrade, which may limits the applicability of the proposed algorithm.\n- While theoretically impressive, the implementation nested quantum subroutines is potentially complex. Details on practical quantum resources (circuit depth and width, error accumulation, noise resilience, quantum memory requirements, etc.) required to realize the quantum-inside-quantum approach on real or near-term quantum hardware remain largely unexplored.", "was_revised": true, "final_justification": "I think this paper is theoretically solid and has various applications in finance and optimization. The techniques applied in this paper are  of independent interest. Also the authors address my concerns on the assumptions during the rebuttal period. I would recommend for acceptance.", "rebuttal": "We thank the reviewer for the valuable suggestions! We address the questions raised below:\n\n**Assumptions and Practicality**:\n\nGood point. While the assumptions we made appear frequently in the literature (e.g., the original nested expectation paper [1]), we acknowledge that they may not hold perfectly in all practical scenarios. There are essentially two types of technical assumptions appeared in the current version: \n1) *Smoothness assumption (Assumption 1);* \n2) *Moment assumption (Assumption 2,3).* \n\nWe discuss them separately.\n\n*Regarding the smoothness assumption*: It is indeed possible to generalize this assumption. Additional knowledge about the functions or the underlying distribution could further relax the continuity requirement. In classical Monte Carlo literature, there are studies on nested expectations where the function $g$ in our notation is a Heaviside function [3,4]. The idea of their assumptions is to assume that the underlying distribution behaves appropriately at the discontinuous points, ensuring that it does not cause issues.\nIn summary, there is a tradeoff between the assumptions on distributions and the regularity assumptions on the functions. Stronger distributional assumptions and/or extra knowledge on the function can lead to weaker assumptions on its smoothness, and vice versa. If we use the same distribution assumptions as in [3,4] and assume $g$ is a Heaviside function, we could still get the quadratic speedup. \n\n*On the necessity of finite second moments:* A finite second moment may be required to achieve a complexity of $\\tilde{O}(\\epsilon^{-1})$. Reference [2] shows, even in the context of standard Monte Carlo estimation, assuming only the existence of a $(1 + \\delta)$-th moment with $\\delta \\in (0,1)$ is insufficient for attaining $\\tilde{O}(\\epsilon^{-1})$ cost with a quantum algorithm (but a quadratic speedup still exists).\n\n*On the known constants for the second moment/variance:* There exists an interesting intermediate regime where the assumption (1-2) could be replaced by $<\\infty$ (instead of the conditions $\\leq V$ and $\\leq S$, where $V$ and $S$ are constants known to the users in advance.) Right now we do not know if we can design a quantum algorithm to achieve $\\tilde O(\\epsilon^{-1})$ cost in this relaxed assumption. \nOne potential approach is to first perform a low-cost Monte Carlo estimation to obtain an estimated upper bound that holds with high probability (e.g., via the Markov inequality), and then plug-in this estimated bound into our algorithm.\nA rigorous analysis of these costs is likely complex, but it is certainly a worthwhile direction for future work. In particular, we note that the assumption of finite variance with a known constant is also common in other quantum mean estimation applications, such as stochastic optimization [5]. Therefore, relaxing these assumptions could be beneficial, potentially strengthening the results in these contexts as well.\n\n\n\n**Validity of the assumptions on finance and optimization applications:**\nThe smoothness assumption is commonly satisfied in finance (particularly in option pricing) and optimization problems. In such contexts, the function $g$ is typically smooth or piecewise linear [6]. It is not always the case, though, especially when $g$ could be a Heaviside function [3, 4].\n\nThe finiteness of the second moment with a known constant also holds in many applications, as seen in [5, 7, 8]. In practice, it usually can be verified when the function is bounded (for instance, when $g$ represents a risk or payoff that is inherently bounded) or when the random variables $(X,Y)$ live in a  compact space (e.g., $[0,1]^2$). However, we acknowledge that these assumptions may not always hold, or at least may be difficult to verify outside of these scenarios.\n\n**Other applications on non-linear functionals**: \n\nThank you for the question. The main idea is that the problem should have a compositional structure (such as the inside and outside expectations in our case), which allows us to leverage an effective resource allocation strategy.\n\nThere are potential generalizations relevant to optimization that we have in mind: the first is the Conditional Stochastic Optimization (CSO) problem [7], where the goal is to optimize $\\max_x F(x)$, and each $F(x)$ corresponds to a nested expectation. Our algorithm can be directly applied to estimate $\\hat{F}(x)$ for $F(x)$. This estimate can then be combined with gradient descent (if $F$ is strongly convex and $x$ belongs to a continuous space) or with quantum maximum finding (if $x$ is from a discrete set). Similarly, our method might also be useful for Stochastic Composition Optimization (SCO) [9].\n\nThanks again for your valuable feedback!\n\n\n[1] On nesting Monte Carlo estimators, Rainforth et. al., ICML 2018.\n\n[2] Optimal randomized multilevel Monte Carlo for repeatedly nested expectations, Syed and Wang, ICML 2023.\n\n[3] Multilevel Nested Simulation for Efficient Risk Estimation, Giles and Haji-Ali, SIAM Journal on Uncertainty Quantification 2019.\n\n[4] Nested Simulation in Portfolio Risk Measurement, Gordy and Juneja, Management Science, 2010.\n\n[5] Quantum speedups for stochastic optimization, Sidford and Zhang, NeurIPS 2023.\n\n[6] Multilevel Simulation of Functionals of Bernoulli Random Variables with Application to Basket Credit Derivatives, Bujok et. al., Methodology and Computing in Applied Probability, 2013.\n\n[7] Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning, Hu et. al., NeurIPS 2020. \n\n[8] Bias-Variance-Cost Trade-off of Stochastic Optimization, Hu et. al., NeurIPS 2021.\n\n[9] Accelerating stochastic composition optimization, Wang et. al., JMLR 2017."}, {"review_id": "T0d0O1pMxi", "reviewer": "Reviewer_ZtmP", "summary": "The main focus of this submission is the estimation of non-linear functions of probability distributions. More specifically, the authors proposed quantum algorithms based on an MLMC framework to estimate nested expectations. This proposed quantum algorithm improved upon the previous best-known quantum algorithm (Due to An et al in 2021), and it achieves optimal complexity. The core of the algorithm (and the source of the quantum speedup) is from the quantum mean estimation algorithm by Kothari and O'Donnell in 2023.", "questions": "1. In Section 1.1, the authors listed four potential applications, but in Section 4, only three of them were discussed. What about the conditional stochastic optimization?\n\n2. The algorithm assumes constants $V$ and $S$ are known. In applications such as Bayesian experiment design, EVPPI, and CoC option pricing, how are these constants readily known?\n\n3. Line 190: Maybe the authors should provide some intuition about the garbage register. I know what they are, but people not familiar with quantum computing might be confused.\n\nMinor comment: the quality of Figure 1 is pretty low. Maybe the authors should consider using a better image.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This submission is very well-written. I personally appreciate Section 3.1, where a high-level overview of the main contributing factors of the complexity, as well as the intuition of the MLMC structure. I believe this is beneficial to the readers not familiar with quantum MCMC-type algorithms. \n\nIn terms of results, the main strength of this submission is the newly designed MLMC sequence, which enables the use of quantum mean estimation to estimate the expectation of each level (outside quantum), which further uses quantum mean estimation (inside quantum). For applications with nested expectations, it is quite natural to use quantum mean estimation inside quantum mean estimation.", "was_revised": true, "final_justification": "Final score: 5\n\nMy questions have been addressed in the rebuttal. I keep my positive score.", "rebuttal": "We thank the reviewer for the positive feedback! We are encouraged that the reviewer thinks our paper is well-written and clear.\n\nWe address the questions raised below:\n\n**Conditional stochastic optimization**: Good point. Conditional stochastic optimization (CSO) focuses on solving $\\max_x F(x)$, where each fixed $x$ involves a nested expectation. We did not include this in Section 4 of the submitted version, as it introduces an additional layer of complexity (optimization) beyond straightforward nested expectations in other applications and was also excluded due to space limitations. \n\nFollowing the suggestion, we will provide a rigorous formulation of the CSO in the revise version. We will include details on the space of $x$ and assumptions on $F$, and explain how our results lead to improvements over classical results.\n\n**Constant in these applications**: Thanks for the question. We acknowledge that the assumption on a known upper bound for the second moment may not always hold, or difficult to verify in many cases. In practice, it usually can be verified when the function is bounded (for instance, when $g$ represents a risk or payoff that is inherently bounded) or when the random variables $(X,Y)$ live in a  compact space (e.g., $[0,1]^2$). \n\nAn interesting direction for future research is to relax the assumption of known constants to simply requiring finiteness (i.e., $< \\infty$; see also our response to reviewer hqsW). In particular, we note that the assumption of finite variance with a known constant is also common in other quantum mean estimation applications, such as stochastic optimization [5]. Therefore, relaxing these assumptions could be beneficial, potentially strengthening the results in these contexts as well.\n\n**Explain garbage register**: Thanks! We will do this in the revised version.\n\n**Better Figure 1**: Thank you for the comment! We will revise Figure 1 in the updated version to ensure it is clearer and more informative.\n\n[1] Quantum speedups for stochastic optimization, Sidford and Zhang, NeurIPS 2023."}, {"review_id": "5X6yE402x4", "reviewer": "Reviewer_H1SM", "summary": "This paper proposes a quantum algorithm for non-linear nested expectation values The approach builds upon quantum-accelerated Monte Carlo, which provides a quadratic speedup for multi-level Monte Carlo (MLMC) methods. The main innovation is the use of quantum-inside-quantum, which allows their algorithm to retain the quadratic speedup in contrast to a naive application of quantum-accelerated MLMC. It is shown that the algorithm achieves near-optimal complexity of $\\widetilde{O}(1/\\epsilon)$. Several applications of nested expectations are briefly mentioned.", "questions": "- While the algorithm is optimal due to the worst-case lower bound for mean approximation, are there any applications where the best known classical algorithm has cost strictly greater than $\\mathcal{O}(1/\\epsilon^2)$, i.e., the quantum algorithm achieves more than a quadratic speedup in practice?\n- The main innovation of this paper is that both the outer and inner loops of classical MLMC for nested expectations must be accelerated to achieve the full quadratic speedup. However, intuitively it seems like nested loops should be able to be unraveled into a single loop, in the same way that a quantum-inside-quantum algorithm can be viewed as a single quantum algorithm. Is there a way to re-interpret Q-NestExpect as a singly quantum-accelerated Monte Carlo algorithm?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The problem of non-linear nested expectations is an interesting one with several real-world applications. The question of whether quantum computers can provide a quadratic speedup is a very natural and non-trivial one, requiring some technical innovations.\n- The discussion of why quadratic speedup is lost when naively applying quantum-accelerated Monte Carlo is very insightful. \n- The idea of quantum-inside-quantum appears to be a useful idea that may have applications elsewhere.\n\n## Weaknesses\n- (Minor typo?) On page 2, it looks like $\\gamma$ and $\\psi$ are both being used to represent the conditonal expectation of $\\phi(x,Y)$.\n- As it stands, Figure 1 is a bit difficult to interpret and could be improved. I suppose the idea here is that QA-MC is being \"distributed\" more evenly in Q-NestExpect compared to QA-MLMC, but this is somewhat vague and hard to understand.\n- While it is not a major issue, I think this paper could benefit from some numerics to validate the theoretical findings.\n- In the context of quantum algorithms, a quadratic speedup is theoretically interesting but practically disappointing since the overhead of error correction is expected to outweigh any possible quantum advantage.", "was_revised": true, "final_justification": "I think this paper has a result that is both theoretically interesting and potentially relevant for quantum applications. Considering the importance of MCMC, showing how to obtain quadratic speedups using quantum-accelerated MCMC for nonlinear problems is valuable and may be useful more broadly in areas outside of the quantum algorithms community.", "rebuttal": "We thank the reviewer for the positive feedback! We are encouraged that the reviewer thinks the problem is interesting and the discussion is insightful. We address the questions below:\n\n\n**Better than quadratic speedup**: Great question. We are also very interested in exploring this further. Currently, we don’t have concrete examples or applications. The main challenge is that all the subroutines so far rely on Grover’s search, which offers at most a quadratic speedup. However, in these multilevel problems, the allocation of computational resources also impacts the total cost, so there may still be some potential that a superquadratic speedup comes from (quadratic speedup on all the subroutines + an overall more efficient allocation strategy). \n\nA side note is, there are many Monte Carlo problems that have worse than $O(\\epsilon^{-2})$ cost. The simplest one is to estimate the expectation of a heavy-tailed distribution with finite $(1+\\delta)$-th moment but not 2nd moment. However, in that case, the quantum algorithm can still only provide a quadratic speedup (their corresponding cost will also be slower than the typical $O(\\epsilon^{-1})$ [1]. \n\n\n**One single loop?**: Good point. Currently, we believe the Q-NESTEXPECT algorithm cannot be reinterpreted as a single quantum-accelerated Monte Carlo algorithm without sacrificing its performance advantage. The Q-NESTEXPECT algorithm is built on improving the classical MLMC method, which itself isn’t a single loop (the core idea of MLMC is to break the target quantity into components and estimate each piece separately). This splitting strategy is crucial to the performance advantage of MLMC compared to simpler nested Monte Carlo methods [2].\nThus, if a classical design were to achieve the same performance as MLMC using a single loop, there might be a possibility to design a quantum algorithm (or reinterpret our existing algorithm) as a single quantum-accelerated Monte Carlo algorithm. However, this is not the case as of now.\n\n\n\n\n\n**Typo**: Thanks for catching this! We will fix in the revised version.\n\n**Better Figure 1**:  Thank you for the comment. As suggested (and also suggested by reviewer ZtmP), we will revise Figure 1 in the updated version to ensure it is clearer and more informative. We will also include additional explanations to help readers interpret the figure more easily.\n\n\n\n[1] Quadratic Speed-up in Infinite Variance Quantum Monte Carlo, Blanchet et. al. 2024.\n\n[2] On nesting Monte Carlo estimators, Rainforth et. al., ICML 2018."}, {"review_id": "ABKKlM84jo", "reviewer": "Reviewer_QYbp", "summary": "The paper provides a quantum algorithm for the Monte-Carlo estimation of nested quantities. This nested MC considers the evaluation of an expectation value of a function that depends on another expectation value.", "questions": "Is it possible to reason about the implications for end-to-end advantages?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: The quantum algorithm achieves the near-optimal result 1/eps via a clever distribution of the error to the parts of the Monte Carlo estimation and the quantum subroutines. The paper contains a mathematical solid discussion of the algorithm and its guarantees. The paper is an important result about the various ways to use amplitude amplification and estimation towards practical applications. It has implications to several domains such as finance, AI, and optimization. \n\nWeaknesses: The paper is fully theoretical and does not contain numerics. However, the fundamental nature of the work and the results justify this presentation. The paper relies on the inputs given via oracles, which is standard for similar works, but leaves end-to-end advantages for future work.", "was_revised": true, "final_justification": "It is a solid work that advances the research on where amplitude amplification/estimation could lead to polynomial quantum advantages.", "rebuttal": "We thank the reviewer for their positive assessment and insightful comments. We are delighted the reviewer recognized the technical strength and potential impact of our work. \n\nThe reviewer is correct in noting that our work uses the standard oracle model. A full end-to-end speedup, which includes the oracle construction, should be theoretically feasible. Theoretically, an end-to-end speedup depends on efficient state preparation. Assuming we have access to a classical algorithm that prepares the underlying distribution of \\$X\\$ and \\$Y \\mid X\\$ (which is practical in the applications we considered), we can convert it into a quantum oracle using classical Toffoli and NOT gates with constant overhead [1]. In practice, it will involve additional complexities, particularly around error correction. \n\nWe will include more discussions on end-to-end advantages in the revised version. Thanks again for the valuable feedback, we remain available for further questions.\n\n[1] Logical reversibility of computation, Bennett, IBM journal of Research and Development, 1973."}, {"review_id": "oog7tjvJe1", "reviewer": "Reviewer_BADi", "summary": "This paper studies the nested expectation estimation problem and proposes a new quantum algorithm that achieves a quadratic quantum speedup over the classical multi-level Monte Carlo method. It also improves the previous QA-MLMC by An et al.", "questions": "Why does the equation below Line 544 hold?\n\nWhich assumptions in Lines 166-175 are possible to relax?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: This paper is well-written and all the theorems/lemmas are mathematically sound to me. The new quantum algorithm enhances the previous QA-MLMC in two aspects: 1. It utilizes a state-of-the-art quantum mean estimation procedure that has several beneficial properties compared to the version used by An et al. 2. In the conditional expectation estimation phase, directly applying An et al. employs a classical procedure, while the new quantum algorithm integrates the quantum mean estimation.This reduces the complexity from $\\epsilon^{-1.5}$ to $\\epsilon^{-1}$, which is optimal in quantum.\n\nWeaknesses: First, the idea of the new quantum algorithm is quite natural and straightforward (although the analysis contains some non-trivial work). More specifically, the improvement over QA-MLMC highly depends on the structure of the problem studied in this paper. Therefore, the technical contribution of this paper is relatively weak. Second, the previous work, QA-MLMC, has wider applications than the algorithm in this paper. To apply the algorithm proposed in this paper, five assumptions are required; however, these may not hold in certain practical scenarios. To strengthen this paper, it would be better to provide more detailed discussions regarding the applications in  Bayesian experiment design, EVPPI, and CoC. More specifically, it may provide more explicit calculations regarding the costs and speedups by taking into account certain practical parameters of these problems.", "was_revised": true, "final_justification": "I agree with the authors that this paper presents a new \"quantum-quantum\" structure for MLMC, which could be useful in certain specific research areas. However, the technical contributions remain weak, and the algorithm might have limited practical impact. Therefore, I believe this paper is on the borderline of acceptance.", "rebuttal": "We thank the reviewer for the careful reading! We are encouraged that the reviewer thinks the paper is well-written and mathematically sound. We address the questions below: \n\n**On Technical Contribution and Originality**\n\nWe appreciate and agree the reviewer's perspective that the high-level idea is natural. \n\nWe would like to clarify that our primary technical contribution is not simply the substitution of a procedure with a quantum counterpart, but the development of a new \"quantum-inside-quantum\" structure that is necessary to achieve the optimal speedup. \n\nFrom a complexity-theoretic standpoint, our work helps characterize the quantum query complexity of this problem by providing a near-optimal algorithm, which provides new insights to understand this problem. \n\nFrom the method perspective, the previous QA-MLMC algorithm applies quantum speedup only at the \"outer\" level. A direct application of this method to our problem results in a suboptimal cost of $\\tilde O(\\epsilon^{−1.5})$ because the cost of the classical inner-level estimators grows too quickly. Our key insight is that one must redesign the MLMC levels themselves by creating a new sequence of quantum subroutines that leverage quantum estimation for the inner conditional expectation. We believe this demonstrates a novel design pattern for quantum MLMC that is a valuable methodological improvement beyond prior work.\n\n**Comparison with QA-MLMC**\nThe reviewer correctly notes that our algorithm is more specialized than the general QA-MLMC framework. This was a deliberate trade-off. Our goal was to demonstrate that for the important class of nested expectation problems, a full quadratic speedup is achievable. We have traded generality for optimality in this critical domain.\n\n**Assumptions**\n\nGreat point. Among the five assumptions, assumption 4-5 are essential to setup the problem, and is explicitly or implicitly assumed in the relevant literature that we are aware of.\n\nRegarding assumption 1-3, we acknowledge that they may not hold perfectly or may be hard to check in some practical scenarios. Nevertheless, they are also standard assumptions in both the classical and quantum literature, for example, the smoothness assumption is made in [1-6]. That said, we agree with the reviewer that these assumptions may not hold in certain applications. \n\nFollowing the reviewer's suggestion, we will expand Section 4 in our revision. *We will provide more explicit cost calculations for applications like EVPPI*, detailing how practical parameters influence the overall speedup and making the significance of our result more concrete. We also discuss possible ways to relax these assumptions (see the response to the last question), and will comment on them in the revised version.\n\n**Derivation of line 544**:\nWe first note that $\\mathbb E_{Y\\mid X}[S_{\\text{E}}] = \\mathbb E_{Y\\mid X}[S_{\\text{O}}] = 2^{l-1}\\mathbb E_{Y\\mid X}[\\phi(X,Y)]$ (by our definition in Algorithm 1). Therefore,\n\n$$\\mathbb E_{Y\\mid X}\\left[\\left\\lVert\\frac{1}{2^l} (S_{\\text{E}} + S_{\\text{O}})  - \\mathbb E_{Y\\mid X}[\\phi(X,Y)] \\right\\rVert\\right] \\leq \\mathbb E_{Y\\mid X}\\left[\\left\\lVert\\frac{1}{2^l} (S_{\\text{E}} + S_{\\text{O}})  -  \\mathbb E_{Y\\mid X}[\\phi(X,Y)]\\right\\rVert^2\\right]^{0.5} $$\n\nby Cauchy-Schwarz. The right-hand side further simplifies to $\\lVert Var_{Y\\mid X}\\left[\\frac{1}{2^l}(S_{\\text{E}} + S_{\\text{O}})  -\\mathbb E_{Y\\mid X}[\\phi(X,Y)]\\right]\\rVert_1$ (since the random vector inside has an expectation of 0 for each coordinate, so its second moment equals the variance). Here, variance of a random vector is taken on each coordinate, just as we did for expectation. Note that there is a typo in the right-hand side of the first inequality under line 544, where there is an additional $\\lVert \\cdot \\rVert$ in the variance. It should be $\\lVert \\cdot \\rVert_1$ outside the variance. We'll fix this typo in the revision.\n\nSince given $X$, $\\mathbb E_{Y\\mid X}\\left[\\phi(X,Y)]\\right]$ is a constant that does not change the variance, we can further simply the variance term to $Var_{Y\\mid X}\\left[\\frac{1}{2^l}(S_{\\text{E}} + S_{\\text{O}})]\\right]$. \n\nWe further claim $$ Var_{Y\\mid X}\\left[\\frac{1}{2^l}(S_{\\text{E}} + S_{\\text{O}})]\\right]  = \\frac 1 {2^l} Var_{Y\\mid X}(\\phi(X, Y)),$$\nbecause both $S_{\\text{E}}$ and $S_{\\text{O}}$ are sum of $2^{l-1}$ i.i.d. random vectors each has the same distribution as $\\phi(X,Y)$, therefore averaging over $2^l$ i.i.d. copy reduce the variance of each copy by a factor of $2^{-l}$. Plugging into the earlier inequality,\n\n$$\\mathbb E_{Y\\mid X}\\left[\\left\\lVert\\frac{1}{2^l} (S_{\\text{E}} + S_{\\text{O}})  - \\mathbb E_{Y\\mid X}[\\phi(X,Y)]] \\right\\rVert\\right]  \\leq \\frac{1}{2^{l/2}} \\lVert Var_{Y\\mid X}(\\phi(X,Y))\\rVert_1^{0.5} \\leq \\frac{m^{0.5} V^{0.5}}{2^{l/2}}$$ by Assumption 2. \n \n \n**Which assumptions are possible to relax**:\n\nThe question is also asked by reviewer hqsW. There are essentially two types of technical assumptions appeared in the current version: \n1) *Smoothness assumption (Assumption 1);* \n2) *Moment assumption (Assumption 2,3).* \n\nWe discuss them separately.\n\n*Regarding the smoothness assumption*: It is indeed possible to generalize this assumption. Additional knowledge about the functions or the underlying distribution could further relax the continuity requirement. In classical Monte Carlo literature, there are studies on nested expectations where the function $g$ in our notation is a Heaviside function [7,8]. The idea of their assumptions is to assume that the underlying distribution behaves appropriately at the discontinuous points, ensuring that it does not cause issues.\nIn summary, there is a tradeoff between the assumptions on distributions and the regularity assumptions on the functions. Stronger distributional assumptions and/or extra knowledge on the function can lead to weaker assumptions on its smoothness, and vice versa. If we use the same distribution assumptions as in [3,4] and assume $g$ is a Heaviside function, we could still get the quadratic speedup. \n\n*On the necessity of finite second moments:* A finite second moment may be required to achieve a complexity of $\\tilde{O}(\\epsilon^{-1})$. Reference [9] shows, even in the context of standard Monte Carlo estimation, assuming only the existence of a $(1 + \\delta)$-th moment with $\\delta \\in (0,1)$ is insufficient for attaining $\\tilde{O}(\\epsilon^{-1})$ cost with a quantum algorithm (but a quadratic speedup still exists). Therefore one may still hope for a quadratic speedup for the nested expectation problem without finite second moment, however, the quantum algorithm's cost will also be worst than $\\tilde{O}(\\epsilon^{-1})$.\n\n*On the known constants for the second moment/variance:* There exists an interesting intermediate regime where the assumption (1-2) could be replaced by $<\\infty$ (instead of the conditions $\\leq V$ and $\\leq S$, where $V$ and $S$ are constants known to the users in advance.) Right now we do not know if we can design a quantum algorithm to achieve $\\tilde O(\\epsilon^{-1})$ cost in this relaxed assumption. \nOne potential approach is to first perform a low-cost Monte Carlo estimation to obtain an estimated upper bound that holds with high probability (e.g., via the Markov inequality), and then plug-in this estimated bound into our algorithm.\nA rigorous analysis of these costs is likely complex, but it is certainly a worthwhile direction for future work. In particular, we note that the assumption of finite variance with a known constant is also common in other quantum Monte Carlo applications, such as stochastic optimization [4]. Therefore, relaxing these assumptions could be beneficial, potentially strengthening the results in these contexts as well.\n\nWe hope these responses clarifies your concerns and questions. Thanks again for your valuable feedback! \n\n\n\n\n[1] On nesting Monte Carlo estimators, Rainforth et. al., ICML 2018.\n\n[2] Multilevel Simulation of Functionals of Bernoulli Random Variables with Application to Basket Credit Derivatives, Bujok et. al., Methodology and Computing in Applied Probability, 2013.\n\n[3] Optimal randomized multilevel Monte Carlo for repeatedly nested expectations, Syed and Wang, ICML 2023\n\n[4] Quantum speedups for stochastic optimization, Sidford and Zhang, NeurIPS 2023.\n\n[5] Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning, Hu et. al., NeurIPS 2020. \n\n[6] Bias-Variance-Cost Trade-off of Stochastic Optimization, Hu et. al., NeurIPS 2021.\n\n[7] Multilevel Nested Simulation for Efficient Risk Estimation, Giles and Haji-Ali, SIAM Journal on Uncertainty Quantification 2019.\n\n[8] Nested Simulation in Portfolio Risk Measurement, Gordy and Juneja, Management Science, 2010\n\n[9] Quadratic Speed-up in Infinite Variance Quantum Monte Carlo, Blanchet et. al. 2024."}]

Author rebuttal:

Meta-review: Consider the problem of estimating a nested expectation. This paper proposes a quantum algorithm with cost $\tilde{O}(\epsilon^{-1})$. Previously, the best-known classical MLMC algorithm has a cost of $\tilde{O}(\epsilon^{-2})$, and the best-known quantum algorithm, QA-MLMC (An et al., 2021), has a cost of $\tilde{O}(\epsilon^{-1.5})$.

The paper is very well written, with an inspiring discussion of the ideas in previous and current works. The problem considered is adequately important, and the improvement over existing work is significant. Reviewer BADi correctly pointed out that the application of the proposed algorithm is more restrictive than that of QA-MLMC by An et al. (2021). Nevertheless, I believe this paper is already worthy of publication given its contribution to the specific problem of nested expectation estimation. The other reviewers also appear to be positive about this paper.

Given the above, I suggest accepting this paper as a spotlight.
Decision: Accept (spotlight)