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:1010.2745 · Journal of Physics A Mathematical and Theoretical

High-order quantum algorithm for solving linear differential equations

Dominic William Berry

Published Feb 19, 2014• 277 citations
arXivHTMLPDF

Abstract

Linear differential equations are ubiquitous in science and engineering. Quantum computers can simulate quantum systems, which are described by a restricted type of linear differential equations. Here we extend quantum simulation algorithms to general inhomogeneous sparse linear differential equations, which describe many classical physical systems. We examine the use of high-order methods to improve the efficiency. These provide scaling close to $Δt^2$ in the evolution time $Δt$. As with other algorithms of this type, the solution is encoded in amplitudes of the quantum state, and it is possible to extract global features of the solution.

DOI
10.1088/1751-8113/47/10/105301

Related papers

Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

Sophia Simon, Dominic W. Berry, Rolando D. Somma

We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity $\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)$, where the constant $ν$ depends on the problem parameters, $\mathcal{L}$ involves a time integral of upper bounds on the norms of evolution operators, and $ε$ is the error. In particular, $ν\mathcal{L}$ is linear in $t$ for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of $Ω(ν\mathcal{L} t/ε)$ for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.

quant-pharXiv:2605.16195•May 18, 2026•0 citations

Quantum algorithm for time-dependent differential equations using Dyson series

Dominic William Berry, Pedro C. S. Costa

Time-dependent linear differential equations are a common type of problem that needs to be solved in classical physics. Here we provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. As usual, there is an exponential improvement over classical approaches in the scaling of the complexity with the dimension, with the caveat that the solution is encoded in the amplitudes of a quantum state. Our method is to encode the Dyson series in a system of linear equations, then solve via the optimal quantum linear equation solver. Our method also provides a simplified approach in the case of time-independent differential equations.

arXiv:2212.03544•Quantum•Jun 13, 2024•31 citations

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

Dekuan Dong, Yingzhou Li, Jungong Xue

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:2504.06948•Quantum•Jun 17, 2025•2 citations

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

High-precision quantum algorithms for partial differential equations

Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

arXiv:2002.07868•Quantum•Nov 10, 2021•154 citations

Efficient Quantum Algorithm for Solving Linear Distributed Delay Differential Equations

Wataru Setoyama, Keisuke Fujii

Non-Markovian dynamics is ubiquitous in both quantum and classical systems, but the numerical computation of the time-delay dynamics is demanding. In this work, we propose an efficient quantum algorithm for solving linear distributed delay differential equations and identify the condition under which it applies. Using the linear chain trick, the distributed delay differential equations can be embedded into ordinary differential equations augmented with auxiliary variables, when the kernel function is characterized by a phase-type distribution. Employing the Schrödingerization method, the resulting equations can be embedded into the Schrödinger equation and efficiently solved by Hamiltonian simulation. Although this embedding requires the augmented differential equation to be semi-stable, we show that it is satisfied if and only if the original distributed-delay differential equations are semi-stable. The query complexity to obtain the normalized solution state of the $N$-dimensional delay system $|\mathbf{x}(t)\rangle\equiv\mathbf{x(t)}/\vert\vert\mathbf{x}(t)\vert\vert$ is $\mathcal{O}((st\vert\vert H\vert\vert_{\max}+\logε^{-1}/\log\logε^{-1})\vert\vert\mathbf{x}(0)\vert\vert/\vert\vert\mathbf{x}(t)\vert\vert)$ with $ε$, $g$, $H$, and $s$ being the allowable error, the dimension of the auxiliary variables associated with each kernel function, the Hamiltonian operator, and its sparsity, respectively. The gate complexity is given by this quantity multiplied by $\mathcal{O}(m+\log(N(1+gs)))$, where $m$ is the number of precision bits. To demonstrate the efficacy of our method, we present its applications to the generalized master equation and to the Redfield equation of the dephasing model.

quant-pharXiv:2603.17941•Mar 19, 2026•0 citations
Linear differential equations are ubiquitous in science and engineering. Quantum computers can simulate quantum systems, which are described by a restricted type of linear differential equations. Here we extend quantum simulation algorithms to general inhomogeneous sparse linear differential equations, which describe many classical physical systems. We examine the use of high-order methods to improve the efficiency. These provide scaling close to Δt2Δt^2Δt2 in the evolution time ΔtΔtΔt. As with other algorithms of this type, the solution is encoded in amplitudes of the quantum state, and it is possible to extract global features of the solution.
We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity O~(νLt/ε)\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)O(νLt/ε), where the constant ννν depends on the problem parameters, L\mathcal{L}L involves a time integral of upper bounds on the norms of evolution operators, and εεε is the error. In particular, νLν\mathcal{L}νL is linear in ttt for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of Ω(νLt/ε)Ω(ν\mathcal{L} t/ε)Ω(νLt/ε) for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.
Time-dependent linear differential equations are a common type of problem that needs to be solved in classical physics. Here we provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. As usual, there is an exponential improvement over classical approaches in the scaling of the complexity with the dimension, with the caveat that the solution is encoded in the amplitudes of a quantum state. Our method is to encode the Dyson series in a system of linear equations, then solve via the optimal quantum linear equation solver. Our method also provides a simplified approach in the case of time-independent differential equations.
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.
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
Non-Markovian dynamics is ubiquitous in both quantum and classical systems, but the numerical computation of the time-delay dynamics is demanding. In this work, we propose an efficient quantum algorithm for solving linear distributed delay differential equations and identify the condition under which it applies. Using the linear chain trick, the distributed delay differential equations can be embedded into ordinary differential equations augmented with auxiliary variables, when the kernel function is characterized by a phase-type distribution. Employing the Schrödingerization method, the resulting equations can be embedded into the Schrödinger equation and efficiently solved by Hamiltonian simulation. Although this embedding requires the augmented differential equation to be semi-stable, we show that it is satisfied if and only if the original distributed-delay differential equations are semi-stable. The query complexity to obtain the normalized solution state of the NNN-dimensional delay system ∣x(t)⟩≡x(t)/∣∣x(t)∣∣|\mathbf{x}(t)\rangle\equiv\mathbf{x(t)}/\vert\vert\mathbf{x}(t)\vert\vert∣x(t)⟩≡x(t)/∣∣x(t)∣∣ is O((st∣∣H∣∣max⁡+log⁡ε−1/log⁡log⁡ε−1)∣∣x(0)∣∣/∣∣x(t)∣∣)\mathcal{O}((st\vert\vert H\vert\vert_{\max}+\logε^{-1}/\log\logε^{-1})\vert\vert\mathbf{x}(0)\vert\vert/\vert\vert\mathbf{x}(t)\vert\vert)O((st∣∣H∣∣max​+logε−1/loglogε−1)∣∣x(0)∣∣/∣∣x(t)∣∣) with εεε, ggg, HHH, and sss being the allowable error, the dimension of the auxiliary variables associated with each kernel function, the Hamiltonian operator, and its sparsity, respectively. The gate complexity is given by this quantity multiplied by O(m+log⁡(N(1+gs)))\mathcal{O}(m+\log(N(1+gs)))O(m+log(N(1+gs))), where mmm is the number of precision bits. To demonstrate the efficacy of our method, we present its applications to the generalized master equation and to the Redfield equation of the dephasing model.