Quantum Search

Grover’s Algorithm was proposed by Lov Grover in 1996. Like the Deutsch-Jozsa Algorithm, a quantum algorithm is empirically faster than our fastest classical solution to the same problem. How much faster? Grover’s Algorithm provides a quadratic speedup over its classical counterpart. While at first sight, it is not as remarkable as the exponential speedup of the DJ Algorithm, one can argue that Grover’s solution is immediately useful and provides a great blueprint for solving similar problems.

The problem that Lov Grover solved using his algorithm is related to searching an unordered collection of items. Imagine an unordered list of elements from which we want to search for a particular item. For example, in the following array, we want to find -6, the second-to-last element.