Content deleted Content added
HHL not only uses Amplitude amplification, it also uses Phase estimation (see: https://arxiv.org/abs/0811.3171). Since this algorithm is BQP-complete, i'll be moving it to the BQP-complete section Tag: section blanking |
Solving Linear systems of equations is BQP-complete (see https://arxiv.org/abs/0811.3171), so i'm putting it here. |
||
Line 428:
|doi=10.1103/PhysRevA.82.040302
}}</ref>
===Solving a linear systems of equations===
{{main|Quantum algorithm for linear systems of equations}}
In 2009 [[Aram Harrow]], Avinatan Hassidim, and [[Seth Lloyd]], formulated a quantum algorithm for solving [[System of linear equations|linear systems]]. The [[Quantum algorithm for linear systems of equations|algorithm]] estimates the result of a scalar measurement on the solution vector to a given linear system of equations.<ref name="Quantum algorithm for solving linear systems of equations by Harrow et al.">{{Cite journal|arxiv = 0811.3171|last1 = Harrow|first1 = Aram W|title = Quantum algorithm for solving linear systems of equations|journal = Physical Review Letters|volume = 103|issue = 15|pages = 150502|last2 = Hassidim|first2 = Avinatan|last3 = Lloyd|first3 = Seth|year = 2008|doi = 10.1103/PhysRevLett.103.150502|pmid = 19905613|bibcode = 2009PhRvL.103o0502H}}</ref>
Provided the linear system is a [[sparse matrix|sparse]] and has a low [[condition number]] <math>\kappa</math>, and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of <math>O(\log(N)\kappa^2)</math>, where <math>N</math> is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in <math>O(N\kappa)</math> (or <math>O(N\sqrt{\kappa})</math> for positive semidefinite matrices).
==Hybrid quantum/classical algorithms==
| |||