Grover's algorithm: Difference between revisions - Wikipedia

Line 20:

Although the purpose of Grover's algorithm is usually described as "searching a database", it may be more accurate to describe it as "inverting a function". In fact since the [[oracle machine|oracle]] for an unstructured database requires at least linear complexity, the algorithm cannot be used for actual databases.<ref>https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf</ref> Roughly speaking, if a function <math>y = f(x)</math> can be evaluated on a quantum computer, Grover's algorithm calculates <math>x</math> when given <math>y</math>. Inverting a function is related to the searching of a database because we could come up with a function that produces one particular value of <math>y</math> ("true", for instance) if <math>x</math> matches a desired entry in a database, and another value of <math>y</math> ("false") for other values of <math>x</math>.

Grover's algorithm can also be used for estimating the [[mean]] and [[median]] of a set of numbers.<ref>{{cite arxiv|eprint=quant-ph/9711043|last1=Grover|first1=Lov K.|title=A framework for fast quantum mechanical algorithms|year=1997}}</ref> The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand. Grover's algorithm has implications for the security of symmetric cryptography as it can be used to search the key space. This is not necessarily the most efficient algorithm, for example the parallel rho algorithm is able to find a collision in SHA2 more efficiently than Grover's.

== Setup ==