A quantum algorithm for linear autonomous differential equations via Padé approximation

Abstract

We propose a novel quantum algorithm for solving linear autonomous ordinary differential equations (ODEs) using the Padé approximation. For linear autonomous ODEs, the discretized solution can be represented by a product of matrix exponentials. The proposed algorithm approximates the matrix exponential by the diagonal Padé approximation, which is then encoded into a large, block-sparse linear system and solved via quantum linear system algorithms (QLSA). The detailed quantum circuit is given based on quantum oracle access to the matrix, the inhomogeneous term, and the initial state. The complexity of the proposed algorithm is analyzed. Compared to the method based on Taylor approximation, which approximates the matrix exponential using a $k$-th order Taylor series, the proposed algorithm improves the approximation order $k$ from two perspectives: 1) the explicit complexity dependency on $k$ is improved, and 2) a smaller $k$ suffices for the same precision. Numerical experiments demonstrate the advantages of the proposed algorithm comparing to other related algorithms.

51 pages, 15 figures

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Quantum simulation of Maxwell's equations via Schrödingersation
• Dilation theorem via Schrödingerisation, with applications to the quantum simulation of differential equations
• Quantum simulation of the Fokker-Planck equation via Schrodingerization
• Analog quantum simulation of parabolic partial differential equations using Jaynes-Cummings-like models
• Structure-preserving quantum algorithms for linear and nonlinear Hamiltonian systems
• Investigation on a quantum algorithm for linear differential equations