Grover Search Algorithm

The first algorithm we will tackle is the Grover search algorithm, which is a quantum algorithm that speeds up searching through databases. Lov Grover developed the algorithm in 1996. Although there are now many improved variations on the original algorithm, we’ll take a close look at how the original works because it uses a strategy that many other quantum algorithms use.

First, let’s think about a classical search question. Suppose we have $N$ cards, only one of which has a special purple dot on it. If we spread the cards out face down on a table, how many cards do we need to turn over to find the one with the purple dot? Well, we might be lucky and find it on the first try. More likely, we will have to turn over many cards before finding the one with the purple dot. In the worst case, we might turn over $N − 1$ cards without seeing the purple dot. If that happens, we know that the dot must be on the remaining card, but we still turn it over to make sure that no one has messed with the cards. It turns out that on average, we need to flip just more than half of the cards to find the purple dot. The average is $2$ for $3$ cards, $2.5$ for $4$ cards, and $50.5$ for $100$ cards.

For the quantum version, we search for a particular quantum state. For a system with $n$ qubits, we have, as we know, $N = 2^n$ possible states. Suppose we want to find just one state, equivalent to the card with the purple dot. To set up the search mechanism, we label the states $|x⟩$ with the binary number $x$ ranging from $0$ through $2^n − 1$.

We also need to “tag” the “target” state so the search mechanism has something to look for. Let’s assume that there is a function $f(x)$ defined such that $f(x) = 0$ unless $x = w$, where $|w⟩$ is the target state and someone has arranged for $f(w) = 1$. Another way of putting this is that we give each of the basis states the amplitude $\frac{(−1)^{f(x)}}{\sqrt{2^n}}$. So, all the amplitudes have same magnitude. All will be positive except for the amplitude of the target state $|w⟩$, which is negative. That amplitude is the quantum equivalent of the purple dot in our card example.