HackerPapers

arXiv:0811.3171quant-ph

Quantum algorithm for solving linear systems of equations

Aram W. Harrow, Avinatan Hassidim, Seth Lloyd

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.

arXiv comments
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
Journal reference
Phys. Rev. Lett. vol. 15, no. 103, pp. 150502 (2009)
DOI
doi:10.1103/PhysRevLett.103.150502
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jun 2013 to Jun 2017. Found in 1 HN submission from Nov 2009 to Nov 2009. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Solving systems of linear equations with quantum mechanics 1 comment

    • Exponentially better than a polynomial in N is a polynomial in log N. See the abstract of [1] for the precise complexity claim about the algorithm mentioned in the article. As good as N^3 sounds, it's still not great on enormous systems. [1] https://arxiv.org/abs/0811.3171

      cvossView on HNParent context

  2. What could the NSA do with a quantum computer? 1 comment

    • He might be referring to this: http://arxiv.org/pdf/0811.3171v3.pdf So, if the question you want to ask is "what is some property of the solution of the (sparse) set of linear equations" rather than wanting to know the (inherently O(n)) solution itself, you can get exponential…

      drkevorkianView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.