Posts Tagged ‘Grover’s algorithm’

How to search an unsorted database in sub linear order of time?

October 9, 2011 Leave a comment

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. 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.)

Source: Grover’s Algorithm