论文标题
用于求解热方程的量子与经典算法
Quantum vs. classical algorithms for solving the heat equation
论文作者
论文摘要
预计量子计算机的表现要优于求解部分微分方程的经典计算机，这可能是指数级的。在这里，我们考虑了一种典型的PDE-矩形区域中的热方程式 - 并详细比较了十种用于求解它的经典和量子算法的复杂性，从而大致计算给定区域中的热量。我们发现，对于空间尺寸$ d \ ge 2 $，最多可以使用基于将振幅估计的方法应用于加速的经典随机步行来使用方法。但是，基于线性方程的量子算法的替代方法永远不会比最佳的经典算法更快。
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.
