Quantum complexity theory: Difference between revisions

Revision as of 21:37, 30 September 2014

Revision as of 10:39, 23 November 2014

Line 6:

==Quantum Query Complexity==

It is one ofIn 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, the input is given as an oracle (Blackblack Boxbox). WeThe getalgorithm thegets information about the input only by querying the oracle. In the start ofThe algorithm we startstarts in some fixed quantum state and the state evolves as weit queryqueries 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.

Quantum Query Complexity is the smallest number of queries to the oracle that are required in order to calculate the function. Clearly, Quantum Query Complexity is a lower bound on the overall time complexity of a function.

[[Grover's algorithm]] for searching unstructured database 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.

An example depicting the power of Quantum Computing is [[Grover's algorithm]] for searching unstructured databasedatabases. is one of the best example depicting the power of Quantum Computing.Its Quantum Query Complexity of Grover Search is ''O''(''N''^1/2) which is quadratically better than the best known classical query compleixtycomplexity.

==References==