June 10, 2022
Colloquium Topic: An efficient quantum algorithm for dissipative nonlinear partial differential equations
Models governed by both ordinary differential equations (ODEs) and partial differential equations (PDEs) arise extensively in the natural and social sciences, medicine, and engineering. Such equations characterize physical and biological systems that exhibit a wide variety of complex phenomena, including turbulence and chaos. In this talk, we focus on differential equations with nonlinearities that can be expressed with quadratic polynomials, which include many archetypal models in biology, fluid dynamics, and plasma physics.
Quantum algorithms offer the prospect of rapidly characterizing the solutions of high-dimensional systems of linear ODEs and PDEs. Such algorithms can produce a quantum state proportional to the solution of a sparse (or block- encoded) n-dimensional system of linear differential equations in time poly(logn) using the quantum linear system algorithm (QLSA) (cf. Harrow et al (2009), Childs et al (2016)).
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. Finally, we discuss potential applications, showing that the imposed condition can be satisfied in realistic epidemiological models.
The article ``Efficient quantum algorithm for dissipative nonlinear partial differential equations" appeared recently in the Proceedings of the National Academy of Sciences (PNAS 2021).
Authors: J.-P. Liu, H. Kolden, H. Krovi, N. Loureiro, K. Trivisa, and A. Childs.
Colloquium Speaker: Konstantina Trivisa
Konstantina Trivisa is an applied mathematician and the Director of the Institute for Physical Science and Technology (IPST), at the University of Maryland. She received her Ph.D. in 1996 from the Division of Applied Mathematics at Brown University. Her research focuses on the modeling and analysis of systems arising in fluid dynamics, plasma physics, biomedical problems, quantum dynamics, and on the construction of numerical algorithms for their approximation. Her research has been recognized by a series of awards including an Alfred P. Sloan Research Fellowship, The Faculty Early Career Award, The Presidential Early Career Award for Scientists and Engineers (PECASE) as well as a Simons Foundation Fellowship. She was also selected as ADVANCE Professor and Leadership Fellow at the University of Maryland for her work on issues of diversity and inclusion. She served as Director of the Applied Mathematics & Statistics, and Scientific Computation Program (AMSC) in the period 2007-2018 and was recognized with the 2018 Outstanding Director of Graduate Studies Award. She is member of Spectra (the Association for LGBTQ+ Mathematicians) and in 2021 served as member of the organizing committee of the Spectra LGBTQ+ in Mathematics Conference organized at the Institute for Computational and Experimental Research in Mathematics (ICERM).