High-precision quantum algorithms for partial differential equations
High-precision quantum algorithms for partial differential equations
复制标题
DOI：
10.22331/q-2021-11-10-574
复制
发表时间：
2021-11-04
期刊：
影响因子：
6.4
通讯作者：
Ostrander, Aaron
中科院分区：
文献类型：
--
作者：
Childs, Andrew M.;Liu, Jin-Peng;Ostrander, Aaron
量子计算机可以产生微分方程组的解的量子编码，其速度指数级快于经典算法产生显式描述的速度。然而，虽然解线性常微分方程组的高精度量子算法已经建立得很好，但以往解线性偏微分方程组(PDE)的最好的量子算法具有复杂性Poly1/epsilon，其中epsilon是容错性。通过发展基于自适应阶差分方法和谱方法的量子算法，我们将线性偏微分方程组的量子算法的复杂度提高到Poly(d，log(1/epsilon))，其中d是空间维度。我们的算法将高精度量子线性系统算法应用于条件数和近似误差都有界的系统。我们给出了Poisson方程的有限差分算法和更一般的二阶椭圆型方程的谱算法。
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 poly(1/epsilon), where epsilon 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 poly(d, log( 1/epsilon)), 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.