Efficient Quantum Algorithm for Dissipative Nonlinear Differential Equations

Speaker: Hari Krovi, Raytheon BBN Technologies
June 8, 2021

Presentation

Abstract

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 $T^2\poly(\log T, \log n)/\epsilon$, where T is the evolution time and $\epsilon$ 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> \sqrt{2}. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.

Biography

Hari Krovi is a Senior Scientist at Raytheon BBN technologies. He is broadly interested in quantum information and computing. He specializes in quantum algorithms, quantum cryptography, mathematical modeling, quantum circuits and complexity theory. He has done his PhD in the University of Southern California and postdoctoral work in NEC labs and the University of Connecticut. In BBN, he has worked on several quantum programs and has been a principal investigator for many DoD and DoE projects.

Seminar Participation

Attending In Person

For select seminars, you may wish to attend in-person if you are in the vicinity of NASA Ames Research Center. These AMS seminars are held in Building N258 in Room 127, just off the front lobby. Sessions available to attend in-person will be indicated in the announcement information. In-person participants without NASA badges will need a valid visitor badge (US citizenship or permanent residency is required) to enter the facility.

Join Us Online

To attend an AMS seminar, click on the Microsoft Teams link in the seminar description. You can connect through the desktop Teams App if you have it, or you can select "Watch on the Web Instead" to enter the meeting as a guest. Please ensure that you've muted your microphone in Teams before you select "Join Now" to enter the meeting lobby.