# Diffusion and Performance

Our second major building block in Grover’s algorithm is the
*diffusion operator*, which implements the “inversion about the mean”
operation. The algorithm gives us a polynomial speedup on a broad
array of problems.

## Inverting About the Mean

After the marking operation discussed in the last Step, we invert the
amplitude of all of the states about the mean (average) of the set.
In this figure, on the left, we show two isolated examples. Accept
for the moment that the average over all of the elements of the
superposition is at the dashed line. In diffusion, the blue (upper)
one moves *toward* the center of the dial when it inverts about the
mean – that is, its amplitude shrinks. The orange (lower) one is the
same amplitude (length) as the blue one, but because its phase puts it
pointing downward, it sits below and farther from the average, so when
it flips about the mean, it winds up moving *away* from the center of
the dial – that is, its amplitude grows. (Its phase also flips, so
that it’s pointed up.)

The diffusion operator is effective because of the phase of the states. In the figure below, the first step is the mark operator. The solution to our problem is the one with the phase opposite the others (orange in the figure). The possibilities that aren’t marked (the blue bars) all point up. As shown in the third column of dials, this results in an average of the bars as shown, close to the tip of the blue bars.

For our four-possibility chess example, let’s see what happens when we run the mark-diffuse sequence once. The amplitude of a losing move sequence (each blue bar in the figure below) becomes zero and the amplitude of the winning move sequence (orange bar) becomes one.

After these steps, we measure the two qubits and learn which one of
the move sequences had been marked, with probability one. In this
case, the measurement result becomes \(\vert 10 \rangle\) which
corresponds to the third move sequence. Recall that our marking
function \(f(x)\) identifies solutions to the problem, but it does
*not* a priori know what value or values of the input \(x\) will be
flipped; all of them are done at the same time, in superposition.

All of this happens because of the constructive interference that causes the amplitude of our answer to grow and the destructive interference that causes the incorrect possibilities to shrink.

## Performance

In our four-possibility chess example, as it happens, only one iteration of our mark-diffuse sequence is needed to raise the amplitude of the answer to one. For larger problems, the average is very close to the unmarked states. Therefore, the first few iterations don’t have much of an effect, but eventually the growth of the orange vector starts to pick up speed until it accumulates half or more of the total wave function, at which point it’s time to stop and measure it. (The exact number of iterations that it takes depends on the number of marked states versus the number of unmarked states, but a variant of Grover’s algorithm allows you to estimate that ratio, as well.)

As a general case using a classical computer, with \(N\) possibilities and only one answer, 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 value of \(x\) we are looking for with only \(O(\sqrt{N})\) executions of the mark-diffuse routine.

## Applications

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 of the cities in a list 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.

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.

Moreover, both chess and TSP have known *heuristics* that provide
pretty good, if not perfect, solutions. Better candidates for
Grover’s algorithm are those with no known structure, where our best
order for testing possibilities classically would be no better than
random.

It is hard to construct efficient algorithms for problems without
structure, such as searching 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.

© Keio University