Sunday 31 December 2017

Grover's algorithm for the unstructured search problem

After Peter Shor showed how quantum computers can factor numbers efficiently, interest surged in finding other problems which quantum methods solved faster than the best known classical techniques. In 1996 Lov Grover developed such a quantum algorithm for solving the unstructured search problem.

In a generic search problem, we are given a set $S$ of $N$ items. Some of the items in the set are marked. Our task is to find a marked item in the set $S$.

You can think of a search problem like looking up a name in a list. In most cases, the list will be arranged in a way that makes finding names easier. For example, a list of names is often sorted alphabetically. Here we are talking about a list with no discernible ordering. In this case, the best we could do is to check each entry for the desired name.