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

Dekuan Dong; Yingzhou Li; Jungong Xue

doi:10.22331/q-2025-06-17-1770

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

Dekuan Dong¹, Yingzhou Li^1,2, and Jungong Xue¹

¹School of Mathematical Sciences, Fudan University
²Shanghai Key Laboratory for Contemporary Applied Mathematics

Published:	2025-06-17, volume 9, page 1770
Editor:	Jin-Peng Liu
Eprint:	arXiv:2504.06948v3
Doi:	https://doi.org/10.22331/q-2025-06-17-1770
Citation:	Quantum 9, 1770 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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.

Popular summary

Solving differential equations lies at the core of modeling physical systems—from predicting how planets move to simulating electrical circuits or understanding quantum systems. A common and important class of these problems involves linear autonomous ordinary differential equations (ODEs), where the system’s rules remain constant over time. While classical computers can handle these equations, the computational cost grows rapidly with the size of the system. In contrast, quantum algorithms offer promising advantages for solving large-scale ODEs.

In this paper, we introduce a new quantum algorithm that addresses linear autonomous differential equations by combining insights from numerical analysis and quantum computing. Instead of the traditional Taylor series, we use the Padé approximation, which provides a more accurate and efficient way to approximate matrix exponentials—a crucial step in solving such equations. This approximation is then encoded into a structured linear system, which can be efficiently solved using quantum linear system algorithms (QLSA).

Our approach achieves two key improvements in the approximation order $k$: 1) the explicit complexity dependency on $k$ is improved, and 2) a smaller $k$ suffices for the same precision. We also provide a detailed construction of the quantum circuit needed for this algorithm. This work strengthens the link between classical numerical techniques and quantum computing, and marks a step toward more efficient quantum solutions of differential equations.

► BibTeX data

@article{Dong2025quantumalgorithm,
  doi = {10.22331/q-2025-06-17-1770},
  url = {https://doi.org/10.22331/q-2025-06-17-1770},
  title = {A quantum algorithm for linear autonomous differential equations via {P}ad{\'{e}} approximation},
  author = {Dong, Dekuan and Li, Yingzhou and Xue, Jungong},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1770},
  month = jun,
  year = {2025}
}

► References

[1] Awad H. Al-Mohy and Nicholas J. Higham. A new scaling and squaring algorithm for the matrix exponential. SIAM Journal on Matrix Analysis and Applications, 31 (3): 970–989, 2010. 10.1137/09074721X. URL https://doi.org/10.1137/09074721X.
https://doi.org/10.1137/09074721X

[2] Dong An, Andrew M. Childs, and Lin Lin. Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters. ArXiv, abs/2312.03916, 2023a. URL https://doi.org/10.48550/arXiv.2312.03916.
https://doi.org/10.48550/arXiv.2312.03916

[3] Dong An, Jin-Peng Liu, and Lin Lin. Linear combination of hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. Phys. Rev. Lett., 131: 150603, Oct 2023b. 10.1103/PhysRevLett.131.150603. URL https://doi.org/10.1103/PhysRevLett.131.150603.
https://doi.org/10.1103/PhysRevLett.131.150603

[4] Dominic W Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 47 (10): 105301, feb 2014. 10.1088/1751-8113/47/10/105301. URL https://dx.doi.org/10.1088/1751-8113/47/10/105301.
https://doi.org/10.1088/1751-8113/47/10/105301

[5] Dominic W. Berry and Pedro C. S. Costa. Quantum algorithm for time-dependent differential equations using Dyson series. Quantum, 8: 1369, June 2024. ISSN 2521-327X. 10.22331/q-2024-06-13-1369. URL https://doi.org/10.22331/q-2024-06-13-1369.
https://doi.org/10.22331/q-2024-06-13-1369

[6] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, 2015. 10.1109/FOCS.2015.54. URL https://doi.org/10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54

[7] Dominic W Berry, Andrew M Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356: 1057–1081, 2017. 10.1007/s00220-017-3002-y. URL https://doi.org/10.1007/s00220-017-3002-y.
https://doi.org/10.1007/s00220-017-3002-y

[8] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation, 2002. ISSN 0271-4132. URL https://doi.org/10.48550/arXiv.quant-ph/0005055.
https://doi.org/10.48550/arXiv.quant-ph/0005055
arXiv:quant-ph/0005055

[9] Daan Camps and Roel Van Beeumen. FABLE: Fast Approximate Quantum Circuits for Block-Encodings . In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 104–113, Los Alamitos, CA, USA, September 2022. IEEE Computer Society. 10.1109/QCE53715.2022.00029. URL https://doi.org/10.1109/QCE53715.2022.00029.
https://doi.org/10.1109/QCE53715.2022.00029

[10] Yu Cao, Shi Jin, and Nana Liu. Quantum simulation for time-dependent hamiltonians – with applications to non-autonomous ordinary and partial differential equations, 2023. URL https://doi.org/10.48550/arXiv.2312.02817.
https://doi.org/10.48550/arXiv.2312.02817

[11] Andrew M. Childs and Jin-Peng Liu. Quantum spectral methods for differential equations. Communications in Mathematical Physics, 375: 1427 – 1457, 2019. URL https://doi.org/10.1007/s00220-020-03699-z.
https://doi.org/10.1007/s00220-020-03699-z

[12] Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3: 040303, Oct 2022. 10.1103/PRXQuantum.3.040303. URL https://doi.org/10.1103/PRXQuantum.3.040303.
https://doi.org/10.1103/PRXQuantum.3.040303

[13] Xiaojing Dong, Yizhe Peng, Qili Tang, Yin Yang, and Yue Yu. Investigation on a quantum algorithm for linear differential equations, 2024. URL https://doi.org/10.48550/arXiv.2408.01762.
https://doi.org/10.48550/arXiv.2408.01762

[14] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. 10.1145/3313276.3316366. URL https://doi.org/10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[15] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103: 150502, Oct 2009. 10.1103/PhysRevLett.103.150502. URL https://doi.org/10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[16] Nicholas J. Higham. The scaling and squaring method for the matrix exponential revisited. SIAM Journal on Matrix Analysis and Applications, 26 (4): 1179–1193, 2005. 10.1137/04061101X. URL https://doi.org/10.1137/04061101X.
https://doi.org/10.1137/04061101X

[17] Junpeng Hu, Shi Jin, Nana Liu, and Lei Zhang. Dilation theorem via schrödingerisation, with applications to the quantum simulation of differential equations, 2023. URL https://doi.org/10.48550/arXiv.2309.16262.
https://doi.org/10.48550/arXiv.2309.16262

[18] Junpeng Hu, Shi Jin, Nana Liu, and Lei Zhang. Quantum Circuits for partial differential equations via Schrödingerisation. Quantum, 8: 1563, December 2024a. ISSN 2521-327X. 10.22331/q-2024-12-12-1563. URL https://doi.org/10.22331/q-2024-12-12-1563.
https://doi.org/10.22331/q-2024-12-12-1563

[19] Junpeng Hu, Shi Jin, and Lei Zhang. Quantum algorithms for multiscale partial differential equations. Multiscale Modeling & Simulation, 22 (3): 1030–1067, 2024b. 10.1137/23M1566340. URL https://doi.org/10.1137/23M1566340.
https://doi.org/10.1137/23M1566340

[20] Shi Jin and Nana Liu. Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via schrodingerisation, 2023. URL https://doi.org/10.48550/arXiv.2304.02865.
https://doi.org/10.48550/arXiv.2304.02865

[21] Shi Jin and Nana Liu. Analog quantum simulation of partial differential equations. Quantum Science and Technology, 9 (3): 035047, jun 2024a. 10.1088/2058-9565/ad49cf. URL https://dx.doi.org/10.1088/2058-9565/ad49cf.
https://doi.org/10.1088/2058-9565/ad49cf

[22] Shi Jin and Nana Liu. Analog quantum simulation of parabolic partial differential equations using jaynes-cummings-like models, 2024b. URL https://doi.org/10.48550/arXiv.2407.01913.
https://doi.org/10.48550/arXiv.2407.01913

[23] Shi Jin, Nana Liu, and Yue Yu. Quantum simulation of partial differential equations via schrodingerisation, 2022. URL https://doi.org/10.48550/arXiv.2212.13969.
https://doi.org/10.48550/arXiv.2212.13969

[24] Shi Jin, Nana Liu, and Chuwen Ma. Quantum simulation of maxwell's equations via schrödingersation, 2023a. URL https://doi.org/10.48550/arXiv.2308.08408.
https://doi.org/10.48550/arXiv.2308.08408

[25] Shi Jin, Nana Liu, and Yue Yu. Quantum simulation of partial differential equations: Applications and detailed analysis. Phys. Rev. A, 108: 032603, Sep 2023b. 10.1103/PhysRevA.108.032603. URL https://doi.org/10.1103/PhysRevA.108.032603.
https://doi.org/10.1103/PhysRevA.108.032603

[26] Shi Jin, Xiantao Li, Nana Liu, and Yue Yu. Quantum simulation for partial differential equations with physical boundary or interface conditions. Journal of Computational Physics, 498: 112707, 2024a. ISSN 0021-9991. 10.1016/j.jcp.2023.112707. URL https://doi.org/10.1016/j.jcp.2023.112707.
https://doi.org/10.1016/j.jcp.2023.112707

[27] Shi Jin, Xiantao Li, Nana Liu, and Yue Yu. Quantum simulation for quantum dynamics with artificial boundary conditions. SIAM Journal on Scientific Computing, 46 (4): B403–B421, 2024b. 10.1137/23M1563451. URL https://doi.org/10.1137/23M1563451.
https://doi.org/10.1137/23M1563451

[28] Shi Jin, Nana Liu, and Chuwen Ma. Schrödingerisation based computationally stable algorithms for ill-posed problems in partial differential equations, 2024c. URL https://doi.org/10.48550/arXiv.2403.19123.
https://doi.org/10.48550/arXiv.2403.19123

[29] Shi Jin, Nana Liu, and Chuwen Ma. On schrödingerization based quantum algorithms for linear dynamical systems with inhomogeneous terms, 2024d. URL https://doi.org/10.48550/arXiv.2402.14696.
https://doi.org/10.48550/arXiv.2402.14696

[30] Shi Jin, Nana Liu, and Yue Yu. Quantum simulation of the fokker-planck equation via schrodingerization, 2024e. URL https://doi.org/10.48550/arXiv.2404.13585.
https://doi.org/10.48550/arXiv.2404.13585

[31] Shi Jin, Nana Liu, and Yue Yu. Quantum circuits for the heat equation with physical boundary conditions via schrodingerisation, 2025. URL https://doi.org/10.48550/arXiv.2407.15895.
https://doi.org/10.48550/arXiv.2407.15895

[32] Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7: 913, February 2023. ISSN 2521-327X. 10.22331/q-2023-02-02-913. URL https://doi.org/10.22331/q-2023-02-02-913.
https://doi.org/10.22331/q-2023-02-02-913

[33] Cleve Moler and Charles Van Loan. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review, 45 (1): 3–49, 2003. 10.1137/S00361445024180. URL https://doi.org/10.1137/S00361445024180.
https://doi.org/10.1137/S00361445024180

[34] Ashley Montanaro. Quantum algorithms: an overview. npj Quantum Information, 2 (1): 15023, Jan 2016. ISSN 2056-6387. 10.1038/npjqi.2015.23. URL https://doi.org/10.1038/npjqi.2015.23.
https://doi.org/10.1038/npjqi.2015.23

[35] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa. Quantum circuits for general multiqubit gates. Phys. Rev. Lett., 93: 130502, Sep 2004. 10.1103/PhysRevLett.93.130502. URL https://doi.org/10.1103/PhysRevLett.93.130502.
https://doi.org/10.1103/PhysRevLett.93.130502

[36] Edwarwd B Saff and Richard S Varga. On the zeros and poles of padé approximants to ez. Numerische Mathematik, 25 (1): 1–14, 1975. 10.1007/BF01411842. URL https://doi.org/10.1007/BF01411842.
https://doi.org/10.1007/BF01411842

[37] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, 1997. 10.1137/S0097539795293172. URL https://doi.org/10.1137/S0097539795293172.
https://doi.org/10.1137/S0097539795293172

[38] Richard S. Varga. On higher order stable implicit methods for solving parabolic partial differential equations. Journal of Mathematics and Physics, 40 (1-4): 220–231, 1961. https://doi.org/10.1002/sapm1961401220.
https://doi.org/10.1002/sapm1961401220

[39] Hsuan-Cheng Wu and Xiantao Li. Structure-preserving quantum algorithms for linear and nonlinear hamiltonian systems, 2025. URL https://doi.org/10.48550/arXiv.2411.03599.
https://doi.org/10.48550/arXiv.2411.03599

Cited by

[1] Kavitha Velusamy, Sowmiya Ramasamy, George Washington Samuelraj Chrysolite, Mallika Arjunan Mani, and Seenith Sivasundaram, "A Residual-Adaptive Preconditioned ψ-Fractional Quantum Pseudo-Spectral Method: Delay-Memory Differential Equations", Mathematics 14 15, 2842 (2026).

[2] Dekuan Dong, Yingzhou Li, and Jungong Xue, "Products between Block-encodings", (2026).

[3] Dekuan Dong, Yingzhou Li, and Jungong Xue, "Products between block-encodings", arXiv:2509.15779, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-12 00:08:07) and SAO/NASA ADS (last updated successfully 2026-08-12 00:08:08). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.