Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Random Bits for Quadrature of SDEs

Lukas Mayer‐Suess

Published Jan 1, 2020• 0 citations
OpenAlex

Abstract

In this thesis we study a variant of the quadrature problem for stochastic differential equations (SDEs), namely the approximation of expectations \(\mathrm{E}(f(X))\), where \(X = (X(t))_{t \in [0,1]}\) is the solution of an SDE and \(f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R}\) is a functional, mapping each realization of \(X\) into the real numbers. The distinctive feature in this work is that we consider randomized (Monte Carlo) algorithms with random bits as their only source of randomness, whereas the algorithms commonly studied in the literature are allowed to sample from the uniform distribution on the unit interval, i.e., they do have access to random numbers from \([0,1]\). By assumption, all further operations like, e.g., arithmetic operations, evaluations of elementary functions, and oracle calls to evaluate \(f\) are considered within the real number model of computation, i.e., they are carried out exactly. In the following, we provide a detailed description of the quadrature problem, namely we are interested in the approximation of \begin{align*} S(f) = \mathrm{E}(f(X)) \end{align*} for \(X\) being the \(r\)-dimensional solution of an autonomous SDE of the form \begin{align*} \mathrm{d}X(t) = a(X(t)) \, \mathrm{d}t + b(X(t)) \, \mathrm{d}W(t), \quad t \in [0,1], \end{align*} with deterministic initial value \begin{align*} X(0) = x_0 \in \mathbb{R}^r, \end{align*} and driven by a \(d\)-dimensional standard Brownian motion \(W\). Furthermore, the drift coefficient \(a \colon \mathbb{R}^r \to \mathbb{R}^r\) and the diffusion coefficient \(b \colon \mathbb{R}^r \to \mathbb{R}^{r \times d}\) are assumed to be globally Lipschitz continuous. For the function classes \begin{align*} F_{\infty} = \bigl\{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq \|x-y\|_{\sup}\bigr\} \end{align*} and \begin{align*} F_p = \bigl\{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq \|x-y\|_{L_p}\bigr\}, \quad 1 \leq p < \infty. \end{align*} we have established the following. \[\] \(\textit{Theorem 1.}\) There exists a random bit multilevel Monte Carlo (MLMC) algorithm \(M\) using \[ L = L(\varepsilon,F) = \begin{cases}\lceil{\log_2(\varepsilon^{-2}}\rceil, &\text{if} \ F = F_p,\\ \lceil{\log_2(\varepsilon^{-2} + \log_2(\log_2(\varepsilon^{-1}))}\rceil, &\text{if} \ F = F_\infty \end{cases} \] and replication numbers \[ N_\ell = N_\ell(\varepsilon,F) = \begin{cases} \lceil{(L+1) \cdot 2^{-\ell} \cdot \varepsilon^{-2}}\rceil, & \text{if} \ F = F_p,\\ \lceil{(L+1) \cdot 2^{-\ell} \cdot \max(\ell,1) \cdot \varepsilon^{-2}}\rceil, & \text{if} \ F=f_\infty \end{cases} \] for \(\ell = 0,\ldots,L\), for which exists a positive constant \(c\) such that \begin{align*} \mathrm{error}(M,F) = \sup_{f \in F} \bigl(\mathrm{E}(S(f) - M(f))^2\bigr)^{1/2} \leq c \cdot \varepsilon \end{align*} and \begin{align*} \mathrm{cost}(M,F) = \sup_{f \in F} \mathrm{E}(\mathrm{cost}(M,f)) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for every \(\varepsilon \in {]0,1/2[}\). \[\] Hence, in terms of the \(\varepsilon\)-complexity \begin{align*} \mathrm{comp}(\varepsilon,F) = \inf\bigl\{\mathrm{cost}(M,F) \colon M \ \text{is a random bit MC algorithm}, \mathrm{error}(M,F) \leq \varepsilon\bigr\} \end{align*} we have established the upper bound \begin{align*} \mathrm{comp}(\varepsilon,F) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for some positive constant \(c\). That is, we have shown the same weak asymptotic upper bound as in the case of random numbers from \([0,1]\). Hence, in this sense, random bits are almost as powerful as random numbers for our computational problem. Moreover, we present numerical results for a non-analyzed adaptive random bit MLMC Euler algorithm, in the particular cases of the Brownian motion, the geometric Brownian motion, the Ornstein-Uhlenbeck SDE and the Cox-Ingersoll-Ross SDE. We also provide a numerical comparison to the corresponding adaptive random number MLMC Euler method. A key challenge in the analysis of the algorithm in Theorem 1 is the approximation of probability distributions by means of random bits. A problem very closely related to the quantization problem, i.e., the optimal approximation of a given probability measure (on a separable Hilbert space) by means of a probability measure with finite support size. Though we have shown that the random bit approximation of the standard normal distribution is 'harder' than the corresponding quantization problem (lower weak rate of convergence), we have been able to establish the same weak rate of convergence as for the corresponding quantization problem in the case of the distribution of a Brownian bridge on \(L_2([0,1])\), the distribution of the solution of a scalar SDE on \(L_2([0,1])\), and the distribution of a centered Gaussian random element in a separable Hilbert space.

Related papers

Some Numerical Methods And Analysis of A Class of Quantum Stochastic Differential Equations

Samuel Oluwaseyi Ogundipe

The classical stochastic differential equation given as \[dX(t, \omega) = a(t, X) \, dt + b(t, X) \, dQ(t), \quad X(t_0) = X_0, \quad t \in [t_0, T],\] where the driving process \( Q(t) \) is a martingale, and \( a \) and \( b \) are adapted functionals has several numerical schemes developed for it, where each exhibits distinct stability and convergence properties depending on the nature of the driving process and the functional space of the solution. A generalization of this equation is the quantum stochastic differential equation introduced by Hudson and Parthasarathy, expressed as \[dX(t) = E(t, X(t)) \, d\Lambda_\pi(t) + F(t, X(t)) \, dA_f^\dagger(t) + G(t, X(t)) \, dA_g(t) + H(t, X(t)) \, dt,\] where \( E, F, G, \) and \( H \) are stochastic operator-valued functions defined on a Hilbert space. In 1992, Ekhaquere reformulated this equation in an equivalent form involving the non-classical differential equation stated as; \[\frac{d}{dt} \langle \eta, X(t) \xi \rangle = P(t, X(t)) \langle \eta, \xi \rangle, \quad X(t_0) = X_0, \quad t \in [t_0, T],\] which represents an ordinary differential equation of non-classical type. The stochastic process \( X(t) \) acts as a densely defined linear operator on a tensor product of two Hilbert spaces, one of which is the Boson Fock space. The vectors \( \eta \) and \( \xi \) belong to a dense subset of this tensor product Hilbert space, and the mapping \[(\eta, \xi) \mapsto P(t, X)(\eta, \xi)\] defines a sesquilinear form for each fixed pair \((t, X)\). We analyze the numerical approximation of the QSDE using its equivalent inner-product form. The numerical investigation employs three principal methods: the Lagrangian Quadrature Method, the Linear Multistep Scheme, and the Newton–Cotes Method. Each method is carefully designed to ensure the consistency, stability, and convergence of the approximate solution \(X(t)\) toward the exact stochastic process. These schemes are implemented using Python programming language, which provides a flexible and efficient computational environment for testing the proposed algorithms. Our computational results show that the developed schemes generalize Taylor-type approximations of Itô processes under weak convergence criteria. The proposed algorithms exhibit numerical stability and yield results that compare favorably with analytical benchmarks. Furthermore, the implementation avoids direct approximation of the driving quantum processes, thereby preserving the natural adaptation of the schemes to quantum dynamical models.

•Jan 9, 2026•0 citations

Lattice random walk discretisations of stochastic differential equations

Samuel Duffield, Maxwell Aifer, Denis Melanson +2 more

Abstract We introduce a lattice random walk discretisation scheme for stochastic differential equations (SDEs) that samples binary or ternary increments at each step, suppressing complex drift and diffusion computations to simple 1 or 2 bit random values. This approach is a significant departure from traditional floating point discretisations and offers several advantages; including compatibility with stochastic computing architectures that avoid floating-point arithmetic in place of directly manipulating the underlying probability distribution of a bitstream, elimination of Gaussian sampling requirements, robustness to quantisation errors, and handling of non-Lipschitz drifts. We prove weak convergence and demonstrate the advantages through experiments on various SDEs, including state-of-the-art diffusion models.

arXiv:2508.20883•npj Unconventional Computing•Aug 14, 2026•0 citations

Quantum Algorithms for Stochastic Differential Equations: Achieving Polynomial and Super-Polynomial Speedups for High-Dimensional Systems

Yalla Jnan Devi Satya Prasad

Stochastic differential equations (SDEs) model noisy dynamical systems across quantitative finance, chemistry, physics, and climate science. Classical solvers-Euler-Maruyama schemes, Monte Carlo methods, and finite-difference PDE solvers for Fokker-Planck equations-suffer from exponential growth in computational cost with dimension and accuracy requirements. We present a family of quantum algorithms for simulating and solving SDEs with improved scaling. Our approach combines Hamiltonian simulation for drift terms, quantum random number generation for noise increments, and quantum amplitude estimation for computing expectations. For linear and semilinear SDEs with Lipschitz coefficients, we prove that relevant quantities (option prices, expected hitting times, moments) can be estimated to accuracy ε in time Õ(poly(d)polylog(1/ε)), versus classical O(poly(d)/ε 2). For nonlinear SDEs, we introduce variational quantum schemes leveraging parameterized circuits, with a priori error bounds and trainability analysis avoiding barren plateaus. We analyze multi-asset Black-Scholes models, Heston stochastic volatility, and Langevin dynamics for molecular coarse-graining, quantifying resource requirements (qubits, gate depth, oracle calls). Numerical simulations on small instances demonstrate polynomial-to-super-polynomial empirical speedups in accuracy for fixed runtime, establishing SDE solving as a promising quantum-accelerated task with practical applications.

•Jan 5, 2026•0 citations

High-Dimensional Function Approximation: Breaking the Curse with Monte Carlo Methods

Robert J. Kunsch

In this dissertation we study the tractability of the information-based complexity $n(\varepsilon,d)$ for $d$-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $d$. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the $L_{\infty}$-approximation of certain classes of $C^{\infty}$-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the $L_{\infty}$-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the $L_1$-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ only.

arXiv:1704.08213•Apr 26, 2017•8 citations

Quantum Speedups for Derivative Pricing Beyond Black-Scholes

Dylan Herman, Yue Sun, Jin-Peng Liu +5 more

This paper explores advancements in quantum algorithms for derivative pricing of exotics, a computational pipeline of fundamental importance in quantitative finance. For such cases, the classical Monte Carlo integration procedure provides the state-of-the-art provable, asymptotic performance: polynomial in problem dimension and quadratic in inverse-precision. While quantum algorithms are known to offer quadratic speedups over classical Monte Carlo methods, end-to-end speedups have been proven only in the simplified setting over the Black-Scholes geometric Brownian motion (GBM) model. This paper extends existing frameworks to demonstrate novel quadratic speedups for more practical models, such as the Cox-Ingersoll-Ross (CIR) model and a variant of Heston's stochastic volatility model, utilizing a characteristic of the underlying SDEs which we term fast-forwardability. Additionally, for general models that do not possess the fast-forwardable property, we introduce a quantum Milstein sampler, based on a novel quantum algorithm for sampling Lévy areas, which enables quantum multi-level Monte Carlo to achieve quadratic speedups for multi-dimensional stochastic processes exhibiting certain correlation types. We also present an improved analysis of numerical integration for derivative pricing, leading to substantial reductions in the resource requirements for pricing GBM and CIR models. Furthermore, we investigate the potential for additional reductions using arithmetic-free quantum procedures. Finally, we critique quantum partial differential equation (PDE) solvers as a method for derivative pricing based on amplitude estimation, identifying theoretical barriers that obstruct achieving a quantum speedup through this approach. Our findings significantly advance the understanding of quantum algorithms in derivative pricing, addressing key challenges and open questions in the field.

quant-pharXiv:2602.03725•Feb 4, 2026•0 citations

A Monte Carlo method for integration of multivariate smooth functions I: Sobolev spaces

Mario Ullrich

We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces $H^s_p$ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge2$, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.

•Apr 20, 2016•1 citation
In this thesis we study a variant of the quadrature problem for stochastic differential equations (SDEs), namely the approximation of expectations (\mathrm{E}(f(X))), where (X = (X(t)){t \in [0,1]}) is the solution of an SDE and (f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R}) is a functional, mapping each realization of (X) into the real numbers. The distinctive feature in this work is that we consider randomized (Monte Carlo) algorithms with random bits as their only source of randomness, whereas the algorithms commonly studied in the literature are allowed to sample from the uniform distribution on the unit interval, i.e., they do have access to random numbers from ([0,1]). By assumption, all further operations like, e.g., arithmetic operations, evaluations of elementary functions, and oracle calls to evaluate (f) are considered within the real number model of computation, i.e., they are carried out exactly. In the following, we provide a detailed description of the quadrature problem, namely we are interested in the approximation of \begin{align*} S(f) = \mathrm{E}(f(X)) \end{align*} for (X) being the (r)-dimensional solution of an autonomous SDE of the form \begin{align*} \mathrm{d}X(t) = a(X(t)) , \mathrm{d}t + b(X(t)) , \mathrm{d}W(t), \quad t \in [0,1], \end{align*} with deterministic initial value \begin{align*} X(0) = x_0 \in \mathbb{R}^r, \end{align*} and driven by a (d)-dimensional standard Brownian motion (W). Furthermore, the drift coefficient (a \colon \mathbb{R}^r \to \mathbb{R}^r) and the diffusion coefficient (b \colon \mathbb{R}^r \to \mathbb{R}^{r \times d}) are assumed to be globally Lipschitz continuous. For the function classes \begin{align*} F{\infty} = \bigl{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq |x-y|{\sup}\bigr} \end{align*} and \begin{align*} F_p = \bigl{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq |x-y|{L_p}\bigr}, \quad 1 \leq p < \infty. \end{align*} we have established the following. [] (\textit{Theorem 1.}) There exists a random bit multilevel Monte Carlo (MLMC) algorithm (M) using [ L = L(\varepsilon,F) = \begin{cases}\lceil{\log_2(\varepsilon^{-2}}\rceil, &\text{if} \ F = F_p,\ \lceil{\log_2(\varepsilon^{-2} + \log_2(\log_2(\varepsilon^{-1}))}\rceil, &\text{if} \ F = F_\infty \end{cases} ] and replication numbers [ N_\ell = N_\ell(\varepsilon,F) = \begin{cases} \lceil{(L+1) \cdot 2^{-\ell} \cdot \varepsilon^{-2}}\rceil, & \text{if} \ F = F_p,\ \lceil{(L+1) \cdot 2^{-\ell} \cdot \max(\ell,1) \cdot \varepsilon^{-2}}\rceil, & \text{if} \ F=f_\infty \end{cases} ] for (\ell = 0,\ldots,L), for which exists a positive constant (c) such that \begin{align*} \mathrm{error}(M,F) = \sup_{f \in F} \bigl(\mathrm{E}(S(f) - M(f))^2\bigr)^{1/2} \leq c \cdot \varepsilon \end{align*} and \begin{align*} \mathrm{cost}(M,F) = \sup_{f \in F} \mathrm{E}(\mathrm{cost}(M,f)) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for every (\varepsilon \in {]0,1/2[}). [] Hence, in terms of the (\varepsilon)-complexity \begin{align*} \mathrm{comp}(\varepsilon,F) = \inf\bigl{\mathrm{cost}(M,F) \colon M \ \text{is a random bit MC algorithm}, \mathrm{error}(M,F) \leq \varepsilon\bigr} \end{align*} we have established the upper bound \begin{align*} \mathrm{comp}(\varepsilon,F) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for some positive constant (c). That is, we have shown the same weak asymptotic upper bound as in the case of random numbers from ([0,1]). Hence, in this sense, random bits are almost as powerful as random numbers for our computational problem. Moreover, we present numerical results for a non-analyzed adaptive random bit MLMC Euler algorithm, in the particular cases of the Brownian motion, the geometric Brownian motion, the Ornstein-Uhlenbeck SDE and the Cox-Ingersoll-Ross SDE. We also provide a numerical comparison to the corresponding adaptive random number MLMC Euler method. A key challenge in the analysis of the algorithm in Theorem 1 is the approximation of probability distributions by means of random bits. A problem very closely related to the quantization problem, i.e., the optimal approximation of a given probability measure (on a separable Hilbert space) by means of a probability measure with finite support size. Though we have shown that the random bit approximation of the standard normal distribution is 'harder' than the corresponding quantization problem (lower weak rate of convergence), we have been able to establish the same weak rate of convergence as for the corresponding quantization problem in the case of the distribution of a Brownian bridge on (L_2([0,1])), the distribution of the solution of a scalar SDE on (L_2([0,1])), and the distribution of a centered Gaussian random element in a separable Hilbert space.
The classical stochastic differential equation given as dX(t,ω)=a(t,X) dt+b(t,X) dQ(t),X(t0)=X0,t∈[t0,T],dX(t, \omega) = a(t, X) \, dt + b(t, X) \, dQ(t), \quad X(t_0) = X_0, \quad t \in [t_0, T],dX(t,ω)=a(t,X)dt+b(t,X)dQ(t),X(t0​)=X0​,t∈[t0​,T], where the driving process Q(t) Q(t) Q(t) is a martingale, and a a a and b b b are adapted functionals has several numerical schemes developed for it, where each exhibits distinct stability and convergence properties depending on the nature of the driving process and the functional space of the solution. A generalization of this equation is the quantum stochastic differential equation introduced by Hudson and Parthasarathy, expressed as dX(t)=E(t,X(t)) dΛπ(t)+F(t,X(t)) dAf†(t)+G(t,X(t)) dAg(t)+H(t,X(t)) dt,dX(t) = E(t, X(t)) \, d\Lambda_\pi(t) + F(t, X(t)) \, dA_f^\dagger(t) + G(t, X(t)) \, dA_g(t) + H(t, X(t)) \, dt,dX(t)=E(t,X(t))dΛπ​(t)+F(t,X(t))dAf†​(t)+G(t,X(t))dAg​(t)+H(t,X(t))dt, where E,F,G, E, F, G, E,F,G, and H H H are stochastic operator-valued functions defined on a Hilbert space. In 1992, Ekhaquere reformulated this equation in an equivalent form involving the non-classical differential equation stated as; ddt⟨η,X(t)ξ⟩=P(t,X(t))⟨η,ξ⟩,X(t0)=X0,t∈[t0,T],\frac{d}{dt} \langle \eta, X(t) \xi \rangle = P(t, X(t)) \langle \eta, \xi \rangle, \quad X(t_0) = X_0, \quad t \in [t_0, T],dtd​⟨η,X(t)ξ⟩=P(t,X(t))⟨η,ξ⟩,X(t0​)=X0​,t∈[t0​,T], which represents an ordinary differential equation of non-classical type. The stochastic process X(t) X(t) X(t) acts as a densely defined linear operator on a tensor product of two Hilbert spaces, one of which is the Boson Fock space. The vectors η \eta η and ξ \xi ξ belong to a dense subset of this tensor product Hilbert space, and the mapping (η,ξ)↦P(t,X)(η,ξ)(\eta, \xi) \mapsto P(t, X)(\eta, \xi)(η,ξ)↦P(t,X)(η,ξ) defines a sesquilinear form for each fixed pair (t,X)(t, X)(t,X). We analyze the numerical approximation of the QSDE using its equivalent inner-product form. The numerical investigation employs three principal methods: the Lagrangian Quadrature Method, the Linear Multistep Scheme, and the Newton–Cotes Method. Each method is carefully designed to ensure the consistency, stability, and convergence of the approximate solution X(t)X(t)X(t) toward the exact stochastic process. These schemes are implemented using Python programming language, which provides a flexible and efficient computational environment for testing the proposed algorithms. Our computational results show that the developed schemes generalize Taylor-type approximations of Itô processes under weak convergence criteria. The proposed algorithms exhibit numerical stability and yield results that compare favorably with analytical benchmarks. Furthermore, the implementation avoids direct approximation of the driving quantum processes, thereby preserving the natural adaptation of the schemes to quantum dynamical models.
Abstract We introduce a lattice random walk discretisation scheme for stochastic differential equations (SDEs) that samples binary or ternary increments at each step, suppressing complex drift and diffusion computations to simple 1 or 2 bit random values. This approach is a significant departure from traditional floating point discretisations and offers several advantages; including compatibility with stochastic computing architectures that avoid floating-point arithmetic in place of directly manipulating the underlying probability distribution of a bitstream, elimination of Gaussian sampling requirements, robustness to quantisation errors, and handling of non-Lipschitz drifts. We prove weak convergence and demonstrate the advantages through experiments on various SDEs, including state-of-the-art diffusion models.
Stochastic differential equations (SDEs) model noisy dynamical systems across quantitative finance, chemistry, physics, and climate science. Classical solvers-Euler-Maruyama schemes, Monte Carlo methods, and finite-difference PDE solvers for Fokker-Planck equations-suffer from exponential growth in computational cost with dimension and accuracy requirements. We present a family of quantum algorithms for simulating and solving SDEs with improved scaling. Our approach combines Hamiltonian simulation for drift terms, quantum random number generation for noise increments, and quantum amplitude estimation for computing expectations. For linear and semilinear SDEs with Lipschitz coefficients, we prove that relevant quantities (option prices, expected hitting times, moments) can be estimated to accuracy ε in time Õ(poly(d)polylog(1/ε)), versus classical O(poly(d)/ε 2). For nonlinear SDEs, we introduce variational quantum schemes leveraging parameterized circuits, with a priori error bounds and trainability analysis avoiding barren plateaus. We analyze multi-asset Black-Scholes models, Heston stochastic volatility, and Langevin dynamics for molecular coarse-graining, quantifying resource requirements (qubits, gate depth, oracle calls). Numerical simulations on small instances demonstrate polynomial-to-super-polynomial empirical speedups in accuracy for fixed runtime, establishing SDE solving as a promising quantum-accelerated task with practical applications.
In this dissertation we study the tractability of the information-based complexity n(ε,d)n(\varepsilon,d)n(ε,d) for ddd-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance ε>0\varepsilon>0ε>0 the complexity n(ε,d)n(\varepsilon,d)n(ε,d) grows exponentially in ddd. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the L∞L_{\infty}L∞​-approximation of certain classes of C∞C^{\infty}C∞-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the L∞L_{\infty}L∞​-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the L1L_1L1​-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance ε>0\varepsilon>0ε>0 the complexity n(ε,d)n(\varepsilon,d)n(ε,d) grows exponentially in d\sqrt{d}d​ only.
This paper explores advancements in quantum algorithms for derivative pricing of exotics, a computational pipeline of fundamental importance in quantitative finance. For such cases, the classical Monte Carlo integration procedure provides the state-of-the-art provable, asymptotic performance: polynomial in problem dimension and quadratic in inverse-precision. While quantum algorithms are known to offer quadratic speedups over classical Monte Carlo methods, end-to-end speedups have been proven only in the simplified setting over the Black-Scholes geometric Brownian motion (GBM) model. This paper extends existing frameworks to demonstrate novel quadratic speedups for more practical models, such as the Cox-Ingersoll-Ross (CIR) model and a variant of Heston's stochastic volatility model, utilizing a characteristic of the underlying SDEs which we term fast-forwardability. Additionally, for general models that do not possess the fast-forwardable property, we introduce a quantum Milstein sampler, based on a novel quantum algorithm for sampling Lévy areas, which enables quantum multi-level Monte Carlo to achieve quadratic speedups for multi-dimensional stochastic processes exhibiting certain correlation types. We also present an improved analysis of numerical integration for derivative pricing, leading to substantial reductions in the resource requirements for pricing GBM and CIR models. Furthermore, we investigate the potential for additional reductions using arithmetic-free quantum procedures. Finally, we critique quantum partial differential equation (PDE) solvers as a method for derivative pricing based on amplitude estimation, identifying theoretical barriers that obstruct achieving a quantum speedup through this approach. Our findings significantly advance the understanding of quantum algorithms in derivative pricing, addressing key challenges and open questions in the field.
We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by n−1/2n^{-1/2}n−1/2 times the L2L_2L2​-norm of the Fourier transform outside a region around the origin, where nnn is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces HpsH^s_pHps​ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is n−s−1/2n^{-s-1/2}n−s−1/2 for p≥2p\ge2p≥2, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than n−1/2n^{-1/2}n−1/2 for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.