Editing Quantum algorithm (section)

==BQP-complete problems==
The [[complexity class]] '''[[BQP]]''' (bounded-error quantum polynomial time) is the set of [[decision problems]] solvable by a [[quantum computer]] in [[polynomial time]] with error probability of at most 1/3 for all instances.<ref name="Chuang2000">Michael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. {{isbn|0-521-63503-9}}.</ref> It is the quantum analogue to the classical complexity class '''[[BPP (complexity)|BPP]]'''.

A problem is '''BQP'''-complete if it is in '''BQP''' and any problem in '''BQP''' can be [[Reduction (complexity)|reduced]] to it in [[polynomial time]]. Informally, the class of '''BQP'''-complete problems are those that are as hard as the hardest problems in '''BQP''' and are themselves efficiently solvable by a quantum computer (with bounded error).

===Computing knot invariants===
Witten had shown that the [[Chern-Simons]] [[topological quantum field theory]] (TQFT) can be solved in terms of [[Jones polynomial]]s. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial,<ref>
{{Cite conference
 | last1 = Aharonov | first1 = D.
 | last2 = Jones | first2 = V.
 | last3 = Landau | first3 = Z.
 | year = 2006
 | title = A polynomial quantum algorithm for approximating the Jones polynomial
 | book-title=Proceedings of the 38th Annual ACM symposium on Theory of Computing
 | pages = 427–436
 | publisher=[[Association for Computing Machinery]]
 | doi = 10.1145/1132516.1132579
| arxiv = quant-ph/0511096| isbn = 1595931341
 }}</ref> which as far as we know, is hard to compute classically in the worst-case scenario.{{citation needed|date=December 2014}}

===Quantum simulation===
{{main|Hamiltonian simulation}}
The idea that quantum computers might be more powerful than classical computers originated in Richard Feynman's observation that classical computers seem to require exponential time to simulate many-particle quantum systems, yet quantum many-body systems are able to "solve themselves."<ref>
{{Cite journal
 | last1=Feynman | first1=R. P.
 | year=1982
 | title=Simulating physics with computers
 | journal=[[International Journal of Theoretical Physics]]
 | volume=21 | issue=6–7 | pages=467–488
 | bibcode = 1982IJTP...21..467F
 | doi = 10.1007/BF02650179
| citeseerx=10.1.1.45.9310
 | s2cid=124545445
 }}</ref> Since then, the idea that quantum computers can simulate quantum physical processes exponentially faster than classical computers has been greatly fleshed out and elaborated. Efficient (i.e., polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems,<ref>
{{Cite journal
 | last1=Abrams |first1=D. S.
 | last2=Lloyd | first2=S.
 | year=1997
 | title=Simulation of many-body Fermi systems on a universal quantum computer
 | journal=[[Physical Review Letters]]
 | volume=79 | issue=13 | pages=2586–2589
 | arxiv = quant-ph/9703054
 | bibcode=1997PhRvL..79.2586A
 | doi=10.1103/PhysRevLett.79.2586
|s2cid=18231521
 }}</ref> as well as the simulation of chemical reactions beyond the capabilities of current classical supercomputers using only a few hundred qubits.<ref>
{{Cite journal
 | last1=Kassal | first1=I.
 | last2=Jordan | first2=S. P.
 | last3=Love | first3=P. J.
 | last4=Mohseni | first4=M.
 | last5=Aspuru-Guzik | first5=A.
 | year=2008
 | title=Polynomial-time quantum algorithm for the simulation of chemical dynamics
 | journal=[[Proceedings of the National Academy of Sciences of the United States of America]]
 | volume=105 |issue=48 | pages=18681–86
 | arxiv= 0801.2986
 | bibcode = 2008PNAS..10518681K
 | doi=10.1073/pnas.0808245105
 | pmc=2596249
 | pmid=19033207
| doi-access=free
 }}</ref> Quantum computers can also efficiently simulate topological quantum field theories.<ref>
{{Cite journal
 | last1=Freedman | first1=M.
 | last2=Kitaev | first2=A.
 | last3=Wang | first3=Z.
 | year=2002
 | title=Simulation of Topological Field Theories by Quantum Computers
 | journal=[[Communications in Mathematical Physics]]
 | volume=227 | issue=3 | pages=587–603
 | arxiv = quant-ph/0001071
 | bibcode = 2002CMaPh.227..587F
 | doi=10.1007/s002200200635
| s2cid=449219
 }}</ref> In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating [[Quantum invariant|quantum topological invariants]] such as [[Jones polynomial|Jones]]<ref>
{{Cite journal
 | last1=Aharonov | first1=D.
 | last2=Jones | first2=V.
 | last3=Landau | first3=Z.
 | year=2009
 | title=A polynomial quantum algorithm for approximating the Jones polynomial
 | journal=[[Algorithmica]]
 | volume=55 | issue=3 | pages=395–421
 | arxiv=quant-ph/0511096
 | doi=10.1007/s00453-008-9168-0
| s2cid=7058660
 }}</ref> and [[HOMFLY polynomial]]s,<ref>
{{Cite journal
 | last1=Wocjan |first1=P.
 | last2=Yard | first2=J.
 | year=2008
 | title=The Jones polynomial: quantum algorithms and applications in quantum complexity theory
 | journal=[[Quantum Information and Computation]]
 | volume=8 | issue=1 | pages=147–180
 |doi=10.26421/QIC8.1-2-10
 | arxiv=quant-ph/0603069
|bibcode = 2006quant.ph..3069W |s2cid=14494227
 }}</ref> and the [[Turaev-Viro invariant]] of three-dimensional manifolds.<ref>
{{Cite journal
 |last1=Alagic | first1=G.
 |last2=Jordan | first2=S.P.
 |last3=König | first3=R.
 |last4=Reichardt | first4=B. W.
 |year=2010
 |title=Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
 |journal=[[Physical Review A]]
 |volume=82 |issue=4 |pages=040302
 |arxiv=1003.0923
 |bibcode=2010PhRvA..82d0302A
 |doi=10.1103/PhysRevA.82.040302
| s2cid=28281402
 }}</ref>

===Solving a linear system 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|s2cid = 5187993}}</ref>

Provided that the linear system is [[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).