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

Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation

Dong Un An, Di Fang, Stephen P. Jordan, Jin-Peng Liu, Guang Hao Low, Jiasu Wang

Published May 2, 2022• 10 citations
arXivHTMLPDF

Abstract

Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition $R < 1$, where $R$ measures the ratio of nonlinearity to dissipation using the $\ell_2$ norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition $R_D < 1$, where $R_D$ measures the ratio of nonlinearity to dissipation using the $\ell_{\infty}$ norm. Since $R_D$ is independent of the number of spatial grid points $n$ while $R$ increases with $n$, the criterion $R_D<1$ is significantly milder than $R<1$ for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.

DOI
10.48550/arxiv.2205.01141

Related papers

Quantum algorithms for general nonlinear dynamics based on the Carleman embedding

David Jennings, Kamil Korzekwa, Matteo Lostaglio +3 more

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 Carleman 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.

quant-pharXiv:2509.07155•Quantum•Sep 10, 2025•1 citation

Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling

Pedro C. S. Costa, Philipp Schleich, Mauro E. S. Morales +1 more

The solution of large systems of nonlinear differential equations is essential for many applications in science and engineering. We present three improvements to existing quantum algorithms based on the Carleman linearisation technique. First, we use a high-precision method for solving the linearised system that yields logarithmic dependence on the error and near-linear dependence on time. Second, we introduce a rescaling strategy that significantly reduces the cost, which would otherwise scale exponentially with the Carleman order, thus limiting quantum speedups for PDEs. Third, we derive tighter error bounds for Carleman linearisation. We apply our results to a class of discretised reaction-diffusion equations using higher-order finite differences for spatial resolution. We also show that enforcing a stability criterion independent of the discretisation can conflict with rescaling due to the mismatch between the max-norm and the 2-norm. Nonetheless, efficient quantum solutions remain possible when the number of discretisation points is constrained, as enabled by higher-order schemes.

arXiv:2312.09518•npj Quantum Information•Aug 18, 2025•16 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

Quantum algorithms for linear and non-linear fractional reaction-diffusion equations

Dong An, Konstantina Trivisa

High-dimensional fractional reaction-diffusion equations have numerous applications in the fields of biology, chemistry, and physics, and exhibit a range of rich phenomena. While classical algorithms have an exponential complexity in the spatial dimension, a quantum computer can produce a quantum state that encodes the solution with only polynomial complexity, provided that suitable input access is available. In this work, we investigate efficient quantum algorithms for linear and nonlinear fractional reaction-diffusion equations with periodic boundary conditions. For linear equations, we analyze and compare the complexity of various methods, including the second-order Trotter formula, time-marching method, and truncated Dyson series method. We also present a novel algorithm that combines the linear combination of Hamiltonian simulation technique with the interaction picture formalism, resulting in optimal scaling in the spatial dimension. For nonlinear equations, we employ the Carleman linearization method and propose a block-encoding version that is appropriate for the dense matrices that arise from the spatial discretization of fractional reaction-diffusion equations.

arXiv:2310.18900•Quantum•Jan 19, 2026•3 citations

Two Quantum Algorithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approximation Method

Manish Kumar

We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshev polynomial approximation. This method is employed to numerically solve the ordinary differential equation emerging from the linearization of the associated nonlinear differential equation. In the first algorithm, we use the matrix exponentiation method (Patel et al., 2018), while in the second algorithm, we repurpose the quantum spectral method (Childs et al., 2020). Our main technical contribution is to derive the sufficient conditions for the diagonalization of the Carleman embedding matrix, which is indispensable for designing both quantum algorithms. We supplement this with an efficient iterative algorithm to diagonalize the Carleman matrix. Our first algorithm has gate complexity of O(d$\cdot$log(d)+T$\cdot$polylog(T/$\varepsilon$)). Here $d$ is the size of the Carleman matrix, $T$ is the simulation time, and $\varepsilon$ is the approximation error. The second algorithm is polynomial in $log(d)$, $T$, and $log(1/\varepsilon)$ - the gate complexity scales as O(polylog(d)$\cdot$T$\cdot$polylog(T/$\varepsilon$)). In terms of $T$ and $\varepsilon$, this is comparable to the speedup gained by the current best known quantum algorithm for this problem, the truncated Taylor series method (Costa et.al., 2025). Our approach has two shortcomings. First, we have not provided an upper bound, in terms of d, on the condition number of the Carleman matrix. Second, the success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution. However, we provide strategies to mitigate these shortcomings in most practical cases.

arXiv:2510.19855•Oct 21, 2025•0 citations
Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition R<1R < 1R<1, where RRR measures the ratio of nonlinearity to dissipation using the ℓ2\ell_2ℓ2​ norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition RD<1R_D < 1RD​<1, where RDR_DRD​ measures the ratio of nonlinearity to dissipation using the ℓ∞\ell_{\infty}ℓ∞​ norm. Since RDR_DRD​ is independent of the number of spatial grid points nnn while RRR increases with nnn, the criterion RD<1R_D<1RD​<1 is significantly milder than R<1R<1R<1 for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.
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 Carleman 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.
The solution of large systems of nonlinear differential equations is essential for many applications in science and engineering. We present three improvements to existing quantum algorithms based on the Carleman linearisation technique. First, we use a high-precision method for solving the linearised system that yields logarithmic dependence on the error and near-linear dependence on time. Second, we introduce a rescaling strategy that significantly reduces the cost, which would otherwise scale exponentially with the Carleman order, thus limiting quantum speedups for PDEs. Third, we derive tighter error bounds for Carleman linearisation. We apply our results to a class of discretised reaction-diffusion equations using higher-order finite differences for spatial resolution. We also show that enforcing a stability criterion independent of the discretisation can conflict with rescaling due to the mismatch between the max-norm and the 2-norm. Nonetheless, efficient quantum solutions remain possible when the number of discretisation points is constrained, as enabled by higher-order schemes.
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.
High-dimensional fractional reaction-diffusion equations have numerous applications in the fields of biology, chemistry, and physics, and exhibit a range of rich phenomena. While classical algorithms have an exponential complexity in the spatial dimension, a quantum computer can produce a quantum state that encodes the solution with only polynomial complexity, provided that suitable input access is available. In this work, we investigate efficient quantum algorithms for linear and nonlinear fractional reaction-diffusion equations with periodic boundary conditions. For linear equations, we analyze and compare the complexity of various methods, including the second-order Trotter formula, time-marching method, and truncated Dyson series method. We also present a novel algorithm that combines the linear combination of Hamiltonian simulation technique with the interaction picture formalism, resulting in optimal scaling in the spatial dimension. For nonlinear equations, we employ the Carleman linearization method and propose a block-encoding version that is appropriate for the dense matrices that arise from the spatial discretization of fractional reaction-diffusion equations.
We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshev polynomial approximation. This method is employed to numerically solve the ordinary differential equation emerging from the linearization of the associated nonlinear differential equation. In the first algorithm, we use the matrix exponentiation method (Patel et al., 2018), while in the second algorithm, we repurpose the quantum spectral method (Childs et al., 2020). Our main technical contribution is to derive the sufficient conditions for the diagonalization of the Carleman embedding matrix, which is indispensable for designing both quantum algorithms. We supplement this with an efficient iterative algorithm to diagonalize the Carleman matrix. Our first algorithm has gate complexity of O(d⋅\cdot⋅log(d)+T⋅\cdot⋅polylog(T/ε\varepsilonε)). Here ddd is the size of the Carleman matrix, TTT is the simulation time, and ε\varepsilonε is the approximation error. The second algorithm is polynomial in log(d)log(d)log(d), TTT, and log(1/ε)log(1/\varepsilon)log(1/ε) - the gate complexity scales as O(polylog(d)⋅\cdot⋅T⋅\cdot⋅polylog(T/ε\varepsilonε)). In terms of TTT and ε\varepsilonε, this is comparable to the speedup gained by the current best known quantum algorithm for this problem, the truncated Taylor series method (Costa et.al., 2025). Our approach has two shortcomings. First, we have not provided an upper bound, in terms of d, on the condition number of the Carleman matrix. Second, the success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution. However, we provide strategies to mitigate these shortcomings in most practical cases.