Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach

Shi Jin, Nana Liu, Wei Wei · 2024

Read Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach by Shi Jin, Nana Liu, Wei Wei (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14868.txt.

Introduction

Shi Jin, Nana Liu, and Wei Wei propose, in a 2024 paper, quantum algorithms for equations that mix steady change with random kicks. Such stochastic equations model prices, particles, and many noisy systems. Their method rewrites the random part as a forcing term in an approximate equation, then applies a trick that turns it into a form quantum machines handle well.

The algorithms cover both smooth bell-shaped noise and jumpy heavy-tailed noise. Their cost grows mildly with dimension and sample count, where classic methods can explode. For the smooth case, they prove the approximation converges at first order. Tests on classic processes, from mean-reverting walks to jump flights, matched the theory.

Catalog record

CREATORShi Jin, Nana Liu, Wei Wei
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14868

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach Shi Jin, Nana Liu, Wei Wei Abstract Quantum computers are known for their potential to achieve up-to-exponential speedup compared to classical computers for certain problems. To exploit the advantages of quantum computers, we propose quantum algorithms for linear stochastic differential equations, utilizing the Schrödingerisation method for the corresponding approximate equation by treating the noise term as a (discrete-in-time) forcing term. Our algorithms are applicable to stochastic differential equations with both Gaussian noise and α \alpha -stable Lévy noise. The gate complexity of our algorithms exhibits an 𝒪 ⁡ ( d ​ log ⁡ ( N ​ d ) ) \mathcal{O}(d\log(Nd)) dependence on the dimensions d d and sample sizes N N , where its corresponding classical counterpart requires nearly exponentially larger complexity in scenarios involving large sample sizes. In the Gaussian noise case, we show the strong convergence of first order in the mean square norm for the approximate equations. The algorithms are numerically verified for the Ornstein–Uhlenbeck processes, geometric Brownian motions, and one-dimensional Lévy flights. Keywords: Quantum computing ⋅ \cdot Quantum algorithms ⋅ \cdot Stochastic differential equations ⋅ \cdot Schrödingerisation ⋅ \cdot Strong convergence AMS 2010 Mathematics Subject Classification: 81P68 ⋅ \cdot 68Q12 ⋅ \cdot 65C30 ⋅ \cdot 60H35. 1 Introduction Stochastic differential equations (SDEs) finds applications in various fields including physics, climate modeling, finance and machine learning [ 35 , 46 , 50 ] . Their broad applicability stems from their ability to encapsulate the randomness in nature, providing insights into the dynamics of complex systems with uncertainty. For example, the stochastic Langevin equation and its variants are widely applied in physics and machine learning, including generative AI [ 14 , 16 , 24 , 46 ] . Another important application of SDEs is in Monte Carlo simulations, where SDEs are used to model and simulate random processes over time. For many applications, it becomes interesting to develop quantum algorithms to leverage the potential advantage offered by quantum computers. Quantum computers, which are different from their classical counterparts, use qubits instead of bits. Some of the quantum algorithms have already proved to have quantum advantages over their classical counterparts in, for example, searching [ 20 ] , cryptography [ 45 ] , sampling [ 1 ] , solving linear algebraic equations [ 12 , 21 ] and etc. Quantum algorithms also have applications in computational finance, which is also closely related to SDEs [ 19 , 36 , 43 ] . There are quantum algorithms for stochastic processes that have demonstrated quantum advantage. For example, as an analogue of classical random walk, the quantum walk achieves up-to exponential speedup [ 11 ] and can serve as a universal computational primitive [ 10 ] for simulating arbitrary quantum circuits. It finds wide applications in Hamiltonian simulation, quantum information processing, and search algorithms [ 47 ] . Quantum algorithms have also been proposed for Markov Chain Monte Carlo simulation, commonly used to sample from the Boltzmann distribution [ 38 ] . They potentially ease the computational bottlenecks posed by this sampling problem and achieve quantum speedup in optimization [ 44 ] . Quantum algorithms can also provide nearly quadratic speedup to Monte Carlo methods for computing expected values of random variables [ 4 , 41 , 8 ] . The Lindbladian equation, which describes an open quantum system, can be interpreted as the master equation for the reduced density matrix of a quantum stochastic differential equation. Classical numerical schemes for SDEs also enable quantum computing methods for the Lindbladian equation to achieve arbitrarily high-order accuracy [ 15 ] . Although classical schemes for SDEs, such as the Euler-Maruyama scheme, have been proposed for decades and are widely used in various areas, the quantum algorithms for SDEs are underdeveloped. The motivation for designing quantum algorithms for SDEs arises from the fact that, while simulating a single sample path incurs only a manageable computational cost, achieving a target precision \epsilon with the Monte Carlo method requires at least \mathcal{O}(1/\epsilon^{2}) simulations, leading to substantial computational expense [ 4 ] . Several quantum algorithms have been proposed for SDEs and Monte Carlo simulations. Reference [ 36 ] develops a quantum-classical hybrid algorithm based on variational quantum simulation. It discretizes the SDE into a trinomial tree model and computes the nodes of the tree by time-evolution of a quantum state. The nodes of the tree of each level represent the distribution of the SDE at each time step. However, the tree model itself suffers from insufficient accuracy. Reference [ 41 ] guarantees the near-quadratic speedup of quantum computers in the sampling process of Monte Carlo methods. Based on this, reference [ 4 ] develops quantum algorithms for multi-level Monte Carlo simulation with simulation of SDEs. However, it is developed based on oracles for the expectation of SDEs, and does not offer a concrete quantum algorithm. Reference [ 15 ] uses the relationship between open quantum systems, SDEs, and Hamiltonian simulations to develop high order quantum algorithms for the open quantum system. Thus, quantum algorithms for SDEs that both match the accuracy of classical schemes and offers greater efficiency, are of significant interest. Recently, a Schrödingerisation approach [ 32 , 30 ] has been proposed to solve general linear ordinary and partial differential equations via Hamiltonian simulation, which can also be implemented in quantum circuits [ 22 , 31 ] and applicable to a wide variety of differential equations [ 23 , 27 , 29 , 28 , 33 ] . The method of Schrödingerisation involves the incorporation of an auxiliary variable to transform a linear differential equation into an equation analogous to the Schrödinger equation, with unitary evolution process, in one higher dimension. Subsequently, the transformed equation lends itself to implementation on quantum computers through Hamiltonian simulation. The desired result is recovered from the Schrödingerised equation on a properly chosen interval of the auxiliary variable. This method maintains the major structure of the original classical differential equations, thus, consequently, one can develop quantum algorithms that retain the convergence rate of classical schemes while leveraging the benefits of quantum computing. In this paper, we propose a general quantum algorithm to simulate the solutions of linear SDEs, including SDEs with additive noise and multiplicative noise. The main idea is to treat the noise term as a discrete-in-time forcing term and then uses the Schrödingerisation method for inhomogeneous differential equations [ 29 ] . While most quantum algorithms focus on SDEs with Gaussian noise, our approach is applicable to SDEs driven by stable Lévy processes, which is a more general type of noise. We design the quantum algorithms for the approximate equation through the Schrödingerisation method, which approximates the corresponding SDEs under mean square norm in the Gaussian noise case. We also discuss the important issue of the choice of the recovery interval and its influence on the precision of the final result. Theoretically, for both the additive and multiplicative Gaussian noise cases, we prove the strong convergence of first order for the approximate solution. The quantum advantage of our algorithm is exhibited by its gate complexity of \mathcal{O}(d\log(Nd)) dependence on the dimensions d and the sample size N , which is a nearly exponential speedup compared to its

Read the complete text