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.

arXiv comment51 pages, 15 figures

References in corpus (25)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Quantum algorithms: an overview
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Circuits for General Multiqubit Gates
• Hamiltonian simulation with nearly optimal dependence on all parameters
• High-order quantum algorithm for solving linear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum spectral methods for differential equations
• Improved quantum algorithms for linear and nonlinear differential equations
• Quantum simulation of partial differential equations via Schrodingerisation: technical details
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Analog quantum simulation of partial differential equations
• Quantum algorithm for time-dependent differential equations using Dyson series
• Quantum Circuits for partial differential equations via Schrödingerisation
• Quantum simulation of Maxwell's equations via Schrödingersation
• Schrödingerisation based computationally stable algorithms for ill-posed problems in partial differential equations
• On Schrödingerization based quantum algorithms for linear dynamical systems with inhomogeneous terms
• Analog quantum simulation of parabolic partial differential equations using Jaynes-Cummings-like models
• Structure-preserving quantum algorithms for linear and nonlinear Hamiltonian systems
• Dilation theorem via Schrödingerisation, with applications to the quantum simulation of differential equations
• Investigation on a quantum algorithm for linear differential equations
• Quantum simulation of the Fokker-Planck equation via Schrodingerization
• Quantum Circuits for the heat equation with physical boundary conditions via Schrodingerisation