Session D4: Quantum Computer Science

2:30 PM–5:30 PM, Monday, March 15, 2010
Room: Oregon Ballroom 204

Sponsoring Unit: GQI
Chair: Dave Bacon, University of Washington

Abstract ID: BAPS.2010.MAR.D4.2

Abstract: D4.00002 : A quantum algorithm for solving linear systems of equations

3:06 PM–3:42 PM

Preview Abstract   MathJax On | Off     Abstract  


  Aram Harrow
    (University of Bristol, UK)

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.\\[4pt] This talk is based on arXiv:0811.3171, which is joint work with Avinatan Hassidim and Seth Lloyd.

To cite this abstract, use the following reference: