Department of Mathematics, University of Bristol, Bristol, BS8 1TW, United Kingdom.
Phys Rev Lett. 2009 Oct 9;103(15):150502. doi: 10.1103/PhysRevLett.103.150502. Epub 2009 Oct 7.
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(-->), find a vector x(-->) such that Ax(-->) = b(-->). We consider the case where one does not need to know the solution x(-->) itself, but rather an approximation of the expectation value of some operator associated with x(-->), e.g., x(-->)(dagger) Mx(-->) 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(-->) and estimate x(-->)(dagger) Mx(-->) in time scaling roughly as N square root(kappa). Here, we exhibit a quantum algorithm for estimating x(-->)(dagger) Mx(-->) 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.
求解线性方程组是一个常见的问题，它不仅自身存在，而且作为更复杂问题的子程序也会出现：给定一个矩阵 A 和一个向量 b（--->），找到一个向量 x（--->），使得 Ax（--->）= b（--->）。我们考虑这样一种情况，即不需要知道解 x（--->）本身，而是需要估计与 x（--->）相关的某个算符的期望值，例如，对于某个矩阵 M，有 x（--->）（dagger）Mx（--->）。在这种情况下，当 A 是稀疏的、N x N 且条件数为 kappa 时，最快的已知经典算法可以在时间复杂度大致为 N 平方根（kappa）的情况下找到 x（--->）并估计 x（-->）（dagger）Mx（--->）。在这里，我们展示了一种用于估计 x（-->）（dagger）Mx（--->）的量子算法，其运行时间是 log（N）和 kappa 的多项式。实际上，对于小的 kappa 值（即 poly log（N）），我们证明（使用一些常见的复杂性理论假设），对于这个问题的任何经典算法，通常都需要比我们的量子算法多指数级的时间。
