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:2605.16195

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

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

quant-phSubmitted May 15, 2026• Announced May 18, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
56 pages

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•93 citations

Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity

Yin Yang, Yue Yu, Long Zhang

Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity $\mathcal{O}(κ_A\log\frac1\varepsilon)$ without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.

quant-pharXiv:2609.19676•Sep 18, 2026•0 citations

Quantum and classical algorithms for nonlinear unitary dynamics

Noah Brüstle, Nathan Wiebe

Quantum algorithms for Hamiltonian simulation and linear differential equations more generally have provided promising exponential speed-ups over classical computers on a set of problems with high real-world interest. However, extending this to a nonlinear problem has proven challenging, with exponential lower bounds having been demonstrated for the time scaling. We provide a quantum algorithm matching these bounds. Specifically, we find that for a non-linear differential equation of the form d|u⟩dt=A|u⟩+B|u⟩⊗2 for evolution of time T , error tolerance ϵ and c dependent on the strength of the nonlinearity, the number of queries to the differential operators that approaches the scaling of the quantum lower bound of eo(T‖B‖) queries in the limit of strong non-linearity. Finally, we introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case, as well as a randomized classical algorithm based on path integration that acts as a true analogue to the quantum algorithm in that it scales comparably to the quantum algorithm in cases where sign problems are absent.

arXiv:2407.07685•Quantum•May 13, 2025•2 citations

Quantum simulation of non-Markovian dynamical systems

Abtin Ameri, Arkopal Dutt, Hari Krovi

Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms. We develop an algorithm for general kernels assuming that $\textsf{M} < 1$, where $\textsf{M}$ characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when $\textsf{M} \geq 1$, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when $\textsf M \geq 1$ by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.

quant-pharXiv:2608.13533•Aug 14, 2026•0 citations

Efficient quantum algorithm for dissipative nonlinear differential equations

Jin-Peng Liu, Herman Øie Kolden, Hari Krovi +3 more

Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming [Formula: see text], where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity [Formula: see text], where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for [Formula: see text] Finally, we discuss potential applications, showing that the [Formula: see text] condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.

arXiv:2011.03185•Proceedings of the National Academy of Sciences•Aug 26, 2021•238 citations

Efficient quantum algorithm for solving differential equations with Fourier nonlinearity via Koopman linearization

Judd Katz, Gopikrishnan Muraleedharan, Abhijeet Alase

Quantum algorithms offer an exponential advantage with respect to the number of dependent variables for solving certain nonlinear ordinary differential equations (ODEs). These algorithms typically begin by transforming the original nonlinear ODE into a higher-dimensional linear ODE using a linearization technique, most commonly Carleman linearization. Existing works restrict their analysis to ODEs where the nonlinearities are polynomial functions of the dependent variables, significantly limiting their applicability. In this work we construct an efficient quantum algorithm for solving ODEs with `Fourier' nonlinear terms expressible as $d{\bf u}/dt = G_0 + G_1 e^{i{\bf u}}$, where ${\bf u}$ denotes a vector of $n$ complex variables evolving with $t$, $G_0$ is an $n$-dimensional complex vector, $G_1$ is an $n \times n$ complex matrix and $e^{i{\bf u}}$ denotes the vector with entries $\{e^{iu_j}\}$. To tackle the Fourier nonlinear term, which is not expressible as a finite sum of polynomials of ${\bf u}$, our algorithm employs a generalization of the Carleman linearization technique known as Koopman linearization. We also make other methodological advances towards relaxing the stringent dissipativity condition required for efficient solution extraction and towards integrated readout of classical quantities from the solution state. Our results open avenues to the development of efficient quantum algorithms for a significantly wider class of high-dimensional nonlinear ODEs, thereby broadening the scope of their applications.

quant-pharXiv:2512.06488•Dec 9, 2025•0 citations
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.
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.
Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity O(κAlog⁡1ε)\mathcal{O}(κ_A\log\frac1\varepsilon)O(κA​logε1​) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
Quantum algorithms for Hamiltonian simulation and linear differential equations more generally have provided promising exponential speed-ups over classical computers on a set of problems with high real-world interest. However, extending this to a nonlinear problem has proven challenging, with exponential lower bounds having been demonstrated for the time scaling. We provide a quantum algorithm matching these bounds. Specifically, we find that for a non-linear differential equation of the form d|u⟩dt=A|u⟩+B|u⟩⊗2 for evolution of time T , error tolerance ϵ and c dependent on the strength of the nonlinearity, the number of queries to the differential operators that approaches the scaling of the quantum lower bound of eo(T‖B‖) queries in the limit of strong non-linearity. Finally, we introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case, as well as a randomized classical algorithm based on path integration that acts as a true analogue to the quantum algorithm in that it scales comparably to the quantum algorithm in cases where sign problems are absent.
Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms. We develop an algorithm for general kernels assuming that M<1\textsf{M} < 1M<1, where M\textsf{M}M characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when M≥1\textsf{M} \geq 1M≥1, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when M≥1\textsf M \geq 1M≥1 by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.
Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming [Formula: see text], where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity [Formula: see text], where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for [Formula: see text] Finally, we discuss potential applications, showing that the [Formula: see text] condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.
Quantum algorithms offer an exponential advantage with respect to the number of dependent variables for solving certain nonlinear ordinary differential equations (ODEs). These algorithms typically begin by transforming the original nonlinear ODE into a higher-dimensional linear ODE using a linearization technique, most commonly Carleman linearization. Existing works restrict their analysis to ODEs where the nonlinearities are polynomial functions of the dependent variables, significantly limiting their applicability. In this work we construct an efficient quantum algorithm for solving ODEs with `Fourier' nonlinear terms expressible as du/dt=G0+G1eiud{\bf u}/dt = G_0 + G_1 e^{i{\bf u}}du/dt=G0​+G1​eiu, where u{\bf u}u denotes a vector of nnn complex variables evolving with ttt, G0G_0G0​ is an nnn-dimensional complex vector, G1G_1G1​ is an n×nn \times nn×n complex matrix and eiue^{i{\bf u}}eiu denotes the vector with entries {eiuj}\{e^{iu_j}\}{eiuj​}. To tackle the Fourier nonlinear term, which is not expressible as a finite sum of polynomials of u{\bf u}u, our algorithm employs a generalization of the Carleman linearization technique known as Koopman linearization. We also make other methodological advances towards relaxing the stringent dissipativity condition required for efficient solution extraction and towards integrated readout of classical quantities from the solution state. Our results open avenues to the development of efficient quantum algorithms for a significantly wider class of high-dimensional nonlinear ODEs, thereby broadening the scope of their applications.