Quantum Algorithm for Linear Systems of Equations
Quantum Algorithm for Linear Systems of Equations
复制标题
DOI：
10.1103/physrevlett.103.150502
复制
发表时间：
2009-10-09
影响因子：
8.6
通讯作者：
Lloyd, Seth
中科院分区：
文献类型：
--
作者：
Harrow, Aram W.;Hassidim, Avinatan;Lloyd, Seth
求解线性方程组是一个常见的问题，它既可以单独出现，也可以作为更复杂问题的子程序出现：给定矩阵A和右箭头上的向量（B），找到右箭头上的向量（x），使得右箭头上的A（x）=右箭头上的（B）。我们考虑这样的情况，其中不需要知道右箭头上的解（x）本身，而是与右箭头上的（x）相关联的某个算子的期望值的近似，例如，(x)在右箭头上（箭头）M（x）在右箭头上对于矩阵M。在这种情况下，当A是稀疏的，N × N并且具有条件数kappa时，已知最快的经典算法可以在时间尺度上粗略地以N根kappa找到右箭头上的（x）并估计右箭头上的（x）（匕首）M（x）。在这里，我们展示了一个量子算法估计（x）在右箭头（匕首）M（x）在右箭头，其运行时间是一个多项式的log（N）和kappa。事实上，对于小的kappa值[即，poly log（N）]，我们证明（使用一些常见的复杂性理论假设），任何经典的算法，这个问题一般需要指数更多的时间比我们的量子算法。
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector (b) over right arrow, find a vector (x) over right arrow such that A (x) over right arrow = (b) over right arrow. We consider the case where one does not need to know the solution (x) over right arrow itself, but rather an approximation of the expectation value of some operator associated with (x) over right arrow, e.g., (x) over right arrow (dagger) M (x) over right arrow for some matrix M. In this case, when A is sparse, N x N and has condition number kappa, the fastest known classical algorithms can find (x) over right arrow and estimate (x) over right arrow (dagger) M (x) over right arrow in time scaling roughly as N root kappa. Here, we exhibit a quantum algorithm for estimating (x) over right arrow (dagger) M (x) over right arrow whose runtime is a polynomial of log(N) and kappa. Indeed, for small values of kappa [i.e., poly log(N)], we prove ( using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.