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

An efficient quantum algorithm for simulating polynomial differential equations

Amit Surana, Abeynaya Gnanasekaran, Tuhin Sahai

We present an efficient quantum algorithm to simulate nonlinear differential equations with polynomial vector fields of arbitrary degree on quantum platforms. Models of physical systems that are governed by ordinary differential equations (ODEs) or partial differential equation (PDEs) can be challenging to solve on classical computers due to high dimensionality, stiffness, nonlinearities, and sensitive dependence to initial conditions. For sparse $n$-dimensional linear ODEs, quantum algorithms have been developed which can produce a quantum state proportional to the solution in poly(log(nx)) time using the quantum linear systems algorithm (QLSA). Recently, this framework was extended to systems of nonlinear ODEs with quadratic polynomial vector fields by applying Carleman linearization that enables the embedding of the quadratic system into an approximate linear form. A detailed complexity analysis was conducted which showed significant computational advantage under certain conditions. We present an extension of this algorithm to deal with systems of nonlinear ODEs with $k$-th degree polynomial vector fields for arbitrary (finite) values of $k$. The steps involve: 1) mapping the $k$-th degree polynomial ODE to a higher dimensional quadratic polynomial ODE; 2) applying Carleman linearization to transform the quadratic ODE to an infinite-dimensional system of linear ODEs; 3) truncating and discretizing the linear ODE and solving using the forward Euler method and QLSA. Alternatively, one could apply Carleman linearization directly to the $k$-th degree polynomial ODE, resulting in a system of infinite-dimensional linear ODEs, and then apply step 3. This solution route can be computationally more efficient. We present detailed complexity analysis of the proposed algorithms, prove polynomial scaling of runtime on $k$ and demonstrate the framework on an example.

arXiv:2212.10775•Dec 21, 2022•5 citations

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•93 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•9 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
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 an efficient quantum algorithm to simulate nonlinear differential equations with polynomial vector fields of arbitrary degree on quantum platforms. Models of physical systems that are governed by ordinary differential equations (ODEs) or partial differential equation (PDEs) can be challenging to solve on classical computers due to high dimensionality, stiffness, nonlinearities, and sensitive dependence to initial conditions. For sparse nnn-dimensional linear ODEs, quantum algorithms have been developed which can produce a quantum state proportional to the solution in poly(log(nx)) time using the quantum linear systems algorithm (QLSA). Recently, this framework was extended to systems of nonlinear ODEs with quadratic polynomial vector fields by applying Carleman linearization that enables the embedding of the quadratic system into an approximate linear form. A detailed complexity analysis was conducted which showed significant computational advantage under certain conditions. We present an extension of this algorithm to deal with systems of nonlinear ODEs with kkk-th degree polynomial vector fields for arbitrary (finite) values of kkk. The steps involve: 1) mapping the kkk-th degree polynomial ODE to a higher dimensional quadratic polynomial ODE; 2) applying Carleman linearization to transform the quadratic ODE to an infinite-dimensional system of linear ODEs; 3) truncating and discretizing the linear ODE and solving using the forward Euler method and QLSA. Alternatively, one could apply Carleman linearization directly to the kkk-th degree polynomial ODE, resulting in a system of infinite-dimensional linear ODEs, and then apply step 3. This solution route can be computationally more efficient. We present detailed complexity analysis of the proposed algorithms, prove polynomial scaling of runtime on kkk and demonstrate the framework on an example.
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.