Fast quantum algorithm for differential equations

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 kappa of the matrices involved in the computation. For many practical applications, kappa 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 kappa 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.