Quantum algorithms for linear and nonlinear differential equations

Abstract

Quantum computers are expected to dramatically outperform classical computers for certain computational problems. Originally developed for simulating quantum physics, quantum algorithms have been subsequently developed to address diverse computational challenges. There has been extensive previous work for linear dynamics and discrete models, including Hamiltonian simulations and systems of linear equations. However, for more complex realistic problems characterized by differential equations, the capability of quantum computing is far from well understood. One fundamental challenge is the substantial difference between the linear dynamics of a system of qubits and real-world systems with continuum and nonlinear behaviors. My research is concerned with mathematical aspects of quantum computing. In this dissertation, I focus mainly on the design and analysis of quantum algorithms for differential equations. Systems of linear ordinary differential equations (ODEs) and linear elliptic partial differential equations (PDEs) appear ubiquitous in natural and social science, engineering, and medicine. I propose a variety of quantum algorithms based on finite difference methods and spectral methods for producing the quantum encoding of the solutions, with an exponential improvement in the precision over previous quantum algorithms. Nonlinear differential equations exhibit rich phenomena in many domains but are notoriously difficult to solve. Whereas previous quantum algorithms for general nonlinear equations have been severely limited due to the linearity of quantum mechanics, I give the first efficient quantum algorithm for nonlinear differential equations with sufficiently strong dissipation. I also establish a lower bound, showing that nonlinear 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. Overall, utilizing advanced linear algebra techniques and nonlinear analysis, I attempt to build a bridge between classical and quantum mechanics, understand and optimize the power of quantum computation, and discover new quantum speedups over classical algorithms with provable guarantees.