## 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 , 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.

Original language | English |
---|---|

Pages (from-to) | 601-641 |

Number of pages | 41 |

Journal | Communications in Mathematical Physics |

Volume | 395 |

Issue number | 2 |

Early online date | 24 Aug 2022 |

DOIs | |

Publication status | Published - Oct 2022 |

### Bibliographical note

Funding Information:We would like to thank Jin-Peng Liu and Gui-Lu Long for comments on a previous version, and two anonymous referees for helpful suggestions which improved this work. We acknowledge support from the QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union’s Horizon 2020 Programme (QuantAlgo project), EPSRC grants EP/R043957/1 and EP/T001062/1, and EPSRC Early Career Fellowship EP/L021005/1. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 817581). No new data were created during this study.

Publisher Copyright:

© 2022, The Author(s).