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

A quantum algorithm to solve nonlinear differential equations

Sarah K. Leyton, Tobias J. Osborne

Published Dec 23, 2008• 178 citations
arXivHTMLPDF

Abstract

In this paper we describe a quantum algorithm to solve sparse systems of nonlinear differential equations whose nonlinear terms are polynomials. The algorithm is nondeterministic and its expected resource requirements are polylogarithmic in the number of variables and exponential in the integration time. The best classical algorithm runs in a time scaling linearly with the number of variables, so this provides an exponential improvement. The algorithm is built on two subroutines: (i) a quantum algorithm to implement a nonlinear transformation of the probability amplitudes of an unknown quantum state; and (ii) a quantum implementation of Euler's method.

DOI
10.48550/arxiv.0812.4423

Related papers

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

A Polynomial Time Quantum Algorithm for Exponentially Large Scale Nonlinear Differential Equations via Hamiltonian Simulation

Yu Tanaka, Keisuke Fujii

Quantum computers have the potential to efficiently solve a system of nonlinear ordinary differential equations (ODEs), which play a crucial role in various industries and scientific fields. However, it remains unclear which system of nonlinear ODEs, and under what assumptions, can achieve exponential speedup using quantum computers. In this work, we introduce a class of systems of nonlinear ODEs that can be efficiently solved on quantum computers, where the efficiency is defined as solving the system with computational complexity of $O(T {\rm log}(N) {\rm polylog}(1/ε))$, where $T$ is the evolution time, $ε$ is the allowed error, and $N$ is the number of variables in the system. Specifically, we employ the Koopman-von Neumann linearization to map the system of nonlinear ODEs to Hamiltonian dynamics and find conditions where the norm of the mapped Hamiltonian is preserved and the Hamiltonian is sparse. This allows us to use the optimal Hamiltonian simulation technique for solving the nonlinear ODEs with $O({\rm log}(N))$ overhead. Furthermore, we show that the nonlinear ODEs include a wide range of systems of nonlinear ODEs, such as the nonlinear harmonic oscillators and the short-range Kuramoto model. This is the first concrete example of solving systems of nonlinear ODEs with exponential quantum speedup by the Koopman-von Neumann linearization, although it is noted that this assumes efficient preparation of the initial state and computation of the output. These findings contribute significantly to the application of quantum computers in solving nonlinear problems.

arXiv:2305.00653•May 1, 2023•15 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•4 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•310 citations

Quantum algorithm for solving nonlinear algebraic equations

Nhat A. Nghiem, Tzu-Chieh Wei

Nonlinear equations are generally challenging to solve. As analytical solutions typically do not exist, numerical methods have been developed to find their solutions. In this article, building upon the classical Newton method and the recent quantum singular value transformation framework, we give a quantum algorithm for solving a system of nonlinear algebraic equations, in which each equation is a homogeneous polynomial of an even degree. A detailed analysis is then carried out to reveal that our method achieves polylogarithmic time relative to the number of variables. Furthermore, the number of required qubits is logarithmic in the number of variables. In particular, we also show that our method can be generalized to deal with polynomials of various types. Some potential applications stem from various contexts, such as the Gross-Pitaevski equation, the Lotka-Volterra equations, and the intersection of algebraic varieties. Our work thus marks a significant step forward toward quantum advantage in nonlinear science, highlighting a promising avenue for future exploration.

arXiv:2404.03810•Physical Review Applied•Sep 26, 2025•3 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•8 citations
In this paper we describe a quantum algorithm to solve sparse systems of nonlinear differential equations whose nonlinear terms are polynomials. The algorithm is nondeterministic and its expected resource requirements are polylogarithmic in the number of variables and exponential in the integration time. The best classical algorithm runs in a time scaling linearly with the number of variables, so this provides an exponential improvement. The algorithm is built on two subroutines: (i) a quantum algorithm to implement a nonlinear transformation of the probability amplitudes of an unknown quantum state; and (ii) a quantum implementation of Euler's method.
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.
Quantum computers have the potential to efficiently solve a system of nonlinear ordinary differential equations (ODEs), which play a crucial role in various industries and scientific fields. However, it remains unclear which system of nonlinear ODEs, and under what assumptions, can achieve exponential speedup using quantum computers. In this work, we introduce a class of systems of nonlinear ODEs that can be efficiently solved on quantum computers, where the efficiency is defined as solving the system with computational complexity of O(Tlog(N)polylog(1/ε))O(T {\rm log}(N) {\rm polylog}(1/ε))O(Tlog(N)polylog(1/ε)), where TTT is the evolution time, εεε is the allowed error, and NNN is the number of variables in the system. Specifically, we employ the Koopman-von Neumann linearization to map the system of nonlinear ODEs to Hamiltonian dynamics and find conditions where the norm of the mapped Hamiltonian is preserved and the Hamiltonian is sparse. This allows us to use the optimal Hamiltonian simulation technique for solving the nonlinear ODEs with O(log(N))O({\rm log}(N))O(log(N)) overhead. Furthermore, we show that the nonlinear ODEs include a wide range of systems of nonlinear ODEs, such as the nonlinear harmonic oscillators and the short-range Kuramoto model. This is the first concrete example of solving systems of nonlinear ODEs with exponential quantum speedup by the Koopman-von Neumann linearization, although it is noted that this assumes efficient preparation of the initial state and computation of the output. These findings contribute significantly to the application of quantum computers in solving nonlinear problems.
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.
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.
Nonlinear equations are generally challenging to solve. As analytical solutions typically do not exist, numerical methods have been developed to find their solutions. In this article, building upon the classical Newton method and the recent quantum singular value transformation framework, we give a quantum algorithm for solving a system of nonlinear algebraic equations, in which each equation is a homogeneous polynomial of an even degree. A detailed analysis is then carried out to reveal that our method achieves polylogarithmic time relative to the number of variables. Furthermore, the number of required qubits is logarithmic in the number of variables. In particular, we also show that our method can be generalized to deal with polynomials of various types. Some potential applications stem from various contexts, such as the Gross-Pitaevski equation, the Lotka-Volterra equations, and the intersection of algebraic varieties. Our work thus marks a significant step forward toward quantum advantage in nonlinear science, highlighting a promising avenue for future exploration.
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.