Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.06948 · Quantum

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

Dekuan Dong, Yingzhou Li, Jungong Xue

Published Jun 17, 2025• 2 citations
arXivHTMLPDF

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.

DOI
10.22331/q-2025-06-17-1770

Related papers

Improved quantum algorithms for linear and nonlinear differential equations

Hari Krovi

We present substantially generalized and improved quantum algorithms over prior work for inhomogeneous linear and nonlinear ordinary differential equations (ODE). Specifically, we show how the norm of the matrix exponential characterizes the run time of quantum algorithms for linear ODEs opening the door to an application to a wider class of linear and nonlinear ODEs. In \cite{BCOW17}, a quantum algorithm for a certain class of linear ODEs is given, where the matrix involved needs to be diagonalizable. The quantum algorithm for linear ODEs presented here extends to many classes of non-diagonalizable matrices including singular matrices. The algorithm here is also exponentially faster than the bounds derived in \cite{BCOW17} for certain classes of diagonalizable matrices. Our linear ODE algorithm is then applied to nonlinear differential equations using Carleman linearization (an approach taken recently by us in \cite{Liue2026805118}). The improvement over that result is two-fold. First, we obtain an exponentially better dependence on error. This kind of logarithmic dependence on error has also been achieved by \cite{Xue_2021}, but only for homogeneous nonlinear equations. Second, the present algorithm can handle any sparse matrix (that models dissipation) if it has a negative log-norm (including non-diagonalizable matrices), whereas \cite{Liue2026805118} and \cite{Xue_2021} additionally require normality.

arXiv:2202.01054•Quantum•Feb 2, 2023•152 citations

QUANTUM ALGORITHMS FOR DIFFERENTIAL EQUATIONS

Aaron Ostrander

This thesis describes quantum algorithms for Hamiltonian simulation, ordinary differential equations (ODEs), and partial differential equations (PDEs). Product formulas are used to simulate Hamiltonians which can be expressed as a sum of terms which can each be simulated individually. By simulating each of these terms in sequence, the net effect approximately simulates the total Hamiltonian. We find that the error of product formulas can be improved by randomizing over the order in which the Hamiltonian terms are simulated. We prove that this approach is asymptotically better than ordinary product formulas and present numerical comparisons for small numbers of qubits. The ODE algorithm applies to the initial value problem for time-independent first order linear ODEs. We approximate the propagator of the ODE by a truncated Taylor series, and we encode the initial value problem in a large linear system. We solve this linear system with a quantum linear system algorithm (QLSA) whose output we perform a post-selective measurement on. The resulting state encodes the solution to the initial value problem. We prove that our algorithm is asymptotically optimal with respect to several system parameters. The PDE algorithms apply the finite difference method (FDM) to Poisson's equation, the wave equation, and the Klein-Gordon equation. We use high order FDM approximations of the Laplacian operator to develop linear systems for Poisson's equation in cubic volumes under periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we output states encoding solutions to Poisson's equation. We prove that our algorithm is exponentially faster with respect to the spatial dimension than analogous classical algorithms. We also consider how high order Laplacian approximations can be used for simulating the wave and Klein-Gordon equations. We consider under what conditions it suffices to use Hamiltonian simulation for time evolution, and we propose an algorithm for these cases that uses QLSAs for state preparation and post-processing.

•Jan 1, 2019•0 citations

Designing a Nearly Optimal Quantum Algorithm for Linear Differential Equations via Lindbladians

Zhong-Xia Shang, Naixu Guo, Dong An +1 more

Solving linear ordinary differential equations (ODEs) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed nonunitary dynamics into intrinsically unitary quantum circuits. In this Letter, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called nondiagonal density matrix encoding, which leverages the inherent nonunitary dynamics of Lindbladians to encode general linear ODEs into the nondiagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.

arXiv:2410.19628•Physical Review Letters•Aug 26, 2025•33 citations

Structure preserving Quantum Algorithms for Linear Ordinary Differential Equations

Mohit Rohida, Alok Shukla, Prakash Vedula

Many scientific and engineering problems are governed by differential equations whose analytical solutions are unavailable, making numerical discretization indispensable. Classical numerical schemes generally fail to preserve the geometric and symmetry properties of the underlying differential equations, which can adversely affect numerical accuracy. In this work, we combine Lie symmetry-preserving numerical discretization with Quantum Linear Systems Algorithms (QLSAs) to develop a quantum framework for solving first-order linear ordinary differential equations. Using the moving-frame invariantization method, we construct a Lie symmetry-preserving variant of the classical Euler method, referred to as the Lie-Euler scheme. Both the classical Euler and Lie-Euler discretizations are formulated as sparse linear systems and solved using the Harrow-Hassidim-Lloyd algorithm. The Lie-Euler discretization preserves the underlying Lie symmetry and improves the global discretization error from O(h) to O(h 2 ), allowing a prescribed accuracy to be achieved using fewer discretization points and hence smaller linear systems with reduced qubit requirements. Furthermore, for an important class of dissipative problems, we prove that the associated Lie-Euler matrices possess uniformly bounded spectral condition numbers, yielding stronger asymptotic complexity guarantees for modern QLSAs. Numerical examples demonstrate the effectiveness of the proposed framework.

•Jul 6, 2026•0 citations

A Quantum Approach for Implementing Fixed-Point Arithmetic in Solving Ordinary Differential Equations

José E. Cruz Serrallés, Oluwadara Ogunkoya, Dog̃a Murat Kürkçüog̃lu +4 more

Differential equations (DEs) serve as fundamental tools in mathematical modeling across scientific disciplines, yet classical numerical solvers face limitations with large-scale or computationally intensive problems. This study explores a quantum-inspired approach to solving DEs, combining quantum-inspired techniques with classical methods. It focuses on fixed-point arithmetic on quantum circuits, utilizing basic quantum gates to manipulate DE solutions. We expand upon the techniques introduced by Zanger et al. [Quantum, 5, 502 (2021)] by offering a precise computation for a fixed-point signed multiplication scheme, while also presenting a quantum circuit capable of executing the fixed-point division algorithm. We demonstrate the feasibility of our approach through the simulation of a linear Ordinary Differential Equation (ODE), where initial conditions and parameters are encoded into quantum circuits using fixed-point representation. By executing sequences of quantum gates mimicking numerical integration steps, we obtain approximate solutions to the ODE with specified fixed-point precision.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

An Efficient Quantum Algorithm for Linear System Problem in Tensor Format

Zeguan Wu, Sidhant Misra, Tamás Terlaky B +2 more

Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.

arXiv:2403.19829•Mar 28, 2024•2 citations
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.
We present substantially generalized and improved quantum algorithms over prior work for inhomogeneous linear and nonlinear ordinary differential equations (ODE). Specifically, we show how the norm of the matrix exponential characterizes the run time of quantum algorithms for linear ODEs opening the door to an application to a wider class of linear and nonlinear ODEs. In \cite{BCOW17}, a quantum algorithm for a certain class of linear ODEs is given, where the matrix involved needs to be diagonalizable. The quantum algorithm for linear ODEs presented here extends to many classes of non-diagonalizable matrices including singular matrices. The algorithm here is also exponentially faster than the bounds derived in \cite{BCOW17} for certain classes of diagonalizable matrices. Our linear ODE algorithm is then applied to nonlinear differential equations using Carleman linearization (an approach taken recently by us in \cite{Liue2026805118}). The improvement over that result is two-fold. First, we obtain an exponentially better dependence on error. This kind of logarithmic dependence on error has also been achieved by \cite{Xue_2021}, but only for homogeneous nonlinear equations. Second, the present algorithm can handle any sparse matrix (that models dissipation) if it has a negative log-norm (including non-diagonalizable matrices), whereas \cite{Liue2026805118} and \cite{Xue_2021} additionally require normality.
This thesis describes quantum algorithms for Hamiltonian simulation, ordinary differential equations (ODEs), and partial differential equations (PDEs). Product formulas are used to simulate Hamiltonians which can be expressed as a sum of terms which can each be simulated individually. By simulating each of these terms in sequence, the net effect approximately simulates the total Hamiltonian. We find that the error of product formulas can be improved by randomizing over the order in which the Hamiltonian terms are simulated. We prove that this approach is asymptotically better than ordinary product formulas and present numerical comparisons for small numbers of qubits. The ODE algorithm applies to the initial value problem for time-independent first order linear ODEs. We approximate the propagator of the ODE by a truncated Taylor series, and we encode the initial value problem in a large linear system. We solve this linear system with a quantum linear system algorithm (QLSA) whose output we perform a post-selective measurement on. The resulting state encodes the solution to the initial value problem. We prove that our algorithm is asymptotically optimal with respect to several system parameters. The PDE algorithms apply the finite difference method (FDM) to Poisson's equation, the wave equation, and the Klein-Gordon equation. We use high order FDM approximations of the Laplacian operator to develop linear systems for Poisson's equation in cubic volumes under periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we output states encoding solutions to Poisson's equation. We prove that our algorithm is exponentially faster with respect to the spatial dimension than analogous classical algorithms. We also consider how high order Laplacian approximations can be used for simulating the wave and Klein-Gordon equations. We consider under what conditions it suffices to use Hamiltonian simulation for time evolution, and we propose an algorithm for these cases that uses QLSAs for state preparation and post-processing.
Solving linear ordinary differential equations (ODEs) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed nonunitary dynamics into intrinsically unitary quantum circuits. In this Letter, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called nondiagonal density matrix encoding, which leverages the inherent nonunitary dynamics of Lindbladians to encode general linear ODEs into the nondiagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.
Many scientific and engineering problems are governed by differential equations whose analytical solutions are unavailable, making numerical discretization indispensable. Classical numerical schemes generally fail to preserve the geometric and symmetry properties of the underlying differential equations, which can adversely affect numerical accuracy. In this work, we combine Lie symmetry-preserving numerical discretization with Quantum Linear Systems Algorithms (QLSAs) to develop a quantum framework for solving first-order linear ordinary differential equations. Using the moving-frame invariantization method, we construct a Lie symmetry-preserving variant of the classical Euler method, referred to as the Lie-Euler scheme. Both the classical Euler and Lie-Euler discretizations are formulated as sparse linear systems and solved using the Harrow-Hassidim-Lloyd algorithm. The Lie-Euler discretization preserves the underlying Lie symmetry and improves the global discretization error from O(h) to O(h 2 ), allowing a prescribed accuracy to be achieved using fewer discretization points and hence smaller linear systems with reduced qubit requirements. Furthermore, for an important class of dissipative problems, we prove that the associated Lie-Euler matrices possess uniformly bounded spectral condition numbers, yielding stronger asymptotic complexity guarantees for modern QLSAs. Numerical examples demonstrate the effectiveness of the proposed framework.
Differential equations (DEs) serve as fundamental tools in mathematical modeling across scientific disciplines, yet classical numerical solvers face limitations with large-scale or computationally intensive problems. This study explores a quantum-inspired approach to solving DEs, combining quantum-inspired techniques with classical methods. It focuses on fixed-point arithmetic on quantum circuits, utilizing basic quantum gates to manipulate DE solutions. We expand upon the techniques introduced by Zanger et al. [Quantum, 5, 502 (2021)] by offering a precise computation for a fixed-point signed multiplication scheme, while also presenting a quantum circuit capable of executing the fixed-point division algorithm. We demonstrate the feasibility of our approach through the simulation of a linear Ordinary Differential Equation (ODE), where initial conditions and parameters are encoded into quantum circuits using fixed-point representation. By executing sequences of quantum gates mimicking numerical integration steps, we obtain approximate solutions to the ODE with specified fixed-point precision.
Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.