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$, there is an at most quadratic quantum speedup 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.

arXiv comment37 pages, 0 figures

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Efficient Simulation of Quantum Systems by Quantum Computers
• Preconditioned quantum linear system algorithm
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum algorithms and the finite element method
• Quantum Algorithm for Simulating the Wave Equation
• Efficient Scheme for Initializing a Quantum Register with an Arbitrary Superposed State
• Quantum algorithm for non-homogeneous linear partial differential equations
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment

Cited by in corpus (6)

• Efficient quantum algorithm for dissipative nonlinear differential equations
• Application of a variational hybrid quantum-classical algorithm to heat conduction equation
• Analog quantum simulation of partial differential equations
• A hybrid classical-quantum approach to solve the heat equation using quantum annealers
• Pricing multi-asset derivatives by finite difference method on a quantum computer
• Improving quantum linear system solvers via a gradient descent perspective