Efficient Quantum Algorithms for Nonlinear Stochastic Dynamical Systems

In this paper, we propose an efficient quantum algorithm for solving nonlinear stochastic differential equations (SDE) via the associated Fokker-Planck equation (FPE). We discretize FPE in space and time using the Chang-Cooper scheme, and compute the solution of the resulting system of linear equations using the quantum linear systems algorithm. The Chang-Cooper scheme is second order accurate and satisfies conservativeness and positivity of the solution. We present detailed error and complexity analyses that demonstrate that our proposed quantum scheme, which we call the Quantum Linear Systems Chang-Cooper Algorithm (QLSCCA), computes the solution to the FPE within prescribed $\epsilon$ error bounds with polynomial dependence on state dimension $d$. Classical numerical methods scale exponentially with dimension, thus, our approach provides an \emph{exponential speed-up} over traditional approaches.