%0 Generic %1 harrow2008quantum %A Harrow, Aram W. %A Hassidim, Avinatan %A Lloyd, Seth %D 2008 %K quantum %R 10.1103/PhysRevLett.103.150502 %T Quantum algorithm for solving linear systems of equations %U http://arxiv.org/abs/0811.3171 %X 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.

@misc{harrow2008quantum, 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.}, added-at = {2020-01-21T15:22:47.000+0100}, author = {Harrow, Aram W. and Hassidim, Avinatan and Lloyd, Seth}, biburl = {https://www.bibsonomy.org/bibtex/2810906b7b315365f05fc6ef14f22c8bd/cmcneile}, description = {Quantum algorithm for solving linear systems of equations}, doi = {10.1103/PhysRevLett.103.150502}, interhash = {578360255c8d7c55eacf515a23ee7363}, intrahash = {810906b7b315365f05fc6ef14f22c8bd}, keywords = {quantum}, note = {cite arxiv:0811.3171Comment: 15 pages. v2 is much longer, with errors fixed, run-time improved and a new BQP-completeness result added. v3 is the final published version and mostly adds clarifications and corrections to v2}, timestamp = {2020-01-21T15:22:47.000+0100}, title = {Quantum algorithm for solving linear systems of equations}, url = {http://arxiv.org/abs/0811.3171}, year = 2008 }