Towards Quantum Speedup for Solving High-Dimensional Partial Differential Equations

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Efficient simulation of high-dimensional partial differential equations has been one of the core tasks in many scientific areas. Recent advances of quantum technologies and algorithms revealed that quantum algorithms can be a new tool to overcome the curse of dimensionality, with the potential of achieving exponential speedups compared to classical implementations. The goal of this project is to investigate potential applications of quantum algorithms on efficiently solving high-dimensional differential equations. Taking advantage of the power of quantum mechanics, the newly proposed quantum algorithms and techniques are expected to significantly accelerate the simulation of such high-dimensional PDEs and give a cost depending poly-logarithmically on the total number of spatial grids and polynomially on the spatial dimension. The development of proposed projects will provide new prospects to overcome the curse of dimensionality in PDE simulations, to advance the state-of-the-art quantum algorithm designed for differential equations, and to help pave the path towards post-quantum scientific computing. On the educational side, the students involved will get good interdisciplinary training in both mathematics and quantum information science. This project aims to develop efficient quantum algorithms for high-dimensional differential equations for both quantum and classical problems, and to establish rigorous error bounds and complexity estimates, and identify the problems that can and can not be efficiently handled quantumly. Such high-dimensional differential equations include the Schrodinger equation with applications to molecular dynamics, and other classical differential equations, such as reaction-diffusion equations emerging from biological applications. The following specific aspects will be addressed. For quantum dynamics simulation, the goal is to deal with dynamics simulation with unbounded operators, we explore techniques such as the vector norm scaling analysis, quantum highly oscillatory protocol in the interaction picture, and semiclassical/microlocal analysis addressing the multiscale aspects of the problem. For classical dynamics that can be non-unitary, we propose and explore time-marching strategies using block encoding oracles, and aim to provide a pedagogical description on quantum algorithms for stiff differential equations, pinpointing the differences between quantum algorithm design and classical numerical analysis. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.