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

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

Manish Kumar

Published Oct 21, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2510.19855

Related papers

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

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

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

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

Quantum algorithm for high-dimensional nonlinear stochastic differential equations based on Carleman linearization

Koichi Miyamoto

Addressing nonlinear numerical problems in quantum computing remains challenging, but several approaches, including Carleman linearization (CL), have been proposed to construct quantum algorithms for such problems. In this work, we develop a CL-based method for a high-dimensional nonlinear stochastic differential equation (SDE) $\mathrm{d} \mathbf{X}_t = \left(A(t) \mathbf{X}_t + F(t) \mathbf{X}_t^{\otimes s}\right) \mathrm{d} t + B(t) \mathrm{d} \mathbf{W}_t$ for an $\mathbb{R}^N$-valued random process $\mathbf{X}_t$, aiming at quantum speed-up with respect to the dimension $N$. We introduce auxiliary processes $\mathbf{Y}^j_t$ that approximate $\mathbf{X}_t^{\otimes j}$, derive a linearized system of SDEs for them, and obtain the linear ordinary differential equation (ODE) governing their expectations. We then apply a quantum ODE solver to it and, from the resulting quantum state, extract an estimate for the expectation of a linear function of $\mathbf{X}_t$ by overlap estimation. We show that, provided the nonlinear and noise terms in the SDE are sufficiently small relative to the linear term, the CL error decreases exponentially with the truncation order $J$ in CL, and we can estimate the target expectation with a ${\rm polylog}(N)$ number of queries to unitaries encoding coefficient matrices $A$, $F$, and $B$. Finally, we also run a numerical demonstration for an SDE related to Langevin dynamics, observing the exponential decay of the CL error as $J$ increases.

quant-pharXiv:2610.27416•Oct 21, 2026•0 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
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.
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.
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.
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.
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.
Addressing nonlinear numerical problems in quantum computing remains challenging, but several approaches, including Carleman linearization (CL), have been proposed to construct quantum algorithms for such problems. In this work, we develop a CL-based method for a high-dimensional nonlinear stochastic differential equation (SDE) dXt=(A(t)Xt+F(t)Xt⊗s)dt+B(t)dWt\mathrm{d} \mathbf{X}_t = \left(A(t) \mathbf{X}_t + F(t) \mathbf{X}_t^{\otimes s}\right) \mathrm{d} t + B(t) \mathrm{d} \mathbf{W}_tdXt​=(A(t)Xt​+F(t)Xt⊗s​)dt+B(t)dWt​ for an RN\mathbb{R}^NRN-valued random process Xt\mathbf{X}_tXt​, aiming at quantum speed-up with respect to the dimension NNN. We introduce auxiliary processes Ytj\mathbf{Y}^j_tYtj​ that approximate Xt⊗j\mathbf{X}_t^{\otimes j}Xt⊗j​, derive a linearized system of SDEs for them, and obtain the linear ordinary differential equation (ODE) governing their expectations. We then apply a quantum ODE solver to it and, from the resulting quantum state, extract an estimate for the expectation of a linear function of Xt\mathbf{X}_tXt​ by overlap estimation. We show that, provided the nonlinear and noise terms in the SDE are sufficiently small relative to the linear term, the CL error decreases exponentially with the truncation order JJJ in CL, and we can estimate the target expectation with a polylog(N){\rm polylog}(N)polylog(N) number of queries to unitaries encoding coefficient matrices AAA, FFF, and BBB. Finally, we also run a numerical demonstration for an SDE related to Langevin dynamics, observing the exponential decay of the CL error as JJJ increases.
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.