Content deleted Content added
removing gibberish |
No edit summary |
||
Line 4:
Two important quantum complexity classes are [[BQP]] and [[QMA]] which are the bounded-error quantum analogues of [[P_(complexity)|P]] and [[NP_(complexity)|NP]]. One of the main aims of quantum complexity theory is to find out where these classes lie with respect to classical complexity classes such as P, NP, [[PP_(complexity)|PP]], [[PSPACE]] and [[List of complexity classes|other complexity classes]].
==Quantum Query Complexity==
It is one of the major field of Quantum Complexity Theory which deals with the number of queries to input in order to calculate the function. In query complexity model, input is given as oracle(Black Box). We get the information about the input by quering oracle. In the start of algorithm we start in some fixed quantum state and the state evolves as we query the oracle. We have to develop an algorithm which minimizes the number of queries required to calculate function. Clearly, Quantum Query Complexity is lower bound on overall time complexity of function and sometimes more important than time complexity.
[[Grover's algorithm]] is one of the best example depicting the power of Quantum Computing. Quantum Query Complexity of Grover Search is O(N^1/2) which is quadratically better than best known classical query compleixty.
==References==
*{{cite arXiv|eprint=0804.3401v1|author1=John Watrous|authorlink=John Watrous (computer scientist)|title=Quantum Computational Complexity|class=quant-ph|year=2008}}
*{{cite book| author = [[Artem Kaznatcheev]]|title= Quantum query complexity| url= http://cstheory.blogoverflow.com/2011/07/quantum-query-complexity/}}
{{comp-sci-theory-stub}}
| |||