How Many Iterations are Required

Our initial state $\Psi_{{0}}^{}$ = (1/$\sqrt{{N}}$, 1/$\sqrt{{N}}$,..., 1/$\sqrt{{N}}$), is attained by performing the Walsh-Hadamard transformation on the register in the zero state.

Let (k, l ) denote denote the state of our vector, where k is the amplitude of the marked state, and l is the amplitude of each of the remaining (N - 1) states. It is the case in Grover's algorithm that the unmarked states always have the same amplitude, so we can use this shorthand.

After the first application of the Walsh-Hadamard operator to place us in an equal superposition of states let us say we are in state $\Psi_{{0}}^{}$ = (k₀, l₀).

From theorem 1 we see the j'th iteration will produce the state $\Psi_{{j}}^{}$ = (k_j, l_j), where k₀ = l₀ = 1/$\sqrt{{N}}$, further:

k_j+1 = $${\frac{{N-2}}{{N}}}$$k_j + $${\frac{{2(N-1)}}{{N}}}$$l_j

l_j+1 = $${\frac{{N-2}}{{N}}}$$l_j - $${\frac{{2}}{{N}}}$$k_j

With a little work on the recurrence relation we an solve for closed form solutions of k and j. Let the angle $\theta$ be defined so that sin²$\theta$ = 1/N. It can be shown through mathematical induction that:

k_j+1 = sin((2j+1)$$\theta$$)

l_j+1 = $${\frac{{1}}{{\sqrt{N-1}}}}$$cos((2j + 1)$$\theta$$)

[BBHT96]

We are interested in the number of iterations for k to have near unit probability. Evidently, we will find the register to be in the target state with unit probability when (2m + 1)$\theta$ = $\pi$/2, or when m = ($\pi$ -2$\theta$)/4$\theta$. We can only perform an integer number of iterations, but the probability of failure is less than 1/N if we iterate $\lfloor$$\pi$/4$\theta$$\rfloor$ times, which is very close to ${\frac{{\pi}}{{4}}}$$\sqrt{{N}}$ when N is large ( 1/$\sqrt{{N}}$ = sin$\theta$ $\approx$ $\theta$). [BBHT96] For the 50 percent probability called for by Grover's algorithm we need only ${\frac{{\pi}}{{8}}}$$\sqrt{{N}}$ iterations. [BBHT96]