Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

Abstract

We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm [Liu et al., PNAS 118, 2021] answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.

21 pages, 5 figures

References in corpus (3)

• Quantum algorithm for solving linear systems of equations
• Quantum algorithm and circuit design solving the Poisson equation
• Algebraic recasting of nonlinear systems of ODEs into universal formats

Cited by in corpus (5)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Quantum Simulation of Nonlinear Dynamical Systems Using Repeated Measurement
• A time-marching quantum algorithm for simulation of the nonlinear Lorenz dynamics
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation