Quantum algorithm for solving linear systems of equations Export

@article{citeulike:3580901, abstract = {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 doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.}, archivePrefix = {arXiv}, author = {Harrow, Aram W. and Hassidim, Avinatan and Lloyd, Seth}, citeulike-article-id = {3580901}, citeulike-linkout-0 = {http://arxiv.org/abs/0811.3171}, citeulike-linkout-1 = {http://arxiv.org/pdf/0811.3171}, day = {30}, eprint = {0811.3171}, keywords = {algorithm, linear, maths, physics}, month = {Sep}, posted-at = {2008-11-20 11:01:55}, priority = {2}, title = {Quantum algorithm for solving linear systems of equations}, url = {http://arxiv.org/abs/0811.3171}, year = {2009} }

TY - JOUR ID - citeulike:3580901 L3 - citeulike-article-id:3580901 N2 - 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 doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm. TI - Quantum algorithm for solving linear systems of equations KW - algorithm KW - linear KW - maths KW - physics AU - Harrow, Aram AU - Hassidim, Avinatan AU - Lloyd, Seth PY - 2009/Sep/30/ UR - http://arxiv.org/abs/0811.3171 ER -