Content deleted Content added
I added a statment about the capabilities of efficiently simulating classical computers with quantum computers and vice versa. I also added source two and used it as an intext citation for this. |
m I added a link to Wikipedia page on probabalistic Turing machines where it is first mentioned. |
||
Line 5:
A [[complexity class]] is a collection of [[Computational problem|computational problems]] that can be solved by a computational model under certain resource constraints. For instance, the complexity class [[P (complexity)|P]] is defined as the set of problems solvable by a [[Turing machine]] in [[polynomial time]]. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the [[Quantum computer|quantum circuit model]] or the equivalent [[quantum Turing machine]]. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as [[P (complexity)|P]], [[NP (complexity)|NP]], [[BPP (complexity)|BPP]], and [[PSPACE]].
One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern [[Church–Turing thesis|Church-Turing thesis]]. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a [[probabilistic Turing machine]].<ref name=":0">{{Cite journal|last=Vazirani|first=Umesh V.|date=2002|title=A survey of quantum complexity theory|url=http://dx.doi.org/10.1090/psapm/058/1922899|journal=Proceedings of Symposia in Applied Mathematics|pages=193–217|doi=10.1090/psapm/058/1922899|issn=2324-7088}}</ref> However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold and that it may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time.<ref name=":0" />
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 fact that <math>BBP\subseteq BQP</math>.<ref>{{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>
| |||