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:2509.07155 · Quantum

Quantum algorithms for general nonlinear dynamics based on the Carleman embedding

David Jennings, Kamil Korzekwa, Matteo Lostaglio, Andrew T Sornborger, Yigit Subasi, Guoming Wang

quant-phcs.DSmath.NASubmitted Sep 8, 2025• Announced Sep 10, 2025• 1 citation• Revised Oct 1, 2026 (v2)
v1 · Sep 8, 2025v2 · Oct 1, 2026v3 · Oct 29, 2026
arXivHTMLPDF

Abstract

Important nonlinear dynamics, such as those found in plasma and fluid systems, are typically hard to simulate on classical computers. Thus, if fault-tolerant quantum computers could efficiently solve such nonlinear problems, it would be a transformative change for many industries. In a recent breakthrough [Liu et al., PNAS 2021], the first efficient quantum algorithm for solving nonlinear differential equations was constructed, based on a single condition $R<1$, where $R$ characterizes the ratio of nonlinearity to dissipation. This result, however, is limited to the class of purely dissipative systems with negative log-norm, which excludes application to many important problems. In this work, we correct technical issues with this and other prior analysis, and substantially extend the scope of nonlinear dynamical systems that can be efficiently simulated on a quantum computer in a number of ways. Firstly, we extend the existing results from purely dissipative systems to a much broader class of stable systems, and show that every quadratic Lyapunov function for the linearized system corresponds to an independent $R$-number criterion for the convergence of the Carlemen scheme. Secondly, we extend our stable system results to physically relevant settings where conserved polynomial quantities exist. Finally, we provide extensive results for the class of non-resonant systems. With this, we are able to show that efficient quantum algorithms exist for a much wider class of nonlinear systems than previously known, and prove the BQP-completeness of nonlinear oscillator problems of exponential size. In our analysis, we also obtain several results related to the Poincaré-Dulac theorem and diagonalization of the Carleman matrix, which could be of independent interest.

Journal reference
Quantum 10, 2233 (2026)
DOI
10.22331/q-2026-10-08-2233
Comments
73+78 pages, 5 figures. Added clarifications on the binary-forest formalism and oscillating systems, as well as a showcase numerical example; fixed typos

Related papers

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

Quantum Algorithms for Nonlinear Differential Equations via Pivot-Shifted Carleman Linearization

Ke Wang, Zikang Jia, Shravan Veerapaneni +1 more

We develop a pivot-shifted Carleman linearization framework for quantum algorithms solving quadratic nonlinear ordinary differential equations. By shifting the dynamics by a pivot state prior to Carleman lifting, and combining this with a Lyapunov transform and rescaling, we enlarge the class of nonlinear systems that can be efficiently simulated on quantum computers. For systems that exhibit stability in the shifted coordinates, we establish long time convergence of the truncated Carleman embedding. We prove that the truncation order scales only logarithmically with the simulation time and target precision, and we derive end-to-end quantum query complexity bounds for preparing a state proportional to the final solution. By introducing a modified nonlinearity condition, this framework entirely removes the conventional lower bound requirement on the initial condition. For more general systems that remain unstable after shifting, we provide short time convergence guarantees that are similarly free from the initial condition constraints. Numerical experiments on the logistic and the Lotka-Volterra equations demonstrate that an appropriate pivot choice improves stability and accuracy, and yields exponential error decay with truncation order. These results show that pivot shifting provides a practical and theoretically justified route for extending Carleman-based quantum algorithms to a broader class of nonlinear dynamical systems.

quant-pharXiv:2605.20071•May 20, 2026•1 citation

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

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 stochastic nonlinear differential equations

Sergey Bravyi, Adam Byrne, Mykhaylo Zayats +1 more

Stochastic nonlinear dynamics underlie many models in engineering and computational physics, yet accurate high-dimensional simulation remains challenging. We present a quantum algorithm for a broad class of $N$-dimensional stochastic differential equations with dissipation and quadratic drift. The algorithm applies to strongly nonlinear systems with all-to-all interactions, thereby extending the scope of previously known quantum algorithms that were limited to weak nonlinearity and sparse systems. For norm-preserving drifts, a condition satisfied by key fluid dynamics discretizations, our method approximates expectation values of low-order correlation functions with rigorous error bounds at a cost polynomial in $\log{(N)}$ and linear in the evolution time. Our main technical advance is a subroutine for simulating an auxiliary system of $N$ interacting quantum harmonic oscillators with cost polylogarithmic in $N$. Finally, we formulate turbulence models, including Navier-Stokes and damped Euler equations, within this framework, opening a route to quantum simulation of strongly nonlinear SDEs governing turbulence and nonlinear wave dynamics.

quant-pharXiv:2606.08349•Jun 9, 2026•0 citations

Fast-forwarding quantum algorithms for weakly nonlinear dissipative differential equations and beyond

Yixiang Li, Dong An

We study a fast-forwarded quantum algorithm for solving weakly nonlinear dissipative ordinary differential equations. Our approach is a combination of the Carleman embedding technique and the linear combination of Hamiltonian simulation algorithm for linearized systems with fast-forwarded scaling. The complexity of our algorithm does not explicitly depend on the evolution time $T$, thus greatly improving the previous state-of-the-art $\widetilde{\mathcal{O}}(\sqrt{T})$ to $\mathcal{O}(1)$, and any remaining time dependence enters through the output norm and forcing parameters. We rigorously analyze the performance of this approach by convergence guarantees of the Carleman embedding for time-dependent coefficient matrices and detailed complexity estimates, and improve the realization of the Carleman-embedding-based algorithms by simplifying the post-selection step. In addition, we perform a numerical study on differential equations beyond the weakly nonlinear case, and identify possibility of achieving fast-forwarding scaling for systems with stronger nonlinearity or linear non-resonant effect.

quant-pharXiv:2608.25822•Aug 27, 2026•0 citations
Important nonlinear dynamics, such as those found in plasma and fluid systems, are typically hard to simulate on classical computers. Thus, if fault-tolerant quantum computers could efficiently solve such nonlinear problems, it would be a transformative change for many industries. In a recent breakthrough [Liu et al., PNAS 2021], the first efficient quantum algorithm for solving nonlinear differential equations was constructed, based on a single condition R<1R<1R<1, where RRR characterizes the ratio of nonlinearity to dissipation. This result, however, is limited to the class of purely dissipative systems with negative log-norm, which excludes application to many important problems. In this work, we correct technical issues with this and other prior analysis, and substantially extend the scope of nonlinear dynamical systems that can be efficiently simulated on a quantum computer in a number of ways. Firstly, we extend the existing results from purely dissipative systems to a much broader class of stable systems, and show that every quadratic Lyapunov function for the linearized system corresponds to an independent RRR-number criterion for the convergence of the Carlemen scheme. Secondly, we extend our stable system results to physically relevant settings where conserved polynomial quantities exist. Finally, we provide extensive results for the class of non-resonant systems. With this, we are able to show that efficient quantum algorithms exist for a much wider class of nonlinear systems than previously known, and prove the BQP-completeness of nonlinear oscillator problems of exponential size. In our analysis, we also obtain several results related to the Poincaré-Dulac theorem and diagonalization of the Carleman matrix, which could be of independent interest.
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.
We develop a pivot-shifted Carleman linearization framework for quantum algorithms solving quadratic nonlinear ordinary differential equations. By shifting the dynamics by a pivot state prior to Carleman lifting, and combining this with a Lyapunov transform and rescaling, we enlarge the class of nonlinear systems that can be efficiently simulated on quantum computers. For systems that exhibit stability in the shifted coordinates, we establish long time convergence of the truncated Carleman embedding. We prove that the truncation order scales only logarithmically with the simulation time and target precision, and we derive end-to-end quantum query complexity bounds for preparing a state proportional to the final solution. By introducing a modified nonlinearity condition, this framework entirely removes the conventional lower bound requirement on the initial condition. For more general systems that remain unstable after shifting, we provide short time convergence guarantees that are similarly free from the initial condition constraints. Numerical experiments on the logistic and the Lotka-Volterra equations demonstrate that an appropriate pivot choice improves stability and accuracy, and yields exponential error decay with truncation order. These results show that pivot shifting provides a practical and theoretically justified route for extending Carleman-based quantum algorithms to a broader class of nonlinear dynamical systems.
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.
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.
Stochastic nonlinear dynamics underlie many models in engineering and computational physics, yet accurate high-dimensional simulation remains challenging. We present a quantum algorithm for a broad class of NNN-dimensional stochastic differential equations with dissipation and quadratic drift. The algorithm applies to strongly nonlinear systems with all-to-all interactions, thereby extending the scope of previously known quantum algorithms that were limited to weak nonlinearity and sparse systems. For norm-preserving drifts, a condition satisfied by key fluid dynamics discretizations, our method approximates expectation values of low-order correlation functions with rigorous error bounds at a cost polynomial in log⁡(N)\log{(N)}log(N) and linear in the evolution time. Our main technical advance is a subroutine for simulating an auxiliary system of NNN interacting quantum harmonic oscillators with cost polylogarithmic in NNN. Finally, we formulate turbulence models, including Navier-Stokes and damped Euler equations, within this framework, opening a route to quantum simulation of strongly nonlinear SDEs governing turbulence and nonlinear wave dynamics.
We study a fast-forwarded quantum algorithm for solving weakly nonlinear dissipative ordinary differential equations. Our approach is a combination of the Carleman embedding technique and the linear combination of Hamiltonian simulation algorithm for linearized systems with fast-forwarded scaling. The complexity of our algorithm does not explicitly depend on the evolution time TTT, thus greatly improving the previous state-of-the-art O~(T)\widetilde{\mathcal{O}}(\sqrt{T})O(T​) to O(1)\mathcal{O}(1)O(1), and any remaining time dependence enters through the output norm and forcing parameters. We rigorously analyze the performance of this approach by convergence guarantees of the Carleman embedding for time-dependent coefficient matrices and detailed complexity estimates, and improve the realization of the Carleman-embedding-based algorithms by simplifying the post-selection step. In addition, we perform a numerical study on differential equations beyond the weakly nonlinear case, and identify possibility of achieving fast-forwarding scaling for systems with stronger nonlinearity or linear non-resonant effect.