02034nas a2200181 4500008004100000245008100041210006900122260001300191490000800204520146900212100001801681700002501699700002001724700002301744700002501767700002301792856003701815 2021 eng d00aEfficient quantum algorithm for dissipative nonlinear differential equations0 aEfficient quantum algorithm for dissipative nonlinear differenti c3/1/20210 v1183 a
While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R<1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2poly(logT,logn)/ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give an improved 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 of this approach to problems arising in biology as well as in fluid and plasma dynamics.
1 aLiu, Jin-Peng1 aKolden, Herman, Øie1 aKrovi, Hari, K.1 aLoureiro, Nuno, F.1 aTrivisa, Konstantina1 aChilds, Andrew, M. uhttps://arxiv.org/abs/2011.03185