2.5

# Grover's Algorithm

The most general quantum algorithm is Lov Grover’s search algorithm. Using entanglement and interference, it allows us to answer the question, “For what value of $x$ does $f(x) = k$, for some number $k$?”

Randomized database search problems can be rephrased to the above question. These unstructured problems are considered to be difficult to solve efficiently.

As a simple example, think about searching for a single ace card from four reversed cards (one ace and three other cards). If we do this classically, in the worst case we might have to try four times before finding the ace, and the average number is 2.5 times. If we use a quantum computer with two qubits and Grover’s search algorithm, we can find the ace using our check operation only one time. Without going into the details, we show a simple example as follows:

In the first step, we set up a superposition of all four states. Second, we flip the amplitude (change the phase by $\pi$) of only one state, corresponding to the ace’s location. (It’s important to note here that we can construct gate sets for such operation even if we do not know the correct location of the ace, otherwise the algorithm would just be confirming what we already know!) Third, we invert amplitude of all of the states about the average of the set. As shown in the above figure, during this operation, the amplitudea of a non-ace location (blue bar) becomes zero and the amplitude of the ace location (orange bar) becomes one. After these steps, we measure the two qubits and learn the position of the ace with probability one. In this case, the measurement result becomes $\vert 10 \rangle$ which corresponds to the third card.

Practical application of Grover’s algorithm to solving the traveling salesman problem (TSP) is known. TSP asks us to find the shortest possible route that visits all $k$ cities exactly once and returns to the starting city. We preset the state of our quantum register to a superposition of all of the possible permutations of routes. We can also apply this search procedure to find the best move for chess, shogi, or go. Preset our state to a superposition of all legal sequences of moves, and flip the phase of any position in which we win. The computational complexity of Grover’s algorithm grows more slowly than brute force classical algorithms that simply try every possibility.

As a general case using a classical computer, with $N$ cards and searching for one ace, the worst case is that we have to check all $N$ possibilities, and the average number we will check is approximately $N/2$. Using a quantum computer with $\log{N}$ qubits running Grover’s search algorithm, we can find the ace location with only $O(\sqrt{N})$ executions of a routine that checks whether we have found the ace: First, we prepare the superposition of all $N$ states. Next, we flip the phase of the state corresponding to the ace’s location. After that, we invert all amplitudes about the average. We iterate these flip and invert operations $O(\sqrt{N})$ times. After completing the iterations, we measure all qubits and discover the ace’s location with high probability. All of this happens because of the constructive inteference that causes the amplitude of our answer to grow and the destructive intference that causes the incorrect possibilities to shrink.

It is hard to construct efficient algorithms for problems without structure, such as this search through a randomly shuffled set of cards. Considering only the asymptotic computational complexity, Grover’s search algorithm achieves a square root speed up compared to classical algorithms. This is true for all computations, so the worst case improvement for any algorithm using a quantum computer should be a square root speedup. Not bad, but not the exponential speedup we might naively think.

However, whether this results in a useful speedup depends on the problem type and size. Classical algorithms for some problems, such as examining chess positions, require exponentially more computation for each additional step you try to look ahead, so the corresponding execution of Grover’s algorithm will still require exponential amounts of computation. It can be said that this fact suggests that quantum computer cannot solve all problems with a usefully dramatic speedup.