Quantum algorithm

Quantum mechanics

Algorithm

Pure mathematics

Dimension (graph theory)

Operating system

Heat equation

Computer science

Speedup

Physics

Mathematics

Quadratic equation

Mathematical analysis

Geometry

Quantum

Combinatorics

Communications in Mathematical Physics

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.

Quantum vs. Classical Algorithms for Solving the Heat Equation