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 \ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> , there is an at most quadratic quantum speedup in terms of the allowable error $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math> 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.