  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-in-$N$ complexity 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
that enables extracting features of the solution. Central to our methodology is
using a wavelet basis as an auxiliary system of coordinates in which the
condition number of associated matrices is 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.
