Fast quantum algorithm for differential equations
Mohsen Bagherimehrab, Kouhei Nakaji, Nathan Wiebe, Brennen, Gavin K., Sanders, Barry C., Aspuru-Guzik, Alán · arXiv (Cornell University) · 2023
Partial differential equations (PDEs) are ubiquitous in science and engineering. Prior quantum algorithms for solving the system of linear algebraic equations obtained from discretizing a PDE have a computational complexity that scales at least linearly with the condition number $κ$ of the matrices involved in the computation. For many practical applications, $κ$ scales polynomially with the size $N$ of the matrices, rendering a polynomial complexity in $N$ for these algorithms. Here we present a quantum algorithm with a complexity that is polylogarithmic in $N$ but is independent of $κ$ for a large class of PDEs. Our algorithm generates a quantum state from which features of the solution can be extracted. Central to our methodology is using a wavelet basis as an auxiliary system of coordinates in which the condition number of associated matrices becomes independent of $N$ by a simple diagonal preconditioner. We present numerical simulations showing the effect of the wavelet preconditioner for several differential equations. Our work could provide a practical way to boost the performance of quantum simulation algorithms where standard methods are used for discretization.