Grover's algorithm

 related topics {math, number, function} {math, energy, light} {rate, high, increase} {county, mile, population}

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space (see big O notation). It was invented by Lov Grover in 1996.

In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N1/2) is asymptotically the fastest possible for searching an unsorted database in the quantum model.[1] It provides a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when N is large.

Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa algorithm, which always produces the correct answer.)

Contents

Applications

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". Roughly speaking, if we have a function y=f(x) that can be evaluated on a quantum computer, this algorithm allows us to calculate x when given y. Inverting a function is related to the searching of a database because we could come up with a function that produces a particular value of y if x matches a desired entry in a database, and another value of y for other values of x.

Grover's algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the Collision problem. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand.

Setup

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by n=log2 N qubits.