# Bulletin of the American Physical Society

# APS March Meeting 2010

## Volume 55, Number 2

## Monday–Friday, March 15–19, 2010; Portland, Oregon

### 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

#### Author:

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: http://meetings.aps.org/link/BAPS.2010.MAR.D4.2

## Follow Us |
## Engage
Become an APS Member |
## My APS
Renew Membership |
## Information for |
## About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |

© 2015 American Physical Society
| All rights reserved | Terms of Use
| Contact Us

**Headquarters**
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200

**Editorial Office**
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000

**Office of Public Affairs**
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700