Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
arXiv:2307.09593 · doi:10.22331/q-2024-10-24-1509
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 (17)
- Quantum algorithm for solving linear systems of equations
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Preconditioned quantum linear system algorithm
- High-order quantum algorithm for solving linear differential equations
- Efficient quantum algorithm for dissipative nonlinear differential equations
- A quantum linear system algorithm for dense matrices
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- Quantum algorithms and the finite element method
- Quantum algorithm and circuit design solving the Poisson equation
- High-precision quantum algorithms for partial differential equations
- Quantum Algorithm for Simulating the Wave Equation
- Quantum spectral methods for differential equations
- Improved quantum algorithms for linear and nonlinear differential equations
- Quantum algorithm for non-homogeneous linear partial differential equations
- Quantum Algorithm for the Vlasov Equation
- Algebraic recasting of nonlinear systems of ODEs into universal formats
- Optimal state discrimination and unstructured search in nonlinear quantum mechanics
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