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 A x ⃗= b ⃗ . We consider the case where 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 ⃗ †M x ⃗ for some matrix M . In this case, when A is sparse, N × N and has condition number κ , the fastest known classical algorithms can find x ⃗ and estimate x ⃗ †M x ⃗ in time scaling roughly as N âˆs κ . Here, we exhibit a quantum algorithm for estimating x ⃗ †M x ⃗ whose runtime is a polynomial of log â�!`( N ) and κ . Indeed, for small values of κ i.e., poly log â�!`( N ) , we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
%0 Journal Article
%1 Harrow2009Quantum
%A Harrow, Aram W.
%A Hassidim, Avinatan
%A Lloyd, Seth
%D 2009
%I American Physical Society
%J Physical Review Letters
%K quantum-algorithm
%N 15
%P 150502+
%R 10.1103/physrevlett.103.150502
%T Quantum Algorithm for Linear Systems of Equations
%U http://dx.doi.org/10.1103/physrevlett.103.150502
%V 103
%X 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 A x ⃗= b ⃗ . We consider the case where 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 ⃗ †M x ⃗ for some matrix M . In this case, when A is sparse, N × N and has condition number κ , the fastest known classical algorithms can find x ⃗ and estimate x ⃗ †M x ⃗ in time scaling roughly as N âˆs κ . Here, we exhibit a quantum algorithm for estimating x ⃗ †M x ⃗ whose runtime is a polynomial of log â�!`( N ) and κ . Indeed, for small values of κ i.e., poly log â�!`( N ) , we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
@article{Harrow2009Quantum,
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 \^{a}ƒ— , find a vector x \^{a}ƒ— such that A x \^{a}ƒ—= b \^{a}ƒ— . We consider the case where one does not need to know the solution x \^{a}ƒ— itself, but rather an approximation of the expectation value of some operator associated with x \^{a}ƒ— , e.g., x \^{a}ƒ— \^{a}€ M x \^{a}ƒ— for some matrix M . In this case, when A is sparse, N \~{A}— N and has condition number \^{I}º , the fastest known classical algorithms can find x \^{a}ƒ— and estimate x \^{a}ƒ— \^{a}€ M x \^{a}ƒ— in time scaling roughly as N \^{a}ˆ\v{s} \^{I}º . Here, we exhibit a quantum algorithm for estimating x \^{a}ƒ— \^{a}€ M x \^{a}ƒ— whose runtime is a polynomial of log \^{a}�!`( N ) and \^{I}º . Indeed, for small values of \^{I}º [i.e., poly log \^{a}�!`( N ) ], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.}},
added-at = {2019-02-26T15:22:34.000+0100},
author = {Harrow, Aram W. and Hassidim, Avinatan and Lloyd, Seth},
biburl = {https://www.bibsonomy.org/bibtex/27c8af80a6197b7b1be0fd0e4d31f5182/rspreeuw},
citeulike-article-id = {5917501},
citeulike-linkout-0 = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=PRLTAO000103000015150502000001\&idtype=cvips\&gifs=yes},
citeulike-linkout-1 = {http://link.aps.org/abstract/PRL/v103/e150502},
citeulike-linkout-2 = {http://dx.doi.org/10.1103/physrevlett.103.150502},
citeulike-linkout-3 = {http://link.aps.org/abstract/PRL/v103/i15/e150502},
citeulike-linkout-4 = {http://link.aps.org/pdf/PRL/v103/i15/e150502},
doi = {10.1103/physrevlett.103.150502},
interhash = {296989bc6772a20148dc3b2ecfaba2f0},
intrahash = {7c8af80a6197b7b1be0fd0e4d31f5182},
journal = {Physical Review Letters},
keywords = {quantum-algorithm},
month = oct,
number = 15,
pages = {150502+},
posted-at = {2009-12-03 09:44:18},
priority = {2},
publisher = {American Physical Society},
timestamp = {2019-02-26T15:22:34.000+0100},
title = {{Quantum Algorithm for Linear Systems of Equations}},
url = {http://dx.doi.org/10.1103/physrevlett.103.150502},
volume = 103,
year = 2009
}