Quantum algorithm for solving linear systems of equations

          @misc{ pirsa_PIRSA:08050061,
            doi = {10.48660/08050061},
            url = {https://pirsa.org/08050061},
            author = {Harrow, Aram},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum algorithm for solving linear systems of equations},
            publisher = {Perimeter Institute},
            year = {2009},
            month = {may},
            note = {PIRSA:08050061 see, \url{https://pirsa.org}}
          }
          

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. Often, 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'Mx for some matrix M. In this case, when A is sparse and well-conditioned, with largest dimension N, the best known classical algorithms can find x and estimate x'Mx in O(N * poly(log(N))) time. In this talk I'll describe a quantum algorithm for solving linear sets of equations that runs in poly(log N) time, an exponential improvement over the best classical algorithm. This talk is based on my paper arXiv:0811.3171v2, which was written with Avinatan Hassidim and Seth Lloyd.