Content deleted Content added
m Substing templates: {{Emerging quantum technologies}}. See User:AnomieBOT/docs/TemplateSubster for info. |
→BQP-complete problems: added description of what BQP-complete means |
||
Line 326:
==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 at least as hard as the hardest problems in '''BQP''' and can themselves be efficiently solved by a quantum computer (with bounded error).
===Computing knot invariants===
| |||