Revision as of 00:22, 11 October 2020 edit ColeDU (talk \| contribs) 61 edits added a paragraph about how computational complexity of functions are expressed with asymptotic notation and I added an intext citation using what was source four, but is now source two because it is now cited earlier in the document. Tag: Visual edit ← Previous edit		Revision as of 00:36, 11 October 2020 edit undo ColeDU (talk \| contribs) 61 edits removed the quantum query complexity section for the time being to make the page less cluttered while I'm not working on that section. Tag: Visual edit Next edit →
Line 10: 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 ==

User:ColeDU/Quantum complexity theory: Difference between revisions