Content deleted Content added
m I added a link to Wikipedia page on probabalistic Turing machines where it is first mentioned. |
I began a section on simulating quantum circuits and added the fourth source and used it as in text citation for this section. |
||
Line 8:
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>
== Quantum query complexity[edit] ==
In the query complexity model, the input is given as an oracle (black box). The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.
Quantum query complexity is the smallest number of queries to the oracle that are required in order to calculate the function. This makes the quantum query complexity a lower bound on the overall time complexity of a function.
An example depicting the power of quantum computing is [[Grover's algorithm]] for searching unstructured databases. The algorithm's quantum query complexity is , a quadratic improvement over the best possible classical query complexity , which is a [[linear search]]. While Grover's algorithm is more optimized than the best possible classical algorithm, we know that Grover's algorithm is not one hundred percent optimal.<ref>{{Cite journal|last=Ambainis|first=Andris|date=October 28, 2005|title=Polynomial degree vs. quantum query complexity|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000005000899|journal=Journal of Computer and System Sciences|language=en|volume=72|issue=2|pages=220–238|doi=10.1016/j.jcss.2005.06.006|via=}}</ref>
== Simulating Quantum Circuits ==
There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time. However, a quantum circuit of <math>S(n)</math> qubits with <math>O(T(n))</math> [[quantum gates]] can be simulated by a classical circuit with <math>O(2^{S(n)}T(n)^3)</math> classical gates<ref>{{Citation|last=Cleve|first=Richard|title=An Introduction to Quantum Complexity Theory|date=2000|url=http://dx.doi.org/10.1142/9789810248185_0004|work=Quantum Computation and Quantum Information Theory|volume=|pages=103–127|publisher=WORLD SCIENTIFIC|isbn=978-981-02-4117-9|access-date=October 10, 2020}}</ref>
== References ==
{{Reflist}}
| |||