Efficient Quantum Algorithms for Nonlinear Stochastic Dynamical Systems


A. Gnanasekaran, A. Surana and T. Sahai, “Efficient Quantum Algorithms for Nonlinear Stochastic Dynamical Systems,” 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Bellevue, WA, USA, 2023, pp. 66-75, doi: 10.1109/QCE57702.2023.10186. keywords: {Linear systems;Quantum algorithm;Heuristic algorithms;Differential equations;Mathematical models;Complexity theory;Dynamical systems;Fokker-Planck Equation;Stochastic Differential Equations;Quantum algorithm;Linear systems;Chang-Cooper;Finite Difference},


In this paper, we propose efficient quantum algorithms for solving nonlinear stochastic differential equations (SDE) via the associated Fokker-Planck equation (FPE). We discretize the FPE in space and time using two well-known numerical schemes, namely Chang-Cooper and implicit finite difference. We then compute the solution of the resulting system of linear equations using the quantum linear systems algorithm. We present detailed error and complexity analyses for both these schemes and demonstrate that our proposed algorithms, under certain conditions, provably compute the solution to the FPE within prescribed ϵ error bounds with polynomial dependence on state dimension d . Classical numerical methods scale exponentially with dimension, thus, our approach, under the aforementioned conditions, provides an exponential speed-up over traditional approaches.

Read more from SRI