Quantum algorithm for solving linear systems of equations
APA
Harrow, A. (2009). Quantum algorithm for solving linear systems of equations. Perimeter Institute. https://pirsa.org/08050061
MLA
Harrow, Aram. Quantum algorithm for solving linear systems of equations. Perimeter Institute, May. 04, 2009, https://pirsa.org/08050061
BibTex
@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}} }
Massachusetts Institute of Technology (MIT) - Department of Physics
Collection
Talk Type
Subject
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.