Content deleted Content added
m Changed fact to belief in background. |
Added section on complexty classes overview and cited source 3 |
||
Line 13:
While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the belief that <math>BBP\subseteq BQP</math>.<ref name=":2">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>
<u>the above is a great insight but it kind comes out of no where. How does it relate to what you have already discusses or what you will discuss later on</u>
== Complexity Classes Overview ==
Some important complexity classes are P, NP, BPP, BQP, PP, and P-Space. To define these we first define a promise problem. A promise problem is a decision problem which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair <math>A=(A_{yes},A_{no})</math>. <math>A_{yes}</math> is the set of yes instances, <math>A_{no}</math> is the set of no instances, and the intersection of these sets is such that <math>A_{yes}\cap A_{no}=\emptyset</math>. All of the previous complexity classes contain promise problems.<ref name=":2" />
== Quantum Circuits ==
| |||