Sergiy Zhuk

We present an end-to-end quantum algorithm with provable performance guarantees for simulating a large class of classical nonlinear dynamical systems. The considered dynamical systems are described by stochastic dissipative differential equations with a quadratic nonlinearity satisfying certain sparsity and divergence-free conditions. Our algorithm approximates the expected value of any sparse low-degree polynomial evaluated at the solution of the classical system. The runtime scales poly-logarithmically with the system size and polynomially with the evolution time, inverse error tolerance, and parameters quantifying sparsity, dissipation, and nonlinearity strength. The considered simulation problem is shown to be BQP-complete, providing a strong evidence for a quantum advantage. We benchmark the quantum algorithm via numerical experiments by simulating a vortex flow in the 2D Navier Stokes equation.