Quantum vs. Classical Algorithms for Solving the Heat Equation

Abstract Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially. Here we consider a prototypical PDE—the heat equation in a rectangular region—and compare in detail the complexities of ten classical and quantum algorithms for solving it, in the sense of approximately computing the amount of heat in a given region. We find that, for spatial dimension d 2 d≥2, there is an at most quadratic quantum speedup in terms of the allowable error ϵ using an approach based on applying amplitude estimation to an accelerated classical random walk. However, an alternative approach based on a quantum algorithm for linear equations is never faster than the best classical algorithms.