A Special Case

It is instructive to consider the special case of N = 4. In this special case, the precise number of iterations needed to attain the correct measurement with unit certainty is one. Thus it can provide some intuition as to the manner in which Grover's algorithm exploits interference between the states to raise the probability of the the desired state. [Grover00]

In the case of N = 4 then, the entire Grover's algorithm is simply:

1. Qureg = (1, 0, 0, 0)^T (Quantum register in state 00 with probability 1)
2. Apply Walsh-Hadamard transformation to Qureg
3. if (C(Qureg) == 1) Apply Phase Inversion
4. Apply A transformation to Qureg (A is inversion about average)
5. Measure state of Qureg

   Let us trace the evolution of our quantum register through the algorithm. Let us assume the state we are searching for is the state three. We will denote the state of our quantum register like this: (a, b, c, d )^T, where the probability of measuring the register to be in the state 00 is a², the probability of measuring state 01 is b², the probability of measuring state 10 is c², and the probability of measuring state 11 is d². In general, the amplitudes could be complex, but no complex amplitudes are used in Grover's algorithm, so a² = | a|².

   For a 4 state system, the Walsh-Hadamard transformation is represented by the matrix:

   W = $${\frac{{1}}{{2}}}$$$$\left(\vphantom{\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{array}}\right.$$$$\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{array}$$$$\left.\vphantom{\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{array}}\right)$$

   The inversion about average transformation is represented by the matrix:

   A = $${\frac{{1}}{{2}}}$$$$\left(\vphantom{\begin{array}{cccc} -1 & 1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ 1 & 1 & 1 & -1 \end{array}}\right.$$$$\begin{array}{cccc} -1 & 1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ 1 & 1 & 1 & -1 \end{array}$$$$\left.\vphantom{\begin{array}{cccc} -1 & 1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ 1 & 1 & 1 & -1 \end{array}}\right)$$

After step 1 of our algorithm the quantum register is in the state (1, 0, 0, 0)^T.
After step 2 of our algorithm the quantum register is in the state W*(1, 0, 0, 0)^T = (.5,.5,.5,.5)^T
After step 3 of our algorithm the quantum register is in the state (.5,.5, - .5,.5)^T. Remember, the marked element in this example is the third one.
After step 4 of our algorithm the quantum register is in the state A*(.5,.5, - .5,.5)^T = (0, 0, 1, 0)^T.
Now comes step 5, the measurement step, we can see that with unit probability we will measure the state 3, which was the marked state.

Now, this is an exceptional case, in general we will not attain unit probability after any number of iterations. By theorem 2 we can see that there is some number of iterations m that is O($\sqrt{{N}}$) such that the probability of measuring the marked state is at least 1/2. Note that the result for monotonic increasing probability of the marked state proved in theorem 2 only applies so long as the amplitude of the marked state is less than ${\frac{{1}}{{\sqrt{2}}}}$. Once the amplitude is greater than that further applications of A cause it to shrink, it will then oscillate back and fourth as more applications of the inner loop are executed. [BBHT96]