论文标题
偏微分方程的高精度量子算法
High-precision quantum algorithms for partial differential equations
论文作者
论文摘要
量子计算机可以生成比经典算法更快的微分方程系统的量子编码，可以产生明确的描述。但是，尽管已良好地确定了线性普通微分方程的高精度量子算法，但线性偏微分方程（PDES）的最佳先前量子算法具有复杂性$ \ mathrm {poly}（1/ε）$，其中$ε$是误差。通过基于自适应阶有限差异方法和光谱方法开发量子算法，我们将线性PDE的量子算法的复杂性提高为$ \ mathrm {poly}（d，\ \ log log（1/ε）$，其中$ d $是空间尺寸。我们的算法将高精度量子线性系统算法应用于我们绑定的条件数和近似误差的系统。我们为泊松方程开发了有限的差异算法和更通用的二阶椭圆方程的光谱算法。
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity $\mathrm{poly}(1/ε)$, where $ε$ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be $\mathrm{poly}(d, \log(1/ε))$, where $d$ is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
