Grover's Algorithm

Assume you have a system with N = 2ⁿ states labeled S₁, S₂,...S_N. These 2ⁿ states are represented by n bit strings. Assume there is a unique marked element S_m that satisfies a condition C(S_m) = 1, and for all other states C(S) = 0. We assume that C can be evaluated in unit time. Our task is to devise an algorithm which minimizes the number of evaluations of C.

The idea of Grover's algorithm is to place our register in a equal superposition of all states, and then selectively invert the phase of the marked state, and then perform an inversion about average operation a number of times. The selective inversion of the marked state follows by the inversion about average steps have the effect of increasing the amplitude of the marked state by O(1/$\sqrt{{N}}$). Therefore after O($\sqrt{{N}}$) operations the probability of measuring the marked state approaches 1. [Grover96]

Grover's algorithm is as follows:

1. Prepare a quantum register to be normalized and uniquely in the first state. Then place the register in an equal superposition of all states $\left(\vphantom{\frac{1}{\sqrt{N}}, \frac{1}{\sqrt{N}} \ldots \frac{1}{\sqrt{N}}}\right.$${\frac{{1}}{{\sqrt{N}}}}$,${\frac{{1}}{{\sqrt{N}}}}$...${\frac{{1}}{{\sqrt{N}}}}$$\left.\vphantom{\frac{1}{\sqrt{N}}, \frac{1}{\sqrt{N}} \ldots \frac{1}{\sqrt{N}}}\right)$ by applying the Walsh-Hadamard operator $\hat{{W}}$. This means simply the state vector will be in an equal superposition of each state.

2. Repeat O($\sqrt{{N}}$) times the following two steps (the precise number of iterations is important, and discussed below):
   1. Let the system be in any state S. If C(S) = 1, rotate the phase by $\pi$ radians, else leave system unaltered. It is worth noting that this operation has no classical analog. We do not observe the state of the quantum register, doing so would collapse the superposition. The selective phase rotation gate would be a quantum mechanical operator which would rotate only the amplitude proportional to the marked state within the superposition.

   2. Apply the inversion about average operator $\hat{{A}}$, whose matrix representation is: A_ij = 2/N if i $\not=$j and A_ii = - 1 + 2/N to the quantum register.

3. Measure the quantum register. The measurement will yield the n bit label of the marked state C(S_M) = 1 with probability at least 1/2.

[Grover96]