A quantum algorithm for linear autonomous differential equations using Padé approximation
Dekuan Dong, Yingzhou Li, Jungong Xue · 2025
Read A quantum algorithm for linear autonomous differential equations using Padé approximation by Dekuan Dong, Yingzhou Li, Jungong Xue (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06948.txt.
Introduction
Differential equations drive models of motion, circuits, and much more, and quantum computers may one day solve them faster. Dekuan Dong, Yingzhou Li, and Jungong Xue propose a quantum algorithm in 2025 for the steady linear kind. Their method rests on how a matrix exponential, the core of the solution, can be approached by a rational formula called a Padé approximation.
That approximation becomes a large, mostly empty linear system that quantum solvers can attack. Compared with a Taylor series route, their method needs a lower order for the same precision and scales better as order grows. Circuit details and cost counts are given, and numerical tests back the claimed edge over rival algorithms.
Catalog record
| CREATOR | Dekuan Dong, Yingzhou Li, Jungong Xue |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-06948
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A quantum algorithm for linear autonomous differential equations using Padé approximation Dekuan Dong, Yingzhou Li, Jungong Xue 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 k -th order Taylor series, the proposed algorithm improves the approximation order k k from two perspectives: 1) the explicit complexity dependency on k k is improved, and 2) a smaller k k suffices for the same precision. Numerical experiments demonstrate the advantages of the proposed algorithm comparing to other related algorithms. 1 Introduction Quantum computing, which fundamentally differs from classical computing, leverages quantum mechanics to perform computations using quantum states and quantum gates. For many problems, quantum computing offers a theoretical advantage over classical computing. In certain cases, quantum algorithms executed on quantum computers can achieve exponential speedup compared to their classical counterparts [ doi:10.1137/S0097539795293172 , PhysRevLett.103.150502 , Montanaro2016 ] . Solving large-scale ordinary differential equations (ODEs) is one such problem where quantum algorithms show significant potential. Solving large-scale ODEs is a fundamental problem in science, with numerous real-world applications across various domains, including weather and climate prediction, chemical reaction modeling, fluid dynamics, and finance, such as option pricing models, etc. ODEs can generally be divided into two categories: linear ODEs and nonlinear ODEs. In each category, ODEs can further be divided into autonomous and non-autonomous ODEs. A general first-order linear ODEs admit, \begin{cases}\frac{\mathrm{d}\boldsymbol{x}}{\mathrm{d}t}=\boldsymbol{A}(t)\boldsymbol{x}(t)+\boldsymbol{b}(t),\quad t\in[0,T],\\ \boldsymbol{x}(0)=\boldsymbol{x}_{0},\end{cases} (1) where \boldsymbol{A}(t)\in\mathbb{C}^{n\times n} is a matrix or discretized operator, \boldsymbol{b}(t)\in\mathbb{C}^{n} is the inhomogeneous term, \boldsymbol{x}_{0}\in\mathbb{C}^{n} is the initial state, n is the dimension of the system, and T is a final time. When both \boldsymbol{A}(t) and \boldsymbol{b}(t) are time-independent, i.e., \boldsymbol{A}(t)=\boldsymbol{A} and \boldsymbol{b}(t)=\boldsymbol{b} , the ODE system ( 1 ) is referred to as a first-order autonomous ODE system. Given suitable quantum oracles to access \boldsymbol{A} , \boldsymbol{b} , and \boldsymbol{x}_{0} , the goal of this paper is to design an efficient quantum algorithm that produces a quantum state that is \epsilon -close to the final state \left|{\boldsymbol{x}(T)}\right\rangle=\frac{\boldsymbol{x}(T)}{\|\boldsymbol{x}(T)\|_{2}} . Many quantum algorithms for solving linear ODEs ( 1 ) have been proposed in the past decades. These algorithms can be grouped into three categories: a) discretized time steps with Quantum Linear System Algorithm (QLSA); b) time-ordered integral form with Linear Combination of Hamiltonian Simulation (LCHS); c) Schrödingerization with Hamiltonian simulation. The first category differs from the latter two categories in its use of Hamiltonian simulation. Methods in the first category rely on Hamiltonian simulation underlying the QLSA, whereas methods in the latter two categories apply Hamiltonian simulation directly. Mathematically, methods in the latter two categories yield similar final expressions, although their derivation procedures differ significantly. Methods in the first category consist of three steps: discretizing the time variable, encoding the discretized linear differential equation into an enlarged linear system, and solving the resulting linear system using QLSA. This approach was first introduced by [ berry2014high ] , which uses linear multi-step methods to discretize the time variable. However, due to the limitations of the discretization method, the query complexity in [ berry2014high ] is \mathrm{poly}(1/\epsilon) even if the most efficient QLSA is applied. To improve the dependence on the precision \epsilon , berry2017quantum applies a truncated Taylor series to approximate the propagator \exp(\boldsymbol{A}t) for autonomous ODEs and encodes the evaluation process of the truncated Taylor series into a linear system. The dependence on \epsilon is improved to \mathrm{poly}(\log(1/\epsilon)) . The analysis in [ berry2017quantum ] requires \boldsymbol{A} to be diagonalizable, i.e., there exists an invertible matrix \boldsymbol{V} such that \boldsymbol{V}^{-1}\boldsymbol{A}\boldsymbol{V} is a diagonal matrix, and the final complexity depends linearly on the condition number of \boldsymbol{V} , \kappa_{\boldsymbol{V}}=\|\boldsymbol{V}\|_{2}\cdot\|\boldsymbol{V}^{-1}\|_{2} . To eliminate the dependence on \kappa_{\boldsymbol{V}} , krovi2023improved proposes a modified linear system that also encodes the evaluation process of the truncated Taylor series into a linear system, and improves the analysis in [ berry2017quantum ] . In [ krovi2023improved ] , the resulting complexity depends on C(\boldsymbol{A}):=\max_{0\leq t\leq T}\|\exp(\boldsymbol{A}t)\|_{2} instead of \kappa_{\boldsymbol{V}} . More recently, dong2024investigationquantumalgorithmlinear revisited the analysis in [ berry2017quantum ] and obtained a similar complexity result to [ krovi2023improved ] without modifying the linear system. wu2025structurepreservingquantumalgorithmslinear proposed structure-preserving quantum algorithms for both linear and nonlinear Hamiltonian systems. These algorithms maintain the symplectic properties of the underlying dynamics, thereby enhancing the robustness and stability of the numerical methods. Additionally, Childs2019QuantumSM and berry2024quantum generalize methods in this category to address non-autonomous linear ODEs, i.e., time-dependent \boldsymbol{A}(t) and \boldsymbol{b}(t) , using spectral method and Dyson’s series, respectively. The second category of methods originates from [ PhysRevLett.131.150603 ] . These methods are based on a novel integral expression for the non-unitary evolution operator \mathcal{T}e^{\int_{0}^{t}\boldsymbol{A}(s)\mathrm{d}s} , where \mathcal{T} denotes the time-ordering operator. By decomposing \boldsymbol{A}(t) into its Hermitian and anti-Hermitian parts, i.e., \boldsymbol{A}(t)=\boldsymbol{L}(t)+\imath\boldsymbol{H}(t) , where \boldsymbol{L}(t)=\frac{\boldsymbol{A}(t)+\boldsymbol{A}^{\dagger}(t)}{2} and \boldsymbol{H}(t)=\frac{\boldsymbol{A}(t)-\boldsymbol{A}^{\dagger}(t)}{2\imath} , the non-unitary evolution operator can be expressed as an integral, \mathcal{T}e^{\int_{0}^{t}\boldsymbol{A}(s)\mathrm{d}s}=\int_{\mathbb{R}}\frac{1}{\pi(1+k^{2})}\mathcal{T}e^{\imath\int_{0}^{t}(\boldsymbol{H}(s)+k\boldsymbol{L}(s))\mathrm{d}s}\mathrm{d}k. (2) This identity holds under the assumption that \boldsymbol{L}(t) is negative semi-definite, i.e., \boldsymbol{L}(t)\preceq 0 for all t\in[0,T] . Later, in [ An2023QuantumAF ] , a large family of identities similar to eq. 2 is unveiled, and the method in this category is improved to achieve near-optimal dependence on all parameters. The extension to the inhomogeneous case is also possible via Duhamel’s principle. Compared to the methods in the first category, methods in this category consider the non-autonomous cases directly and achieve the optimal state preparation cost. However, methods in this category only give the terminal state, whereas methods in the first category provide information throughout the evolution. The third category of methods is known as Schrödingerization [ jin2022quantumsimulationpartialdifferential , PhysRevA.108.032603 ] . These methods use a warped phase transformation to map the linear differential equation into a higher-dimensional system, where it manifests as a Schrödinger equation in the Fourier space of the extra variable. In this way, the linear ODEs with non-unitary dynamics are converted into a system that evolves under unitary dynamics, i.e., a Schrödinger equation, which can be simulated on quantum computing via Hamiltonian simulation. Schrödingerization has been applied to a wide range of problems, including differential equations with various boundary conditions [ hu2023dilationtheoremschrodingerisationapplications , jin2024schrodingerisationbasedcomputationallystable , jin2024quantumsimulationfokkerplanckequation , jin2023quantumsimulationmaxwellsequations , doi:10.1137/23M1563451 , JIN2024112707 , doi:10.1137/23M1566340 , cao2023quantumsimulationtimedependenthamiltonians ] , iterative methods in numerical linear algebra [ jin2023quantumsimulationdiscretelinear ] , and more. In [ jin2024schrodingerizationbasedquantumalgorithms ] , Schrödingerization is extended to solve linear differential equations with inhomogeneous terms, which is the same problem addressed in this paper. The resulting query complexity depends linearly on 1/\epsilon . More recently, methods in this category have been adapted for analog quantum simulation [ jin2024analogquantumsimulationparabolic , Jin_2024 ] . Explicit quantum circuit implementations corresponding to Schrödingerization have been explored in [ Hu2024quantumcircuits , jin2025quantumcircuitsheatequation ] . We propose