total}R\right)=\widetilde{O}\left(T^{2}\mathcal{T}_{\rm
total}(e^{2n}C)^{7d/2n}R^{2}\left(\frac{5^{T}}{\epsilon}\right)^{1+7d/2n}\right).\qed$

A similar result can be obtained for the classical LSM algorithm. Similarly to
Theorems 3.14 and 4.5, Algorithm 1, by using the same bounds on $\lambda$ (Eq.
(15)), outputs $\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}$
such that, for any $\epsilon_{0}\in(0,1/2]$,

$\displaystyle\begin{multlined}\operatorname{Pr}\left[\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{1}}]\big{|}\geq
5^{T}\left(3m\epsilon_{0}R+\operatorname*{\max}_{0<t<T}\operatorname*{\min}_{a\in\mathbb{R}^{m}}\|a\cdot\vec{e}_{t}(X_{t})-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\right)\right]\\\
\leq
4me^{-2N\epsilon_{0}^{2}/m},\end{multlined}\operatorname{Pr}\left[\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{1}}]\big{|}\geq
5^{T}\left(3m\epsilon_{0}R+\operatorname*{\max}_{0<t<T}\operatorname*{\min}_{a\in\mathbb{R}^{m}}\|a\cdot\vec{e}_{t}(X_{t})-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\right)\right]\\\
\leq 4me^{-2N\epsilon_{0}^{2}/m},$

in time $O(TmN+TN(\mathcal{T}_{\rm
samp}+\mathcal{T}_{z}+m\mathcal{T}_{e}))=O(TmN\mathcal{T}_{\rm total})$, where
$O(TmN)$ comes from computing $\widetilde{b}_{t}$, $t\in[T-1]$. The term
$4me^{-2N\epsilon_{0}^{2}/m}$ comes from the Chernoff bounds
$\operatorname{Pr}[|(b_{t})_{j}-(\widetilde{b}_{t})_{j}|\geq\epsilon/\sqrt{m}]\leq
2e^{-2N\epsilon^{2}/m}$ for all $j\in[m]$, and
$\operatorname{Pr}[|\widetilde{Z}_{\widetilde{\tau}_{1}}-\mathbb{E}[Z_{\widetilde{\tau}_{1}}]|\geq\epsilon]\leq
2e^{-2N\epsilon^{2}}$ (note that there is no Chernoff bound related to
matrices $A_{t}$). The application of the Jackson-like inequality is the same
as in the previous theorem. By taking
$N=\lceil\frac{m}{2\epsilon_{0}^{2}}\log(4m/\delta)\rceil$ and the same
parameters $q=\lceil(3\cdot 5^{T}C/\epsilon)^{1/n}\rceil$ and
$\epsilon_{0}=\frac{1}{3C^{d/n}e^{d}R}\big{(}\frac{\epsilon}{3\cdot
5^{T}}\big{)}^{1+d/n}$ as before, the final complexity is

$\displaystyle O(TmN\mathcal{T}_{\rm
total})=O\left(\frac{Tm^{2}}{\epsilon_{0}^{2}}\mathcal{T}_{\rm
total}\log(m/\delta)\right)=\widetilde{O}\left(T\mathcal{T}_{\rm
total}(e^{2n}C)^{4d/n}R^{2}\left(\frac{5^{T}}{\epsilon}\right)^{2+4d/n}\right),$

up to the $\log(m/\delta)$ factor.

In the particular case when the Markov chain follows a Brownian motion,
approximating the matrices by the identity matrix not only leads to a
simplification of the LSM algorithm, but bounds the minimum singular values
that showed up in previous complexities by a constant (to be more
specifically, by $\sigma_{\rm min}=1$). Even more, there is a mild improvement
on the final classical and quantum complexities to
$\widetilde{O}((5^{T}/\epsilon)^{2+4d/n})$ and
$\widetilde{O}((5^{T}/\epsilon)^{1+7d/2n})$, respectively. Still, if the
continuation values are $n$-differentiable for
$n=\Theta(\log(5^{T}/\epsilon)/\log\log(5^{T}/\epsilon))$, there is a quantum
quadratic improvement in the runtime. Finally, we must mention that, even
though we bounded the minimum singular value by a constant, there is still a
hidden dependence on $\epsilon$ in the parameter $C\geq
C_{d,\lambda}\max_{0\leq
t<T}\|\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]|_{Q_{d}(\lambda)}\|_{C^{n}(Q_{d}(\lambda))}$,
since the constant $C_{d,\lambda}$ in the Jackson-like inequality might depend
on the size of the cube $\lambda$. This is the reason why we cannot take
$\lambda\to\infty$ in the previous theorem.

###  4.2 Geometric Brownian motion

We now consider a Markov chain $(X_{t})_{t=0}^{T}$ where each component of
$X_{t}:\Omega\to\mathbb{R}^{d}$ follows an independent geometric Brownian
motion. A geometric Brownian motion is a stochastic process
$S=(S_{t})_{t=0}^{T}$ such that $S_{t}=e^{W_{t}-t/2}$, where
$(W_{t})_{t=0}^{T}$ is a standard Brownian motion.111More generally,
$S_{t}=S_{0}e^{\sigma W_{t}+t(\mu-\sigma^{2}/2)}$, but we shall assume
$S_{0}=1$, $\sigma=1$ and $\mu=0$ here for simplicity. The probability density
function of a geometric Brownian motion is $f_{t}(s)=\frac{1}{\sqrt{2\pi
t}s}\exp\big{(}-\frac{(\ln{s}+t/2)^{2}}{2t}\big{)}$, and thus the image
probability measure $\rho_{t}$ of $X_{t}$ reads
$\rho_{t}(x)=\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi
t}x_{i}}\exp\big{(}-\frac{(\ln{x_{i}}+t/2)^{2}}{2t}\big{)}$ for $t\in[T]$.
Given $t\in[T]$, consider the approximation architecture generated by
$\\{e_{t,\vec{k}}:\mathbb{R}^{d}\to\mathbb{R}\\}_{\vec{k}\in\\{0,\dots,q\\}^{d}}$
for some integer $q\geq 0$, where
$e_{t,\vec{k}}(x)=\prod_{i=1}^{d}x_{i}^{k_{i}}e^{-k_{i}(k_{i}-1)\frac{t}{2}}$.
Given this choice of functions, we have that

$\displaystyle\mathbb{E}[e_{t,\vec{k}}(X_{t})e_{t,\vec{l}}(X_{t})]$
$\displaystyle=\prod_{i,j=1}^{d}e^{(k_{i}-k_{i}^{2}+l_{j}-l_{j}^{2})\frac{t}{2}}\mathbb{E}[X_{t,i}^{k_{i}}X_{t,j}^{l_{j}}]$
$\displaystyle=\left(\prod_{i=1}^{d}e^{(k_{i}-k_{i}^{2}+l_{i}-l_{i}^{2})\frac{t}{2}}e^{((k_{i}+l_{i})^{2}-(k_{i}+l_{i}))\frac{t}{2}}\right)\left(\prod_{i\neq
j}^{d}e^{(k_{i}-k_{i}^{2}+l_{j}-l_{j}^{2})\frac{t}{2}}e^{k_{i}(k_{i}-1)\frac{t}{2}}e^{l_{j}(l_{j}-1)\frac{t}{2}}\right)$
$\displaystyle=\prod_{i=1}^{d}e^{k_{i}l_{i}t}$

using that the $n$-th moment of a log-normally distributed variable $Y$ is
$\mathbb{E}[Y^{n}]=e^{n(n-1)\frac{t}{2}}$ [53, Equation (14.7)]. This means
that the matrices $A_{t}$, $t\in[T-1]$, with entries
$(A_{t})_{\vec{k},\vec{l}}=\mathbb{E}[e_{t,\vec{k}}(X_{t})e_{t,\vec{l}}(X_{t})]$
are given by

$\displaystyle\begin{bmatrix}1&1&1&\cdots&1\\\ 1&e^{t}&e^{2t}&\cdots&e^{qt}\\\
1&e^{2t}&e^{4t}&\cdots&e^{2qt}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&e^{qt}&e^{2qt}&\cdots&e^{q^{2}t}\end{bmatrix}^{\otimes d},$ (20)

i.e., they are tensor power of Vandermonde matrices. By using the following
result (already generalized for $d>1$), we can bound the minimum singular
value of $A_{t}$.

######  Lemma 4.6 ([38, Lemma 4]).

The minimum singular value $\sigma_{\min}(A_{t})$ of the matrix $A_{t}$ in Eq.
(20) is such that

$\displaystyle\frac{1}{\sigma_{\min}(A_{t})}\leq
e^{2ed/(e^{t}-1)^{2}}q^{d}(q+1)^{d}\left(\frac{e^{t}}{e^{t}-1}\right)^{qd}\leq
e^{3qd}q^{2d}.$

We shall use the matrices in Eq. (20) within our Algorithm 2, similarly to
what we did with the identity matrix in the Brownian motion section. Once
again, in order to use the Jackson-like inequality in Lemma 4.1, we must
restrict the domain to a close set like $Q_{d}(\lambda)$. We consider the
approximation architecture generated by $\\{e^{\rm
trunc}_{t,\vec{k}}:\mathbb{R}^{d}\to\mathbb{R}\\}_{\vec{k}\in\\{0,\dots,q\\}^{d}}$
with $e^{\rm
trunc}_{t,\vec{k}}(x)=\prod_{i=1}^{d}x_{i}^{k_{i}}e^{-k_{i}(k_{i}-1)\frac{t}{2}}$
if $x\in Q_{d}(\lambda)$ and $e^{\rm trunc}_{t,\vec{k}}(x)=0$ otherwise. The
implied matrix $A^{\rm trunc}_{t}$ is no longer equal to the matrix in Eq.
(20), but is close to it. Such closeness will be bounded with the aid of the
following simple result. The vector $b_{t}$, $t\in[T-1]$, will still be
approximated using quantum algorithm for Monte Carlo, which, in turn, must use
a discretization of the geometric Brownian motion.

######  Lemma 4.7.

Given $\lambda>0$ and $k\in\mathbb{N}$, then

$\displaystyle\int_{\lambda}^{\infty}\frac{x^{k-1}}{\sqrt{2\pi
t}}e^{-\frac{(\ln{x}+t/2)^{2}}{2t}}\text{d}x\leq\frac{1}{2}e^{\frac{t}{2}k(k-1)-\frac{1}{2t}\big{(}{\ln\lambda}-t(k-\frac{1}{2})\big{)}^{2}}.$

###### Proof.

$\displaystyle\int_{\lambda}^{\infty}\frac{x^{k-1}}{\sqrt{2\pi
t}}e^{-\frac{(\ln{x}+t/2)^{2}}{2t}}\text{d}x=\frac{e^{k(k-1)\frac{t}{2}}}{\sqrt{\pi}}\int_{\frac{\ln\lambda}{\sqrt{2t}}-\sqrt{\frac{t}{2}}(k-\frac{1}{2})}^{\infty}e^{-x^{2}}\text{d}x\leq\frac{1}{2}e^{\frac{t}{2}k(k-1)-\frac{1}{2t}\big{(}{\ln\lambda}-t(k-\frac{1}{2})\big{)}^{2}},$

using the change of variables $x\to e^{\sqrt{2t}x+t(k-\frac{1}{2})}$ and that
$\frac{2}{\sqrt{\pi}}\int_{\lambda}^{\infty}e^{-x^{2}}\text{d}x\leq
e^{-\lambda^{2}}$ [90, 20]. ∎

Recall the definition of the truncation operator $\mathscr{T}_{\beta}$ and the
quantity

$\displaystyle
r_{p}:=T\sqrt{\frac{2M_{p}}{p-2}}+\operatorname*{\max}_{t\in[T-1]}\sum_{i=1}^{d}\mathbb{E}[|X_{t,i}|]=T\sqrt{\frac{2M_{p}}{p-2}}+d$

for $2<p<\infty$, where
$M_{p}:=\max\big{\\{}\|z_{1}\|_{L^{p}(\rho_{1})}^{p},\dots,\|z_{T}\|_{L^{p}(\rho_{T})}^{p}\big{\\}}$
and we used that $\mathbb{E}[|X_{t,i}|]=1$. For simplicity, the next theorem
only considers the case when the continuation values are in
$C^{n}(Q_{d}(\lambda))$. Moreover, we stress that
$L^{2}(\rho_{t})=L^{2}(\mathbb{R}^{d},\rho_{t})$ considers the whole space
$\mathbb{R}^{d}$.

######  Theorem 4.8.

Consider a Markov chain $(X_{t})_{t=0}^{T}$ where each component of
$X_{t}:\Omega\to\mathbb{R}^{d}$ follows an independent geometric Brownian
motion. Let $Q_{d}(\lambda)$ be the closed cube with side length $2\lambda$ in
$\mathbb{R}^{d}$ centered at the origin. Suppose
$M_{p}:=\max\big{\\{}\|z_{1}\|_{L^{p}(\rho_{1})}^{p},\dots,\|z_{T}\|_{L^{p}(\rho_{T})}^{p}\big{\\}}<\infty$
for some $2<p<\infty$. Within the setting of Algorithm 2 with parameters
$\delta$ and $\epsilon_{0}$, let the sampling cost of the Markov chain be
$T\mathcal{T}_{\rm samp}$, and set all matrices $\widetilde{A}_{t}$,
$t\in[T-1]$, to be the matrix in Eq. (20) and use the payoffs
$z_{0},\mathscr{T}_{\beta}z_{1},\dots,\mathscr{T}_{\beta}z_{T}$, where
$\beta:=\lambda^{2/p}$, with query cost $\mathcal{T}_{z}$ and
$R:=\max_{t\in[T]}\|\mathscr{T}_{\beta}z_{t}\|_{u}$. Also, for $t\in[T-1]$,
consider the approximation architectures $\mathscr{H}_{t}=\\{e^{\rm
trunc}_{t,\vec{k}}:\mathbb{R}^{d}\to\mathbb{R}\\}_{\vec{k}\in\\{0,\dots,q\\}^{d}}$,
for some $q\geq 0$, where $e^{\rm
trunc}_{t,\vec{k}}(x)=\prod_{i=1}^{d}x_{i}^{k_{i}}e^{-k_{i}(k_{i}-1)\frac{t}{2}}$
if $x\in Q_{d}(\lambda)$ and $e^{\rm trunc}_{t,\vec{k}}(x)=0$ otherwise. Let
$\mathcal{T}_{e}$ be the query cost of $\mathscr{H}_{t}$, $t\in[T]$. Suppose
there is $n\in\mathbb{N}$, $n<q$, such that the restriction
$\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]|_{Q_{d}(\lambda)}$ to $Q_{d}(\lambda)$ of
each $\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]$, $t\in\\{0,\dots,T-1\\}$, is in
$C^{n}(Q_{d}(\lambda))$. Let $C\geq C_{d,\lambda}\max_{0\leq
t<T}\|\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]|_{Q_{d}(\lambda)}\|_{C^{n}(Q_{d}(\lambda))}$
be known, where $C_{d,\lambda}$ is a constant depending only on
$Q_{d}(\lambda)$. Then, for $\delta\in(0,1)$,
$\epsilon\in\big{(}0,5^{T}(2^{2d}C^{3d/n}R)^{n/(n+3d)}\big{]}$,
$q=\left\lceil(3\cdot 5^{T}C/\epsilon)^{1/n}\right\rceil$ and

(21)

if
$\epsilon_{0}=\frac{\exp(-27Td(5^{T}C/\epsilon)^{2/n})}{2^{2d+2}C^{5d/n}R}\left(\frac{\epsilon}{3\cdot
5^{T}}\right)^{1+5d/n}$, Algorithm 2 outputs
$\widetilde{\mathcal{U}}_{0}:=\max\big{\\{}Z_{0},\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}\big{\\}}$
such that

$\displaystyle\operatorname{Pr}\left[|\widetilde{\mathcal{U}}_{0}-\mathbb{E}[Z_{\tau_{0}}]|\leq\epsilon\right]\geq
1-\delta$

in time

$\displaystyle\widetilde{O}\left(T^{2}\mathcal{T}_{\rm
total}(2^{2n}C)^{15d/2n}e^{32Td(5^{T}C/\epsilon)^{2/n}}R^{2}\left(\frac{5^{T}}{\epsilon}\right)^{1+15d/2n}\right),$

where $\mathcal{T}_{\rm total}:=\mathcal{T}_{\rm
samp}+\mathcal{T}_{z}+\mathcal{T}_{e}$ and $\widetilde{O}(\cdot)$ hides
$\operatorname{polylog}$ terms in $5^{T},R,C,e^{d},\epsilon,\delta$.

###### Proof.

Let $\sigma_{\min}\leq\min_{t\in[T-1]}\sigma_{\min}(\widetilde{A}_{t})$, where
$\widetilde{A}_{t}$ is the matrix from Eq. (20), $t\in[T-1]$ and let
$L:=\max_{t\in[T-1],\vec{k}\in\\{0,\dots,q\\}^{d}}\|e^{\rm
trunc}_{t,\vec{k}}\|_{L^{2}(\rho_{t})}\leq e^{q^{2}Td/2}$. First we note that
Algorithm 2, when using the approximation architecture $\\{e^{\rm
trunc}_{t,\vec{k}}:\mathbb{R}^{d}\to\mathbb{R}\\}_{\vec{k}\in\\{0,\dots,q\\}^{d}}$
and parameters $\epsilon_{b}=\epsilon_{0}/\sqrt{m}$ and
$\delta_{b}=\delta/(2Tm)$ with $m:=(1+q)^{d}$ (there are no $\epsilon_{A}$ and
$\delta_{A}$ parameters), outputs
$\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}$ such that, for any
$\epsilon_{0}\in(0,\sigma_{\min}/2]$,

$\displaystyle\operatorname{Pr}\left[\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{1}}]\big{|}\geq
5^{T}\left(\frac{4\epsilon_{0}mRL^{2}}{\sigma_{\min}^{2}}+\operatorname*{\max}_{0<t<T}\operatorname*{\min}_{a\in\mathbb{R}^{m}}\|a\cdot\vec{e}_{t}(X_{t})-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\right)\right]\leq\delta,$

where $\vec{e}_{t}(\cdot):=(e^{\rm
trunc}_{t,\vec{k}}(\cdot))_{\vec{k}\in\\{0,\dots,q\\}^{d}}$, in time

$\displaystyle O\left(\frac{T^{2}m^{5/2}}{\epsilon_{0}}\mathcal{T}_{\rm
total}RL\log(T)\log(Tm/\delta)\log^{3/2}(\sqrt{m}RL/\epsilon_{0})\log\log(\sqrt{m}RL/\epsilon_{0})\right).$
(22)

The proof is exactly the same as the ones from Theorems 3.11 and 3.13, the
only difference being that the payoffs are now
$z_{0},\mathscr{T}_{\beta}z_{1},\dots,\mathscr{T}_{\beta}z_{T}$ and we must
show that the $L^{2}$-error between $A^{\rm trunc}_{t}$ and the matrix
$\widetilde{A}_{t}$ from Eq. (20) is $\|A^{\rm
trunc}_{t}-\widetilde{A}_{t}\|_{2}\leq\epsilon_{0}$. Indeed, the error
commited in any entry $\mathbb{E}[e^{\rm trunc}_{t,\vec{k}}(X_{t})e^{\rm
trunc}_{t,\vec{k}}(X_{t})]$, when approximating the matrix $A^{\rm trunc}_{t}$
by the one in Eq. (20), is at most

$\displaystyle\prod_{i=1}^{d}e^{k_{i}l_{i}t}-\prod_{i=1}^{d}\Bigg{(}e^{k_{i}l_{i}t}-$
$\displaystyle
e^{(k_{i}-k_{i}^{2}+l_{i}-l_{i}^{2})\frac{t}{2}}\int_{\lambda}^{\infty}\frac{x^{k_{i}+l_{i}-1}}{\sqrt{2\pi
t}}e^{-\frac{(\ln{x}+t/2)^{2}}{2t}}\text{d}x\Bigg{)}$
$\displaystyle\leq\left(\prod_{i=1}^{d}e^{k_{i}l_{i}t}\right)\sum_{j=1}^{d}e^{((k_{j}+l_{j})-(k_{j}+l_{j})^{2})\frac{t}{2}}\int_{\lambda}^{\infty}\frac{x^{k_{j}+l_{j}-1}}{\sqrt{2\pi
t}}e^{-\frac{(\ln{x}+t/2)^{2}}{2t}}\text{d}x$ (23)
$\displaystyle\leq\left(\prod_{i=1}^{d}e^{k_{i}l_{i}t}\right)\sum_{j=1}^{d}\frac{1}{2}e^{-\frac{1}{2t}\big{(}{\ln\lambda}-t(k_{j}+l_{j}-\frac{1}{2})\big{)}^{2}}$
(24)
$\displaystyle\leq\frac{d}{2}e^{q^{2}td-\frac{1}{2t}\big{(}{\ln\lambda}-t(2q-\frac{1}{2})\big{)}^{2}},$

where Eq. (23) follows from convexity and Eq. (24) from Lemma 4.7. Observe now
that, if $\ln\lambda\geq
t(2q-\frac{1}{2})+\sqrt{2q^{2}t^{2}d+\ln(md/2\epsilon_{0})}$, then the above
error is at most $\epsilon_{0}/m$, which implies $\|A^{\rm
trunc}_{t}-\widetilde{A}_{t}\|_{2}\leq\epsilon_{0}$. Regarding the complexity,
the most expensive steps are inverting $\widetilde{A}_{t}$, which requires
time $O(Tm^{\omega_{\ast}})$, and computing all $b_{t}$, which requires time

$\displaystyle O\left(\frac{Tm}{\epsilon_{b}}RL(T\mathcal{T}_{\rm
samp}+T(\log(T)\mathcal{T}_{z}+m\mathcal{T}_{e}))\log\left(\frac{1}{\delta_{b}}\right)\log^{3/2}\left(\frac{RL}{\epsilon_{b}}\right)\log\log\left(\frac{RL}{\epsilon_{b}}\right)\right),$

by calling
$\mathtt{QMonteCarlo}(Z_{\widetilde{\tau}_{t}}e_{t-1,\vec{k}}(X_{t-1}),\epsilon_{b},\delta_{b},RL)$
from Theorem 3.7 for $t\in\\{2,\dots,T\\}$ and
$\vec{k}\in\\{0,\dots,q\\}^{d}$. The term
$T(\log(T)\mathcal{T}_{z}+m\mathcal{T}_{e})$ comes from the unitaries
$C_{t}^{(\vec{k})}$ in $\mathtt{QMonteCarlo}$. Hence, by keeping the largest
terms of each complexity and using that $\epsilon_{b}=\epsilon_{0}/\sqrt{m}$
and $\delta_{b}=\delta/(4Tm)$, the final complexity is the one from Eq. (22).

With this partial result in hands, we again use the Jackson-type inequality
from Lemma 4.1 as in Theorem 4.3. In order to do so, we first need the
following technical result that limits the continuation values to being a
function in the domain $Q_{d}(\lambda)$. More specifically, by [107,
Proposition 3.14],

$\displaystyle\|\mathbf{1}_{Q_{d}(\lambda)}\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\leq
r_{p}\lambda^{2/p-1},$ (25)

where $\mathbf{1}_{Q_{d}(\lambda)}$ is the indicator random variable
corresponding to the set $Q_{d}(\lambda)$. Since $\\{e^{\rm
trunc}_{t,\vec{k}}\\}_{\vec{k}\in\\{0,\dots,q\\}^{d}}$ spans
$\mathcal{R}_{q}(Q_{d}(\lambda))$, the Jackson-type inequality from Lemma 4.1
reads

$\displaystyle\operatorname*{\min}_{a\in\mathbb{R}^{m}}\|a\cdot\vec{e}_{t}(X_{t})-\mathbf{1}_{Q_{d}(\lambda)}\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}=\operatorname*{\inf}_{p\in\mathcal{R}_{q}}\|(p-\mathbb{E}[Z_{\tau_{t+1}}|X_{t}])\mathbf{1}_{Q_{d}(\lambda)}\|_{L^{2}(\rho_{t})}\leq
Cq^{-n},$

for all $t\in\\{0,\dots,T-1\\}$. Combining both results, we finally get that

$\displaystyle\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{1}}]\big{|}\leq
5^{T}\left(\frac{4\epsilon_{0}mRL^{2}}{\sigma_{\min}^{2}}+Cq^{-n}+r_{p}\lambda^{2/p-1}\right),$

with probability at least $1-\delta$. Before we plug values for $m$, $q$,
$\epsilon_{0}$ and $\epsilon$, we get rid of the truncation operator
$\mathscr{T}_{\beta}$ in the inequality above by using that [32, Proposition
5.2]

$\displaystyle\|\mathbb{E}[Z_{\tau_{t+1}}|X_{t}]-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\leq
r_{p}\lambda^{1-p/2}$

(which is quite similar to Eq. (25)). By using that
$|{\max}\\{a_{0},a_{1}\\}-\max\\{a_{0},a_{2}\\}|\leq|a_{1}-a_{2}|$ with
$a_{0},a_{1},a_{2}\in\mathbb{R}$, then

$\displaystyle|\widetilde{\mathcal{U}}_{0}-\mathbb{E}[Z_{\tau_{0}}]|\leq\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[Z_{\tau_{1}}]\big{|}\leq
5^{T}\left(\frac{4\epsilon_{0}mRL^{2}}{\sigma_{\min}^{2}}+Cq^{-n}+2r_{p}\lambda^{2/p-1}\right),$

since $\lambda^{1-p/2}\leq\lambda^{2/p-1}$.

We shall now use that $m\leq 2^{d}q^{d}$, $q=\lceil(3\cdot
5^{T}C/\epsilon)^{1/n}\rceil$ and
$\lambda\geq(\frac{6r_{p}}{\epsilon})^{p/(p-2)}$. We also take

$\displaystyle\epsilon_{0}=\frac{e^{-27Td(5^{T}C/\epsilon)^{2/n}}}{2^{2d+2}C^{5d/n}R}\left(\frac{\epsilon}{3\cdot
5^{T}}\right)^{1+5d/n}\leq\frac{\sigma_{\min}^{2}}{2^{2d+2}C^{d/n}RL^{2}}\left(\frac{\epsilon}{3\cdot
5^{T}}\right)^{1+d/n},$

where we used that $\sigma_{\min}^{-2}\leq e^{6qd}q^{4d}=e^{6d\lceil(3\cdot
5^{T}C/\epsilon)^{1/n}\rceil}\lceil(3\cdot 5^{T}C/\epsilon)^{1/n}\rceil^{4d}$
according to Lemma 4.6 and the bound $L\leq
e^{q^{2}Td/2}=e^{\frac{Td}{2}\lceil(3\cdot 5^{T}C/\epsilon)^{1/n}\rceil^{2}}$.
These bounds lead to the final error

$\displaystyle
5^{T}\left(\frac{4\epsilon_{0}mRL^{2}}{\sigma_{\min}^{2}}+\frac{C}{q^{n}}+2r_{p}\lambda^{2/p-1}\right)\leq
5^{T}\left(\frac{2^{d+2}\epsilon_{0}q^{d}RL^{2}}{\sigma_{\min}^{2}}+\frac{C}{q^{n}}+2r_{p}\lambda^{2/p-1}\right)\leq\epsilon.$

The above in turn implies the complexity, up to polylog factors,

$\displaystyle\widetilde{O}\left(\frac{T^{2}m^{5/2}}{\epsilon_{0}}RL\mathcal{T}_{\rm
total}\right)=\widetilde{O}\left(T^{2}\mathcal{T}_{\rm
total}(2^{2n}C)^{15d/2n}e^{32Td(5^{T}C/\epsilon)^{2/n}}R^{2}\left(\frac{5^{T}}{\epsilon}\right)^{1+15d/2n}\right),$

where we again used that $L\leq e^{\frac{Td}{2}\lceil(3\cdot
5^{T}C/\epsilon)^{1/n}\rceil^{2}}$. Further, regarding the bound on $\lambda$,
we note that

$\displaystyle\ln\lambda$
$\displaystyle\geq\max\\{4qT\sqrt{d},3\sqrt{\ln(md/2\epsilon_{0})}\\}$
$\displaystyle=O\left(\max\left\\{T\sqrt{d}\left(\frac{5^{T}C}{\epsilon}\right)^{1/n},\sqrt{\ln\left(\frac{(2^{2n}C)^{2d/n}RL^{2}d}{\sigma_{\min}^{2}}\left(\frac{5^{T}}{\epsilon}\right)^{1+2d/n}\right)}\right\\}\right)$
$\displaystyle=O\left(\max\left\\{T\sqrt{d}\left(\frac{5^{T}C}{\epsilon}\right)^{1/n},\sqrt{\ln\left((2^{2n}C)^{6d/n}e^{27Td(5^{T}C/\epsilon)^{2/n}}R\left(\frac{5^{T}}{\epsilon}\right)^{1+6d/n}\right)}\right\\}\right)$

implies $\ln\lambda\geq
t(2q-\frac{1}{2})+\sqrt{2q^{2}t^{2}d+\ln(md/2\epsilon_{0})}$. Finally, we note
that $\epsilon\leq 5^{T}(2^{2d}C^{3d/n}R)^{n/(n+3d)}$ implies, as required,
that

$\displaystyle\epsilon_{0}=\frac{e^{-27Td(5^{T}C/\epsilon)^{2/n}}}{2^{2d+2}C^{5d/n}R}\left(\frac{\epsilon}{3\cdot
5^{T}}\right)^{1+5d/n}$ $\displaystyle\leq\frac{e^{-3Td(3\cdot
5^{T}C/\epsilon)^{1/n}}}{2^{2d+2}C^{5d/n}R}\left(\frac{\epsilon}{3\cdot
5^{T}}\right)^{1+5d/n}$ $\displaystyle\leq\frac{1}{2}e^{-3Td(3\cdot
5^{T}C/\epsilon)^{1/n}}\left(\frac{\epsilon}{3\cdot
5^{T}C}\right)^{2d/n}\leq\frac{\sigma_{\min}}{2}.\qed$

A similar result can be obtained for the classical LSM algorithm. Similarly to
Theorems 3.14 and 4.8, Algorithm 1, by using the same bounds on $\lambda$ (Eq.
(21)), outputs $\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}$
such that, for any $\epsilon_{0}\in(0,\sigma_{\min}/2]$,

$\displaystyle\begin{multlined}\operatorname{Pr}\left[\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{1}}]\big{|}\geq
5^{T}\left(\frac{4\epsilon_{0}mRL^{2}}{\sigma_{\min}^{2}}+\operatorname*{\max}_{0<t<T}\operatorname*{\min}_{a\in\mathbb{R}^{m}}\|a\cdot\vec{e}_{t}(X_{t})-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\right)\right]\\\
\leq
4me^{-2N\epsilon_{0}^{2}/m},\end{multlined}\operatorname{Pr}\left[\big{|}\widetilde{(\mathscr{T}_{\beta}Z)}_{\widetilde{\tau}_{1}}-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{1}}]\big{|}\geq
5^{T}\left(\frac{4\epsilon_{0}mRL^{2}}{\sigma_{\min}^{2}}+\operatorname*{\max}_{0<t<T}\operatorname*{\min}_{a\in\mathbb{R}^{m}}\|a\cdot\vec{e}_{t}(X_{t})-\mathbb{E}[(\mathscr{T}_{\beta}Z)_{\tau_{t+1}}|X_{t}]\|_{L^{2}(\rho_{t})}\right)\right]\\\
\leq 4me^{-2N\epsilon_{0}^{2}/m},$

in time $O(TmN+Tm^{\omega_{\ast}}+TN(\mathcal{T}_{\rm
samp}+\mathcal{T}_{z}+m\mathcal{T}_{e}))=O(T(mN+m^{\omega_{\ast}})\mathcal{T}_{\rm
total})$, where $O(TmN)$ comes from computing $\widetilde{b}_{t}$ and
$O(Tm^{\omega_{\ast}})$ from inverting $\widetilde{A}_{t}$ and computing
$\widetilde{\alpha}_{t}=\widetilde{A}_{t}^{-1}\widetilde{b}_{t}$, $t\in[T-1]$.
The application of the Jackson-like inequality is the same as in the previous
theorem. By taking $N=\lceil\frac{m}{2\epsilon_{0}^{2}}\log(4m/\delta)\rceil$
and the same parameters $q=\lceil(3\cdot 5^{T}C/\epsilon)^{1/n}\rceil$ and
$\epsilon_{0}\leq\frac{\sigma_{\min}^{2}}{2^{2d+2}C^{d/n}RL^{2}}\big{(}\frac{\epsilon}{3\cdot
5^{T}}\big{)}^{1+d/n}$ as before, the final complexity is

$\displaystyle O(T(mN+m^{\omega_{\ast}})\mathcal{T}_{\rm total})$
$\displaystyle=\widetilde{O}\left(T\left(\frac{m^{2}}{\epsilon_{0}^{2}}+m^{\omega_{\ast}}\right)\mathcal{T}_{\rm
total}\right)=\widetilde{O}\left(T\mathcal{T}_{\rm
total}(2^{2n}C)^{4d/n}\frac{R^{2}L^{4}}{\sigma_{\min}^{4}}\left(\frac{5^{T}}{\epsilon}\right)^{2+4d/n}\right)$
$\displaystyle=\widetilde{O}\left(T\mathcal{T}_{\rm
total}(2^{2n}C)^{12d/n}e^{54Td(5^{T}C/\epsilon)^{2/n}}R^{2}\left(\frac{5^{T}}{\epsilon}\right)^{2+12d/n}\right),$

up to the $\log(m/\delta)$ factor, using that $\sigma_{\min}^{-4}\leq
e^{12qd}q^{8d}=e^{12d\lceil(3\cdot 5^{T}C/\epsilon)^{1/n}\rceil}\lceil(3\cdot
5^{T}C/\epsilon)^{1/n}\rceil^{8d}$ according to Lemma 4.6 and the bound $L\leq
e^{q^{2}Td/2}=e^{\frac{Td}{2}\lceil(3\cdot 5^{T}/\epsilon)^{1/n}\rceil^{2}}$.

Even though the geometric Brownian motion setting does not simplify the LSM
algorithm as much as the Brownian motion setting from the previous section,
the minimum singular value from the matrices $\widetilde{A}_{t}$ can still be
bounded. The final classical and quantum complexities are
$\widetilde{O}\big{(}e^{54Td(5^{T}/\epsilon)^{2/n}}(5^{T}/\epsilon)^{2+12d/n}\big{)}$
and
$\widetilde{O}\big{(}e^{32Td(5^{T}/\epsilon)^{2/n}}(5^{T}/\epsilon)^{1+15d/2n}\big{)}$,
respectively. We can see that the bound on the minimum singular value in Lemma
4.6, as well as the $L^{2}$-norm of the chosen functions $e_{t,\vec{k}}$, are
very sensitive to the degree $q$ of the polynomials spanning our approximation
architecture: they lead to the exponential factor
$e^{O(Td(5^{T}/\epsilon)^{2/n})}$ on $\epsilon$, which greatly deteriorates
the polynomial dependence on $\epsilon$ that was previously observed in
previous sections. Nonetheless, if the continuation values are sufficiently
smooth, i.e., $n$-differentiable for
$n=\Theta(\log(5^{T}/\epsilon)/\log\log(5^{T}/\epsilon))$, then such an
exponential factor becomes $\exp\big{(}O(Td\log^{c}(5^{T}/\epsilon))\big{)}$
for any constant $0<c<1$, and we recover classical and quantum complexities
which are close to the expected $\widetilde{O}(1/\epsilon^{2})$ and
$\widetilde{O}(1/\epsilon)$, respectively.

##  5 Conclusions

In this work, we developed a new quantum algorithm for a stochastic optimal
stopping problem (as in Theorem 2.6) with a quantum advantage in the runtime.
This problem cannot be solved accurately by a single application of quantum
algorithms for Monte Carlo [70, 45, 23, 22, 2]. Instead one must compute in
superposition (and recursively) the stopping times as in Lemma 3.8, which is
key to obtaining a quantum speedup. As the classical LSM algorithm can be used
to solve a large variety of problems, our quantum LSM can also be used for
problems in finance including insurance [59] and risk management [42], and for
many optimization problems outside finance, such as quickest detection [89]
and sequential Bayesian hypothesis testing [27]. Additionally, we believe that
there are many other problems in, for example, dynamic programming, stochastic
optimal stopping and optimal control where the interplay of function
approximation and quantum subroutines for Monte Carlo could be used to design
new quantum algorithms.

A few design choices of the quantum algorithm were guided by real problems
where the classical algorithm is already used. Even though we took number of
expansion functions $m={\rm poly}(5^{T}/\epsilon)$ in order to bound the
approximation error, in practice one typically assumes $m$ to be constant
[63]. For big values of $m$, our algorithm could be modified in order to use
quantum subroutines for inner product estimation, and reduce the complexity
polynomially in $m$, but introducing a further $\epsilon$ dependence. Thus,
further analysis is needed to understand the impact of the precision
parameters on the runtime of these subroutines. Along these lines, we have
chosen to invert the linear systems for finding $\alpha_{t}$ on a classical
computer. A possible modification of our algorithm could output quantum states
$|\alpha_{t}\rangle$ via HHL-like algorithms [47]. We also discussed how,
under the hypothesis that the Markov chain is a Brownian motion or a Geometric
Brownian motion, the matrices $A_{t}$ can be expressed with a closed formula
and their minimum singular value be bounded. This idea exhibits some
similarity with the idea proposed in [62]. There, they leveraged quasi-
regression algorithms and a particular choice of expansion functions [75], so
to pre-compute the matrices $A_{t}$, and thus skip costly Monte Carlo
estimators. Moreover, when considering a Brownian or a Geometric Brownian
motion, the chosen functions $\\{e_{t,k}\\}_{k=1}^{m}$ had a explicit time
dependence on $t$, but it is possible to transform the optimal stopping time
problem behind American option pricing in a way that such dependence is
suppressed and a single set of approximating functions is employed [15, 16].
We believe that such approach could improve our complexities. Finally, in our
algorithm, we use quantum subroutines from [70], but could equivalently use
the subroutines from [45, 23, 22]. Our template could be extended to quantum
algorithms that are similar in spirit but are solving different problems [96].

Our final complexities have an exponential dependence on $T$, the number of
time steps. We believe that such dependence, present in several past works
[32, 105, 107, 104, 106, 69], is only a consequence of a loose error bound and
could possibly be improved. Such hope is backed up by the ubiquitous
employment of LSM algorithms for pricing American options in every day
financial markets. We also note that a more careful error analysis would
improve classical results as well, but, regardless, the quantum quadratic
improvement would still be present. Finally, notice that it always possible to
compensate a reduction on the number of time steps with more accurate
approximations for continuation values and similar quantities.

We stress the importance of fast quantum algorithms for optimal stopping
problems. For American option pricing, the value of the payoff function could
easily reach a few million dollars, and the additive precision $\epsilon$
could be of the order of $10^{-11}$ [3]. Given the level of specialization in
classical algorithms and architectures for this specific problem, how and when
our algorithm can find application in practice is left for future work.

## Acknowledgements

Research at CQT is funded by the National Research Foundation, the Prime
Minister’s Office, and the Ministry of Education, Singapore under the Research
Centres of Excellence programme’s research grant R-710-000-012-135. We thank
Rajagopal Raman for pointing out Ref. [59] and the importance of the
Longstaff-Schwarz algorithm in the insurance industry. We also thank Koichi
Miyamoto for Ref. [54] and Eric Ghysels for Refs. [15, 16].

## References

  * [1] Javier Alcazar, Vicente Leyton-Ortega and Alejandro Perdomo-Ortiz  “Classical versus quantum models in machine learning: insights from a finance application”  In _Machine Learning: Science and Technology_ 1.3 IOP Publishing, 2020, pp. 035003
  * [2] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao and Jiasu Wang  “Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance”  In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 481
  * [3] Leif B.. Andersen, Mark Lake and Dimitri Offengenden  “High-performance American option pricing”  In _Journal of Computational Finance_ 20.1, 2016, pp. 39–87
  * [4] Anna Rita Bacinello, Enrico Biffis and Pietro Millossovich  “Pricing life insurance contracts with early exercise features”  In _Journal of computational and applied mathematics_ 233.1 Elsevier, 2009, pp. 27–35
  * [5] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli and Stefan Woerner  “Improving variational quantum optimization using CVaR”  In _Quantum_ 4 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2020, pp. 256
  * [6] Giovanni Barone-Adesi and Robert E. Whaley  “Efficient analytic approximation of American option values”  In _the Journal of Finance_ 42.2 Wiley Online Library, 1987, pp. 301–320
  * [7] Christian Bender and Jessica Steiner  “Least-squares Monte Carlo for backward SDEs”  In _Numerical methods in finance_ Springer, 2012, pp. 257–289
  * [8] Alain Bensoussan and J.-L. Lions  “Applications of variational inequalities in stochastic control”  Elsevier, 2011
  * [9] A. Benveniste, M. Métivier and P. Priouret  “Adaptive algorithms and stochastic approximations”  In _Applications of Mathematics_ , 1990
  * [10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari and Rolando D. Somma  “Simulating Hamiltonian dynamics with a truncated Taylor series”  In _Phys. Rev. Lett._ 114 American Physical Society, 2015, pp. 090502
  * [11] Fischer Black and Myron Scholes  “The pricing of options and corporate liabilities”  In _Journal of Political Economy_ 81, 1973, pp. 637–654
  * [12] Adam Bouland, Wim Dam, Hamed Joorati, Iordanis Kerenidis and Anupam Prakash  “Prospects and challenges of quantum finance”  In _arXiv preprint arXiv:2011.06492_ , 2020
  * [13] Phelim P. Boyle  “Options: a Monte Carlo approach”  In _Journal of Financial Economics_ 4.3 Elsevier, 1977, pp. 323–338
  * [14] Gilles Brassard, Peter Hoyer, Michele Mosca and Alain Tapp  “Quantum amplitude amplification and estimation”  In _Contemporary Mathematics_ 305 Providence, RI; American Mathematical Society; 1999, 2002, pp. 53–74
  * [15] Mark Broadie, Jérôme Detemple, Eric Ghysels and Olivier Torrès  “American options with stochastic dividends and volatility: A nonparametric investigation”  In _Journal of Econometrics_ 94.1-2 Elsevier, 2000, pp. 53–92
  * [16] Mark Broadie, Jérôme Detemple, Eric Ghysels and Olivier Torrès  “Nonparametric estimation of American options’ exercise boundaries and call prices”  In _Journal of Economic Dynamics and Control_ 24.11-12 Elsevier, 2000, pp. 1829–1857
  * [17] Mark Broadie and Paul Glasserman  “Monte Carlo methods for pricing high-dimensional American options: an overview”  In _Net Exposure_ 3, 1997, pp. 15–37
  * [18] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner and William J. Zeng  “A threshold for quantum advantage in derivative pricing”  In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 463
  * [19] Don M. Chance  “A synthesis of binomial option pricing models for lognormally distributed assets”  In _Journal of Applied Finance (Formerly Financial Practice and Education)_ 18.1, 2008
  * [20] Marco Chiani and Davide Dardari  “Improved exponential bounds and approximation for the Q-function with application to average error probability computation”  In _Global Telecommunications Conference, 2002. GLOBECOM’02. IEEE_ 2, 2002, pp. 1399–1402  IEEE
  * [21] Emmanuelle Clément, Damien Lamberton and Philip Protter  “An analysis of a least squares regression method for American option pricing”  In _Finance and Stochastics_ 6.4 Springer, 2002, pp. 449–471
  * [22] Arjan Cornelissen, Yassine Hamoudi and Sofiene Jerbi  “Near-optimal quantum algorithms for multivariate mean estimation”  In _arXiv preprint arXiv:2111.09787_ , 2021
  * [23] Arjan Cornelissen and Sofiene Jerbi  “Quantum algorithms for multivariate Monte Carlo estimation”  In _arXiv preprint arXiv:2107.03410_ , 2021
  * [24] John C. Cox, Stephen A. Ross and Mark Rubinstein  “Option pricing: a simplified approach”  In _Journal of Financial Economics_ 7.3 Elsevier, 1979, pp. 229–263
  * [25] Gary Wayne Crosby  “Optimal multiple stopping: theory and applications”, 2017
  * [26] Samudra Dasgupta and Arnab Banerjee  “Quantum annealing algorithm for expected shortfall based dynamic asset allocation”  In _arXiv preprint arXiv:1909.12904_ , 2019
  * [27] Constantinos Daskalakis and Yasushi Kawase  “Optimal stopping rules for sequential hypothesis testing”  In _25th Annual European Symposium on Algorithms (ESA)_ , 2017
  * [28] Ronald A. DeVore and George G. Lorentz  “Constructive approximation”  Springer Science & Business Media, 1993
  * [29] Georgios Dimitrakopoulos  “Least-squares Monte Carlo simulation and high performance computing for Solvency II regulatory capital estimation”, 2013
  * [30] “Directive 2009/138/EC of the European Parliament and of the Council of 25 November 2009 on the taking-up and pursuit of the business of Insurance and Reinsurance (Solvency II)”  In _Official Journal of European Union_ , 2009
  * [31] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner and Elena Yndurain  “Quantum computing for finance: state of the art and future prospects”  In _IEEE Transactions on Quantum Engineering_ IEEE, 2020
  * [32] Daniel Egloff  “Monte Carlo algorithms for optimal stopping and statistical learning”  In _The Annals of Applied Probability_ 15.2 Institute of Mathematical Statistics, 2005, pp. 1396–1432
  * [33] Robert P. Feinerman and Donald J. Newman  “Polynomial approximation”, 1974
  * [34] Hans Föllmer and Alexander Schied  “Stochastic finance”  de Gruyter, 2016
  * [35] Filipe Fontanela, Antoine Jacquier and Mugad Oumgari  “A quantum algorithm for linear PDEs arising in finance”  In _SIAM Journal on Financial Mathematics_ 12.4 SIAM, 2021, pp. SC98–SC114
  * [36] Michael C. Fu, Scott B. Laprise, Dilip B. Madan, Yi Su and Rongwen Wu  “Pricing American options: a comparison of Monte Carlo simulation approaches”  In _Journal of Computational Finance_ 4.3 Citeseer, 2001, pp. 39–88
  * [37] Stefan Gerhold  “The Longstaff-Schwartz algorithm for Lévy models: results on fast and slow convergence”  In _The Annals of Applied Probability_ 21.2 Institute of Mathematical Statistics, 2011, pp. 589–608
  * [38] Paul Glasserman and Bin Yu  “Number of paths versus number of basis functions in American option pricing”  In _The Annals of Applied Probability_ 14.4 Institute of Mathematical Statistics, 2004, pp. 2090–2119
  * [39] Emmanuel Gobet, Jean-Philippe Lemor and Xavier Warin  “A regression-based Monte Carlo method to solve backward stochastic differential equations”  In _The Annals of Applied Probability_ 15.3 Institute of Mathematical Statistics, 2005, pp. 2172–2202
  * [40] Emmanuel Gobet and Plamen Turkedjiev  “Approximation of discrete BSDE using least-squares regression”, 2011  URL: https://hal.archives-ouvertes.fr/hal-00642685
  * [41] Gene H. Golub and Charles F. Van Loan  “Matrix computations”  The Johns Hopkins University Press, 2013
  * [42] Andrew Green  “XVA: Credit, funding and capital valuation adjustments”  John Wiley & Sons, 2015
  * [43] Lov Grover and Terry Rudolph  “Creating superpositions that correspond to efficiently integrable probability distributions”  In _arXiv preprint quant-ph/0208112_ , 2002
  * [44] Eli Gutin  “Practical applications of large-scale stochastic control for learning and optimization”, 2018
  * [45] Yassine Hamoudi  “Quantum sub-Gaussian mean estimator”  In _29th Annual European Symposium on Algorithms (ESA 2021)_ , 2021  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [46] Jeong Yu Han and Patrick Rebentrost  “Quantum advantage for multi-option portfolio pricing and valuation adjustments”  In _arXiv preprint arXiv:2203.04924_ , 2022
  * [47] Aram W. Harrow, Avinatan Hassidim and Seth Lloyd  “Quantum algorithm for linear systems of equations”  In _Physical review letters_ 103.15 APS, 2009, pp. 150502
  * [48] Steven Herbert  “No quantum speedup with Grover-Rudolph state preparation for quantum Monte Carlo integration”  In _Physical Review E_ 103.6 APS, 2021, pp. 063302
  * [49] Mark Hodson, Brendan Ruck, Hugh Ong, David Garvin and Stefan Dulman  “Portfolio rebalancing experiments using the quantum alternating operator ansatz”  In _arXiv preprint arXiv:1911.05296_ , 2019
  * [50] Jacqueline Huang and Jong-Shi Pang  “Option pricing and linear complementarity”, 2003
  * [51] Dunham Jackson  “A general class of problems in approximation”  In _American Journal of Mathematics_ 46.4 JSTOR, 1924, pp. 215–234
  * [52] Patrick Jaillet, Damien Lamberton and Bernard Lapeyre  “Variational inequalities and the pricing of American options”  In _Acta Applicandae Mathematica_ 21.3 Springer, 1990, pp. 263–289
  * [53] Norman L Johnson, Samuel Kotz and Narayanaswamy Balakrishnan  “Continuous univariate distributions”  John wiley & sons, 1995
  * [54] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda and Kazuyoshi Yoshino  “Linear regression by quantum amplitude estimation and its extension to convex optimization”  In _Phys. Rev. A_ 104 American Physical Society, 2021, pp. 022430  DOI: 10.1103/PhysRevA.104.022430
  * [55] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda and Kazuyoshi Yoshino  “Quantum pricing with a smile: implementation of local volatility model on quantum computer”  In _arXiv preprint arXiv:2007.01467_ , 2020
  * [56] In Joon Kim  “The analytic valuation of American options”  In _The Review of Financial Studies_ 3.4 Oxford University Press, 1990, pp. 547–572
  * [57] Maciej Klimek and Marcin Pitera  “The least squares method for option pricing revisited”  In _Applicationes Mathematicae_ 45 Instytut Matematyczny Polskiej Akademii Nauk, 2018, pp. 5–29
  * [58] Michael Kohler  “A review on regression-based Monte Carlo methods for pricing American options”  In _Recent developments in applied probability and statistics_ Springer, 2010, pp. 37–58
  * [59] Anne-Sophie Krah, Zoran Nikolić and Ralf Korn  “A least-squares Monte Carlo framework in proxy modeling of life insurance companies”  In _Risks_ 6.2 Multidisciplinary Digital Publishing Institute, 2018, pp. 62
  * [60] Jean-Philippe Lemor, Emmanuel Gobet and Xavier Warin  “Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations”  In _Bernoulli_ 12.5 Bernoulli Society for Mathematical StatisticsProbability, 2006, pp. 889–916
  * [61] Xiaofei Li, Yi Wu, Quanxin Zhu, Songbo Hu and Chuan Qin  “A regression-based Monte Carlo method to solve two-dimensional forward backward stochastic differential equations”  In _Advances in Difference Equations_ 2021.1 Springer, 2021, pp. 1–13
  * [62] Chen Liu, Henry Schellhorn and Qidi Peng  “American option pricing with regression: convergence analysis”  In _International Journal of Theoretical and Applied Finance_ 22.08 World Scientific, 2019, pp. 1950044
  * [63] Francis A. Longstaff and Eduardo S. Schwartz  “Valuing American options by simulation: a simple least-squares approach”  In _The review of financial studies_ 14.1 Oxford University Press, 2001, pp. 113–147
  * [64] Wilhelm Magnus, Fritz Oberhettinger and Raj Pal Soni  “Formulas and theorems for the special functions of mathematical physics”  Springer Science & Business Media, 2013
  * [65] Gabriel Marin-Sancheza, Javier Gonzalez-Conde and Mikel Sanz  “Quantum algorithms for approximate function loading”  In _arXiv preprint arXiv:2111.07933_ , 2021
  * [66] Ana Martin, Bruno Candelas, Ángel Rodríguez-Rozas, José D. Martín-Guerrero, Xi Chen, Lucas Lamata, Román Orús, Enrique Solano and Mikel Sanz  “Toward pricing financial derivatives with an IBM quantum computer”  In _Physical Review Research_ 3.1 APS, 2021, pp. 013167
  * [67] Henry P. McKean Jr  “A free boundary problem for the heat equation arising from a problem of mathermatical economics”  In _Industrial Management Review_ 6, 1965, pp. 32–39
  * [68] Robert C. Merton  “Theory of rational option pricing”  In _The Bell Journal of Economics and Management Science_ 4.1, 1973, pp. 141–183
  * [69] Koichi Miyamoto  “Bermudan option pricing by quantum amplitude estimation and Chebyshev interpolation”  In _arXiv preprint arXiv:2108.09014_ , 2021
  * [70] Ashley Montanaro  “Quantum speedup of Monte Carlo methods”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 471.2181 The Royal Society, 2015, pp. 20150301
  * [71] Alexey Muravlev and Mikhail Zhitlukhin  “A Bayesian sequential test for the drift of a fractional Brownian motion”  In _Advances in Applied Probability_ 52.4 Cambridge University Press, 2020, pp. 1308–1324
  * [72] Jacques Neveu  “Discrete-parameter martingales”  Elsevier, 1975
  * [73] Michael A. Nielsen and Isaac L. Chuang  “Quantum computation and quantum information”  Cambridge University Press, 2010  DOI: 10.1017/CBO9780511976667
  * [74] Roman Orus, Samuel Mugel and Enrique Lizaso  “Quantum computing for finance: overview and prospects”  In _Reviews in Physics_ 4 Elsevier, 2019, pp. 100028
  * [75] Art B. Owen  “Assessing linearity in high dimensions”  In _The Annals of Statistics_ 28.1 Institute of Mathematical Statistics, 2000, pp. 1–19
  * [76] Antoon Pelsser and Janina Schweizer  “The difference between LSMC and replicating portfolio in insurance liability modeling”  In _European actuarial journal_ 6.2 Springer, 2016, pp. 441–494
  * [77] Goran Peskir and Albert Shiryaev  “Optimal stopping and free-boundary problems”  Springer, 2006
  * [78] Warren B. Powell  “A unified framework for stochastic optimization”  In _European Journal of Operational Research_ 275.3 Elsevier, 2019, pp. 795–821
  * [79] Santosh Kumar Radha  “Quantum option pricing using Wick rotated imaginary time evolution”  In _arXiv preprint arXiv:2101.04280_ , 2021
  * [80] Sergi Ramos-Calderer, Adrián Pérez-Salinas, Diego García-Martín, Carlos Bravo-Prieto, Jorge Cortada, Jordi Planaguma and José I. Latorre  “Quantum unary approach to option pricing”  In _Physical Review A_ 103.3 APS, 2021, pp. 032414
  * [81] Patrick Rebentrost, Brajesh Gupt and Thomas R. Bromley  “Quantum computational finance: Monte Carlo pricing of financial derivatives”  In _Phys. Rev. A_ 98, 2018, pp. 022321
  * [82] Patrick Rebentrost and Seth Lloyd  “Quantum computational finance: quantum algorithm for portfolio optimization”  In _arXiv preprint arXiv:1811.03975_ , 2018
  * [83] Patrick Rebentrost, Miklos Santha and Siyi Yang  “Quantum Alphatron”  In _arXiv preprint arXiv:2108.11670_ , 2021
  * [84] Richard J. Rendleman  “Two-state option pricing”  In _The Journal of Finance_ 34.5 JSTOR, 1979, pp. 1093–1110
  * [85] Leonard C.. Rogers  “Monte Carlo valuation of American options”  In _Mathematical Finance_ 12.3 Wiley Online Library, 2002, pp. 271–286
  * [86] Joose Mikko Juhani Sauli  “On the suitability of the Longstaff-Schwartz term structure model for modelling the cost of government debt”, 2013
  * [87] William F. Sharpe, Gordon J. Alexander and Jeffrey W. Bailey  “Investments”  Prentice-Hall, 1999
  * [88] Albert N. Shiryaev  “Optimal stopping rules”  Springer Science & Business Media, 2007
  * [89] Albert N. Shiryaev  “Quickest detection problems: fifty years later”  In _Sequential Analysis_ 29.4 Taylor & Francis, 2010, pp. 345–385
  * [90] Marvin K. Simon and Dariush Divsalar  “Some new twists to problems involving the Gaussian probability integral”  In _IEEE Transactions on Communications_ 46.2 IEEE, 1998, pp. 200–210
  * [91] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen and Stefan Woerner  “Option pricing using quantum computers”  In _arXiv preprint arXiv:1905.02666_ , 2019
  * [92] Nikitas Stamatopoulos, Guglielmo Mazzola, Stefan Woerner and William J. Zeng  “Towards quantum advantage in financial market risk using quantum gradient algorithms”  In _arXiv preprint arXiv:2111.12509_ , 2021
  * [93] Lars Stentoft  “Convergence of the least squares Monte Carlo approach to American option valuation”  In _Management Science_ 50.9 INFORMS, 2004, pp. 1193–1203
  * [94] Peter Tankov, Ekaterina Voltchkova and Rama Cont  “Option pricing models with jumps: integro-differential equations and inverse problems”  In _European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2004)_ , 2004
  * [95] Elliot Tonkes and Dharma Lesmono  “A Longstaff and Schwartz approach to the early election problem”  In _Advances in Decision Sciences_ 2012 Hindawi, 2012
  * [96] John N. Tsitsiklis and Benjamin Van Roy  “Regression methods for pricing complex American-style options”  In _IEEE Transactions on Neural Networks_ 12.4 IEEE, 2001, pp. 694–703
  * [97] S… Van Eijndhoven and J… Meyers  “New orthogonality relations for the Hermite polynomials and related Hilbert spaces”  In _Journal of Mathematical Analysis and Applications_ 146.1 Elsevier, 1990, pp. 89–98
  * [98] Pierre Van Moerbeke  “On optimal stopping and free boundary problems”  In _Archive for Rational Mechanics and Analysis_ 60.2 Springer, 1976, pp. 101–148
  * [99] VN Vapnik and A Ya Chervonenkis  “On the uniform convergence of relative frequencies of events to their probabilities”  In _Theory of Probability and its Applications_ 16.2 Society for IndustrialApplied Mathematics, 1971, pp. 264–280
  * [100] Almudena Carrera Vazquez and Stefan Woerner  “Efficient state preparation for quantum amplitude estimation”  In _Physical Review Applied_ 15.3 APS, 2021, pp. 034027
  * [101] Abraham Wald  “Sequential Analysis”  John WileySons, 1947
  * [102] Pawel Wocjan, Chen-Fu Chiang, Daniel Nagaj and Anura Abeyesinghe  “Quantum algorithm for approximating partition functions”  In _Phys. Rev. A_ 80 American Physical Society, 2009, pp. 022340
  * [103] Stefan Woerner and Daniel J. Egger  “Quantum risk analysis”  In _arXiv preprint arXiv:1806.06893_ , 2018
  * [104] Daniel Z. Zanger  “Convergence of a least-squares Monte Carlo algorithm for American option pricing with dependent sample data”  In _Mathematical Finance_ 28.1 Wiley Online Library, 2018, pp. 447–479
  * [105] Daniel Z. Zanger  “Convergence of a least-squares Monte Carlo algorithm for bounded approximating sets”  In _Applied Mathematical Finance_ 16.2 Taylor & Francis, 2009, pp. 123–150
  * [106] Daniel Z. Zanger  “General error estimates for the Longstaff-Schwartz least-squares Monte Carlo algorithm”  In _Mathematics of Operations Research_ 45.3 INFORMS, 2020, pp. 923–946
  * [107] Daniel Z. Zanger  “Quantitative error estimates for a least-squares Monte Carlo algorithm for American option pricing”  In _Finance and Stochastics_ 17.3 Springer, 2013, pp. 503–534

##  Appendix A Proof of Lemma 4.4

######  Lemma A.1.

Given $\lambda>0$ and $k,l\in\mathbb{N}$ with $l\leq k$, then

$\displaystyle\left|\int_{\lambda}^{\infty}H_{k}(x)H_{l}(x)e^{-x^{2}}\text{d}x\right|\leq\begin{dcases}k!2^{k}\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)+e^{-\lambda^{2}}H_{k+1}(\lambda)^{2}\quad&\text{if}~{}k=l,\\\
e^{-\lambda^{2}}|H_{l+1}(\lambda)H_{k}(\lambda)|\quad&\text{if}~{}k\neq
l,\end{dcases}$

where
$\operatorname{erfc}(\lambda)=\frac{2}{\sqrt{\pi}}\int_{\lambda}^{\infty}e^{-x^{2}}\text{d}x$
is the complementary error function. In particular,

$\displaystyle\left|\int_{\lambda}^{\infty}H_{k}(x)H_{l}(x)e^{-x^{2}}\text{d}x\right|\leq
2^{2+(k+l)/2}\sqrt{(k+1)!(l+1)!}e^{(\sqrt{2(k+1)}+\sqrt{2(l+1)})\lambda}e^{-\lambda^{2}}.$

###### Proof.

In the following, by $H^{(j)}_{k}(x)$ we denote the $j$-th derivative of
$H_{k}(x)$. By plugging the definition of $H_{l}(x)$, it is not hard to
observe the following using integration by parts:

$\displaystyle\int_{\lambda}^{\infty}H_{k}(x)H_{l}(x)e^{-x^{2}}\text{d}x$
$\displaystyle=(-1)^{k}\int_{\lambda}^{\infty}H_{l}(x)\frac{\text{d}^{k}}{\text{d}x^{k}}e^{-x^{2}}\text{d}x$
$\displaystyle=e^{-\lambda^{2}}\sum_{j=0}^{k-1}H_{l}^{(j)}(\lambda)H_{k-j-1}(\lambda)+\int_{\lambda}^{\infty}H_{l}^{(k)}(x)e^{-x^{2}}\text{d}x$
$\displaystyle=e^{-\lambda^{2}}\sum_{j=0}^{k-1}H_{l}^{(j)}(\lambda)H_{k-j-1}(\lambda)+\delta_{kl}2^{k}k!\int_{\lambda}^{\infty}e^{-x^{2}}\text{d}x$
$\displaystyle=e^{-\lambda^{2}}\sum_{j=0}^{k-1}H_{l}^{(j)}(\lambda)H_{k-j-1}(\lambda)+\delta_{kl}2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)$
$\displaystyle=e^{-\lambda^{2}}\sum_{j=0}^{\min(l,k-1)}2^{j}\frac{l!}{(l-j)!}H_{l-j}(\lambda)H_{k-j-1}(\lambda)+\delta_{kl}2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda),$

where we used that $H^{(j)}_{l}(x)=2^{j}\frac{l!}{(l-j)!}H_{l-j}(x)$ for
$j\leq l$, which follows from
$\frac{\text{d}}{\text{d}x}H_{l}(x)=2lH_{l-1}(x)$ [64, Section 5.6.2]. If
$k=l$, then

$\displaystyle\int_{\lambda}^{\infty}H_{k}(x)^{2}e^{-x^{2}}\text{d}x$
$\displaystyle\leq
2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)+e^{-\lambda^{2}}\sum_{j=0}^{k-1}2^{j}\frac{k!}{(k-j)!}|H_{k-j}(\lambda)H_{k-j-1}(\lambda)|$
$\displaystyle\leq
2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)+e^{-\lambda^{2}}\sqrt{\left(\sum_{j=0}^{k-1}\frac{k!2^{j}}{(k-j)!}H_{k-j}(\lambda)^{2}\right)\left(\sum_{j=0}^{k-1}\frac{k!2^{j}}{(k-j)!}H_{k-j-1}(\lambda)^{2}\right)}$
(26) $\displaystyle\leq
2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)+2^{k}k!e^{-\lambda^{2}}\sum_{j=0}^{k}\frac{1}{2^{j}j!}H_{j}(\lambda)^{2}$
$\displaystyle=2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)+\frac{1}{2}e^{-\lambda^{2}}(H_{k+1}(\lambda)^{2}-H_{k}(\lambda)H_{k+2}(\lambda))$
(27) $\displaystyle\leq
2^{k}k!\frac{\sqrt{2}}{\pi}\operatorname{erfc}(\lambda)+e^{-\lambda^{2}}H_{k+1}(\lambda)^{2},$

where Eq. (26) follows from Cauchy-Schwarz inequality and Eq. (27) follows
from the equality
$\frac{1}{2^{k+1}k!}(H_{k+1}(x)^{2}-H_{k}(x)H_{k+2}(x))=\sum_{j=0}^{k}\frac{1}{2^{j}j!}H_{j}(x)^{2}>0$
[64, Section 5.6.4].

If, on the other hand, $k\neq l$, then

$\displaystyle\left|\int_{\lambda}^{\infty}H_{k}(x)H_{l}(x)e^{-x^{2}}\text{d}x\right|$
$\displaystyle\leq
e^{-\lambda^{2}}\sum_{j=0}^{l}2^{j}\frac{l!}{(l-j)!}|H_{l-j}(\lambda)H_{k-j-1}(\lambda)|$
$\displaystyle\leq
e^{-\lambda^{2}}\sqrt{\left(\sum_{j=0}^{l}2^{j}\frac{l!}{(l-j)!}H_{l-j}(\lambda)^{2}\right)\left(\sum_{j=0}^{l}2^{j}\frac{l!}{(l-j)!}H_{k-1-j}(\lambda)^{2}\right)}$
$\displaystyle\leq\sqrt{2^{l}l!}e^{-\lambda^{2}}\sqrt{\left(\sum_{j=0}^{l}\frac{1}{2^{j}j!}H_{j}(\lambda)^{2}\right)\left(\sum_{j=0}^{k-1}2^{j}\frac{(k-1)!}{(k-1-j)!}H_{k-1-j}(\lambda)^{2}\right)}$
$\displaystyle=\sqrt{2^{k+l-1}l!(k-1)!}e^{-\lambda^{2}}\sqrt{\left(\sum_{j=0}^{l}\frac{1}{2^{j}j!}H_{j}(\lambda)^{2}\right)\left(\sum_{j=0}^{k-1}\frac{1}{2^{j}j!}H_{j}(\lambda)^{2}\right)}$
$\displaystyle=\frac{1}{2}e^{-\lambda^{2}}\sqrt{H_{l+1}(\lambda)^{2}-H_{l}(\lambda)H_{l+2}(\lambda)}\sqrt{H_{k}(\lambda)^{2}-H_{k-1}(\lambda)H_{k+1}(\lambda)}$
$\displaystyle\leq e^{-\lambda^{2}}|H_{l+1}(\lambda)H_{k}(\lambda)|,$

where we again used
$\frac{1}{2^{k+1}k!}(H_{k+1}(x)^{2}-H_{k}(x)H_{k+2}(x))=\sum_{j=0}^{k}\frac{1}{2^{j}j!}H_{j}(x)^{2}\geq
0$ [64, Section 5.6.4] and Cauchy-Schwarz inequality. This concludes the first
part of the lemma.

For the second part of the lemma, we use that $|H_{k}(\lambda)|\leq
2^{k/2}\sqrt{k!}e^{\sqrt{2k}|\lambda|}$ [97] and that
$\operatorname{erfc}(\lambda)\leq e^{-\lambda^{2}}$ [90, 20]. Then, if $k=l$,

$\displaystyle\left|\int_{\lambda}^{\infty}H_{k}(x)^{2}e^{-x^{2}}\text{d}x\right|\leq\frac{\sqrt{2}}{\pi}2^{k}k!e^{-\lambda^{2}}+2^{k+1}(k+1)!e^{2\sqrt{2(k+1)}\lambda}e^{-\lambda^{2}}\leq
2^{k+2}(k+1)!e^{2\sqrt{2(k+1)}\lambda}e^{-\lambda^{2}},$

and if $l\neq k$, then

$\left|\int_{\lambda}^{\infty}H_{k}(x)H_{l}(x)e^{-x^{2}}\text{d}x\right|\leq
2^{(k+l+1)/2}\sqrt{k!(l+1)!}e^{(\sqrt{2k}+\sqrt{2(l+1)})\lambda}e^{-\lambda^{2}}.\qed$