Quantum Spectral Methods for Differential Equations
Quantum Spectral Methods for Differential Equations
复制标题
DOI：
10.1007/s00220-020-03699-z
复制
发表时间：
2020-02-18
影响因子：
2.4
通讯作者：
Liu, Jin-Peng
中科院分区：
文献类型：
--
作者：
Childs, Andrew M.;Liu, Jin-Peng
最近发展起来的量子算法通过在希尔伯特空间中执行线性代数来解决数值分析中的计算挑战。这样的算法可以产生与d维线性方程组或具有复杂性Poly(Logd)的线性微分方程组的解成比例的量子态。虽然这些算法中有几个算法以复杂的Poly(log(1/epsilon))逼近epsilon内的解，但对于具有时间相关系数的微分方程组，以前还没有这样的算法。在这里，我们发展了一个基于所谓的谱方法的线性常微分方程组的量子算法，这是一种全局逼近解的有限差分方法的替代方法。利用这种方法，我们给出了一个求解复杂Poly(logd，log(1/epsilon))含时初边值问题的量子算法。
Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(log d). While several of these algorithms approximate the solution to within epsilon with complexity poly(log(1/epsilon)), no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(log d, log(1/epsilon)).