Efficient quantum algorithm for dissipative nonlinear differential equations

Abstract

Significance Nonlinear differential equations appear in many domains and are notoriously difficult to solve. Whereas previous quantum algorithms for general nonlinear differential equations have complexity exponential in the evolution time, we give the first quantum algorithm for dissipative nonlinear differential equations that is efficient provided the dissipation is sufficiently strong relative to nonlinear and forcing terms and the solution does not decay too rapidly. We also establish a lower bound showing that differential equations with sufficiently weak dissipation have worst-case complexity exponential in time, giving an almost tight classification of the quantum complexity of simulating nonlinear dynamics. Furthermore, numerical results for the Burgers equation suggest that our algorithm may potentially address complex nonlinear phenomena even in regimes with weaker dissipation. 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 R<1, where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity T2q poly(log⁡T,log⁡n,log⁡1/ϵ)/ϵ, 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 R≥2. Finally, we discuss potential applications, showing that the R<1 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.