Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision
Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision
复制标题
DOI：
10.1007/s00220-017-3002-y
复制
发表时间：
2017-12-01
影响因子：
2.4
通讯作者：
Wang, Guoming
中科院分区：
文献类型：
--
作者：
Berry, Dominic W.;Childs, Andrew M.;Wang, Guoming
给出了常系数(可能非齐次)线性常微分方程组的量子算法。该算法在期望的最终时间产生与解成正比的量子态。该算法的复杂度在逆误差的对数中是多项式的，比以往解决该问题的量子算法有了指数级的改进。我们的结果建立在量子线性系统算法的最新进展的基础上，通过将模拟编码到一个稀疏的、条件良好的线性系统中，该系统使用泰勒级数根据传播子近似进化。与有限差分法不同，我们的方法不需要额外的假设来确保数值稳定性。
We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.