next up previous contents
Next: Searching for More Than Up: Open Questions Previous: Open Questions   Contents

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}}^{}$ = (k0, l0).

From theorem 1 we see the j'th iteration will produce the state $ \Psi_{{j}}^{}$ = (kj, lj), where k0 = l0 = 1/$ \sqrt{{N}}$, further:

kj+1 = $\displaystyle {\frac{{N-2}}{{N}}}$kj + $\displaystyle {\frac{{2(N-1)}}{{N}}}$lj

lj+1 = $\displaystyle {\frac{{N-2}}{{N}}}$lj - $\displaystyle {\frac{{2}}{{N}}}$kj

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 sin2$ \theta$ = 1/N. It can be shown through mathematical induction that:

kj+1 = sin((2j+1)$\displaystyle \theta$)

lj+1 = $\displaystyle {\frac{{1}}{{\sqrt{N-1}}}}$cos((2j + 1)$\displaystyle \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]


next up previous contents
Next: Searching for More Than Up: Open Questions Previous: Open Questions   Contents
Matthew Hayward - Quantum Computing and Grover's Algorithm GitHub Repository