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

arXiv:2406.01889 · Physical Review A

Dividing quantum circuits for the time evolution of stochastic processes by orthogonal-series-density estimation

Koichi Miyamoto

Published Apr 25, 2025• 2 citations
arXivHTMLPDF

Abstract

Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables, with applications in various industrial fields such as financial derivative pricing. When QMCI is applied to expectations concerning a stochastic process $X(t)$, e.g., an underlying asset price in derivative pricing, the quantum circuit ${U}_{X(t)}$ to generate the quantum state encoding the probability density of $X(t)$ can have a large depth. With time discretized into $N$ points, using state-preparation oracles for the transition probabilities of $X(t)$, the state preparation for $X(t)$ results in a depth of $O(N)$, which may be problematic for large $N$. Moreover, if we estimate expectations concerning $X(t)$ at $N$ time points, the total query complexity scales on $N$ as $O({N}^{2})$, which is worse than the $O(N)$ complexity in the classical Monte Carlo method. In this paper, to improve this, we propose a method to divide ${U}_{X(t)}$ based on orthogonal-series-density estimation. This approach involves approximating the densities of $X(t)$ at $N$ time points with orthogonal series, where the coefficients are estimated as expectations of the orthogonal functions by QMCI. By using these approximated densities, we can estimate expectations concerning $X(t)$ by QMCI without requiring deep circuits. Our error and complexity analysis shows that to obtain the approximated densities at $N$ time points, our method achieves the circuit depth and total query complexity scaling as $O(\sqrt{N})$ and $O({N}^{3/2})$, respectively.

DOI
10.1103/physreva.111.042431

Related papers

Quantum algorithm for solving McKean-Vlasov stochastic differential equations

Koichi Miyamoto

Quantum Monte Carlo integration (QMCI), a quantum algorithm for calculating expectations that provides a quadratic speed-up compared to its classical counterpart, is now attracting increasing interest in the context of its industrial and scientific applications. In this paper, we propose the first application of QMCI to solving McKean-Vlasov stochastic differential equations (MVSDEs), a nonlinear class of SDEs whose drift and diffusion coefficients depend on the law \(\mu _{t}\) of the solution \(X_{t}\) —appearing in fields such as finance and fluid mechanics. We focus on the problem setting where the coefficients depend on \(\mu _{t}\) through expectations of some functions \(\mathbb{E}[\varphi _{k}(X_{t})]\) , and the goal is to compute the expectation of a function \(\mathbb{E}[\phi (X_{T})]\) at a terminal time T . We devise a quantum algorithm that leverages QMCI to compute these expectations, combined with a high-order time discretization method for SDEs and extrapolation of the expectations in time. The proposed algorithm estimates \(\mathbb{E}[\phi (X_{T})]\) with accuracy ϵ , making \(O(1/\epsilon ^{1+2/p})\) queries to the quantum circuit for time evolution over one step, where \(p\in (1,2]\) is the weak order of the SDE discretization method. This demonstrates the speed-up over the well-known classical algorithm called the particle method with complexity of \(O(1/\epsilon ^{3})\) . We conduct numerical demonstrations of our quantum algorithm applied to examples of MVSDEs, with some parts emulated classically, and observe that the accuracy and complexity behave as expected.

arXiv:2507.10926•EPJ Quantum Technology•Dec 10, 2025•0 citations

Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage

Paolo Recchia, Zhan Yu, Kelvin Koor +1 more

Numerical integration with Monte Carlo methods is a central computational task in many scientific and industrial applications, including financial derivative pricing and risk management. Classical Monte Carlo algorithms are computationally demanding: achieving an accuracy $ε$ typically requires a number of function evaluations scaling as $O(1/ε^2)$. Quantum-accelerated Monte Carlo methods based on quantum amplitude estimation can in principle quadratically improve this dependence. However, \textit{quasi}-Monte Carlo methods have not been explored in the quantum context. In this work, we introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation. The proposed method prepares the quasi-random point set coherently in superposition. The method does not yield an asymptotic improvement over classical quasi-Monte Carlo, since the total error separates into a discretization error, determined by the finite net, and a quantum estimation error. Instead, we explore a pre-asymptotic advantage window: for a target accuracy that would classically require $2^q$ low discrepancy points, one can prepare a higher-resolution net of size $2^Q$, with $Q>q$, in superposition and reach the same accuracy using significantly fewer function queries. This window can be controlled by tuning the circuit resolution and amplitude-estimation parameters, making the approach relevant for practical regimes where the number of queries is finite rather than asymptotically large.

quant-pharXiv:2609.03625•Sep 4, 2026•0 citations

Quantum algorithms for Monte Carlo integration using pseudo-random numbers

Koichi Miyamoto

Quantum algorithms for Monte Carlo integration (QMCI), which are based on quantum amplitude estimation (QAE), provide quadratic speed-up compared with classical counterparts, and are therefore widely investigated, along with applications to industries such as finance. One typical feature of problems in finance is high dimensionality, or, in other words, the necessity to create numerous random numbers (RNs) to calculate the integrand. In such a situation, the original implementation of QMCI, in which states encoding the probability distributions of the RNs are generated on different quantum registers, requires a large number of qubits. In this poster, we propose an implementation of QMCI, in which pseudo-random numbers (PRNs) are sequentially generated on one register, and therefore the qubit number is tremendously reduced. Moreover, we show that, when the integrand has the form such that contributions from different RNs are separable into different terms, we can also achieve time complexity reduction with respect to the number of dimensions by combining the nested QAE and use of PRNs.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•3 citations

Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth

Steven Herbert

This paper proposes a method of quantum Monte Carlo integration that retains the full quadratic quantum advantage, without requiring any arithmetic or quantum phase estimation to be performed on the quantum computer. No previous proposal for quantum Monte Carlo integration has achieved all of these at once. The heart of the proposed method is a Fourier series decomposition of the sum that approximates the expectation in Monte Carlo integration, with each component then estimated individually using quantum amplitude estimation. The main result is presented as theoretical statement of asymptotic advantage, and numerical results are also included to illustrate the practical benefits of the proposed method. The method presented in this paper is the subject of a patent application [Quantum Computing System and Method: Patent application GB2102902.0 and SE2130060-3].

arXiv:2105.09100•Quantum•Sep 29, 2022•61 citations

A quantum spectral method for simulating stochastic processes, with applications to Monte Carlo

Adam Bouland, Aditi Dandapani, Anupam Prakash

Stochastic processes play a fundamental role in physics, mathematics, engineering and finance. One potential application of quantum computation is to better approximate properties of stochastic processes. For example, quantum algorithms for Monte Carlo estimation combine a quantum simulation of a stochastic process with amplitude estimation to improve mean estimation. In this work we study quantum algorithms for simulating stochastic processes which are compatible with Monte Carlo methods. We introduce a new ``analog'' quantum representation of stochastic processes, in which the value of the process at time t is stored in the amplitude of the quantum state, enabling an exponentially efficient encoding of process trajectories. We show that this representation allows for highly efficient quantum algorithms for simulating certain stochastic processes, using spectral properties of these processes combined with the quantum Fourier transform. In particular, we show that we can simulate $T$ timesteps of fractional Brownian motion using a quantum circuit with gate complexity $\text{polylog}(T)$, which coherently prepares the superposition over Brownian paths. We then show this can be combined with quantum mean estimation to create end to end algorithms for estimating certain time averages over processes in time $O(\text{polylog}(T)ε^{-c})$ where $3/2

arXiv:2303.06719•Mar 12, 2023•9 citations

Every Classical Sampling Circuit is a Quantum Sampling Circuit

Steven Herbert

This note introduces "Q-marginals", which are quantum states encoding some probability distribution in a manner suitable for use in Quantum Monte Carlo Integration (QMCI), and shows that these can be prepared directly from a classical circuit sampling for the probability distribution of interest. This result is important as the quantum advantage in Monte Carlo integration is in the form of a reduction in the number of uses of a quantum state encoding the probability distribution (in QMCI) relative to the number of samples that would be required in classical MCI -- hence it only translates into a computational advantage if the number of operations required to prepare this quantum state encoding the probability distribution is comparable to the number of operations required to generate a classical sample (as the Q-marginal construction achieves).

arXiv:2109.04842•Sep 10, 2021•3 citations
Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables, with applications in various industrial fields such as financial derivative pricing. When QMCI is applied to expectations concerning a stochastic process X(t)X(t)X(t), e.g., an underlying asset price in derivative pricing, the quantum circuit UX(t){U}_{X(t)}UX(t)​ to generate the quantum state encoding the probability density of X(t)X(t)X(t) can have a large depth. With time discretized into NNN points, using state-preparation oracles for the transition probabilities of X(t)X(t)X(t), the state preparation for X(t)X(t)X(t) results in a depth of O(N)O(N)O(N), which may be problematic for large NNN. Moreover, if we estimate expectations concerning X(t)X(t)X(t) at NNN time points, the total query complexity scales on NNN as O(N2)O({N}^{2})O(N2), which is worse than the O(N)O(N)O(N) complexity in the classical Monte Carlo method. In this paper, to improve this, we propose a method to divide UX(t){U}_{X(t)}UX(t)​ based on orthogonal-series-density estimation. This approach involves approximating the densities of X(t)X(t)X(t) at NNN time points with orthogonal series, where the coefficients are estimated as expectations of the orthogonal functions by QMCI. By using these approximated densities, we can estimate expectations concerning X(t)X(t)X(t) by QMCI without requiring deep circuits. Our error and complexity analysis shows that to obtain the approximated densities at NNN time points, our method achieves the circuit depth and total query complexity scaling as O(N)O(\sqrt{N})O(N​) and O(N3/2)O({N}^{3/2})O(N3/2), respectively.
Quantum Monte Carlo integration (QMCI), a quantum algorithm for calculating expectations that provides a quadratic speed-up compared to its classical counterpart, is now attracting increasing interest in the context of its industrial and scientific applications. In this paper, we propose the first application of QMCI to solving McKean-Vlasov stochastic differential equations (MVSDEs), a nonlinear class of SDEs whose drift and diffusion coefficients depend on the law μt\mu _{t}μt​ of the solution XtX_{t}Xt​ —appearing in fields such as finance and fluid mechanics. We focus on the problem setting where the coefficients depend on μt\mu _{t}μt​ through expectations of some functions E[φk(Xt)]\mathbb{E}[\varphi _{k}(X_{t})]E[φk​(Xt​)] , and the goal is to compute the expectation of a function E[ϕ(XT)]\mathbb{E}[\phi (X_{T})]E[ϕ(XT​)] at a terminal time T . We devise a quantum algorithm that leverages QMCI to compute these expectations, combined with a high-order time discretization method for SDEs and extrapolation of the expectations in time. The proposed algorithm estimates E[ϕ(XT)]\mathbb{E}[\phi (X_{T})]E[ϕ(XT​)] with accuracy ϵ , making O(1/ϵ1+2/p)O(1/\epsilon ^{1+2/p})O(1/ϵ1+2/p) queries to the quantum circuit for time evolution over one step, where p∈(1,2]p\in (1,2]p∈(1,2] is the weak order of the SDE discretization method. This demonstrates the speed-up over the well-known classical algorithm called the particle method with complexity of O(1/ϵ3)O(1/\epsilon ^{3})O(1/ϵ3) . We conduct numerical demonstrations of our quantum algorithm applied to examples of MVSDEs, with some parts emulated classically, and observe that the accuracy and complexity behave as expected.
Numerical integration with Monte Carlo methods is a central computational task in many scientific and industrial applications, including financial derivative pricing and risk management. Classical Monte Carlo algorithms are computationally demanding: achieving an accuracy εεε typically requires a number of function evaluations scaling as O(1/ε2)O(1/ε^2)O(1/ε2). Quantum-accelerated Monte Carlo methods based on quantum amplitude estimation can in principle quadratically improve this dependence. However, \textit{quasi}-Monte Carlo methods have not been explored in the quantum context. In this work, we introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation. The proposed method prepares the quasi-random point set coherently in superposition. The method does not yield an asymptotic improvement over classical quasi-Monte Carlo, since the total error separates into a discretization error, determined by the finite net, and a quantum estimation error. Instead, we explore a pre-asymptotic advantage window: for a target accuracy that would classically require 2q2^q2q low discrepancy points, one can prepare a higher-resolution net of size 2Q2^Q2Q, with Q>qQ>qQ>q, in superposition and reach the same accuracy using significantly fewer function queries. This window can be controlled by tuning the circuit resolution and amplitude-estimation parameters, making the approach relevant for practical regimes where the number of queries is finite rather than asymptotically large.
Quantum algorithms for Monte Carlo integration (QMCI), which are based on quantum amplitude estimation (QAE), provide quadratic speed-up compared with classical counterparts, and are therefore widely investigated, along with applications to industries such as finance. One typical feature of problems in finance is high dimensionality, or, in other words, the necessity to create numerous random numbers (RNs) to calculate the integrand. In such a situation, the original implementation of QMCI, in which states encoding the probability distributions of the RNs are generated on different quantum registers, requires a large number of qubits. In this poster, we propose an implementation of QMCI, in which pseudo-random numbers (PRNs) are sequentially generated on one register, and therefore the qubit number is tremendously reduced. Moreover, we show that, when the integrand has the form such that contributions from different RNs are separable into different terms, we can also achieve time complexity reduction with respect to the number of dimensions by combining the nested QAE and use of PRNs.
This paper proposes a method of quantum Monte Carlo integration that retains the full quadratic quantum advantage, without requiring any arithmetic or quantum phase estimation to be performed on the quantum computer. No previous proposal for quantum Monte Carlo integration has achieved all of these at once. The heart of the proposed method is a Fourier series decomposition of the sum that approximates the expectation in Monte Carlo integration, with each component then estimated individually using quantum amplitude estimation. The main result is presented as theoretical statement of asymptotic advantage, and numerical results are also included to illustrate the practical benefits of the proposed method. The method presented in this paper is the subject of a patent application [Quantum Computing System and Method: Patent application GB2102902.0 and SE2130060-3].
Stochastic processes play a fundamental role in physics, mathematics, engineering and finance. One potential application of quantum computation is to better approximate properties of stochastic processes. For example, quantum algorithms for Monte Carlo estimation combine a quantum simulation of a stochastic process with amplitude estimation to improve mean estimation. In this work we study quantum algorithms for simulating stochastic processes which are compatible with Monte Carlo methods. We introduce a new ``analog'' quantum representation of stochastic processes, in which the value of the process at time t is stored in the amplitude of the quantum state, enabling an exponentially efficient encoding of process trajectories. We show that this representation allows for highly efficient quantum algorithms for simulating certain stochastic processes, using spectral properties of these processes combined with the quantum Fourier transform. In particular, we show that we can simulate TTT timesteps of fractional Brownian motion using a quantum circuit with gate complexity polylog(T)\text{polylog}(T)polylog(T), which coherently prepares the superposition over Brownian paths. We then show this can be combined with quantum mean estimation to create end to end algorithms for estimating certain time averages over processes in time O(polylog(T)ε−c)O(\text{polylog}(T)ε^{-c})O(polylog(T)ε−c) where $3/2
This note introduces "Q-marginals", which are quantum states encoding some probability distribution in a manner suitable for use in Quantum Monte Carlo Integration (QMCI), and shows that these can be prepared directly from a classical circuit sampling for the probability distribution of interest. This result is important as the quantum advantage in Monte Carlo integration is in the form of a reduction in the number of uses of a quantum state encoding the probability distribution (in QMCI) relative to the number of samples that would be required in classical MCI -- hence it only translates into a computational advantage if the number of operations required to prepare this quantum state encoding the probability distribution is comparable to the number of operations required to generate a classical sample (as the Q-marginal construction achieves).