Time Complexity Analysis - Grover

This is going to be a geometric proof to show that the number of Grover iterations we must do to achieve a high probability of measuring the winner state is bounded by $O(\sqrt{N})$.

Equal superposition

We will carry forward what we’ve learned from the past lessons and start with the situation where some arbitrary state $|x\rangle$ could be measured from the superposition, and it lies in between $|w\rangle$ and $|E\rangle$ in the state space. The $|x'\rangle$ state is orthogonal to $|w\rangle$ and the angle between $|x'\rangle$ and $|E\rangle$ is $\Delta$

Reflecting about the $|w\rangle$ state

The state $|x\rangle$ makes an angle $\theta$ with the $|w\rangle$, upon reflection about the $|w\rangle$ state, our new state $|x_1\rangle$ would end up with the same angle but on the opposite side.

Reflecting about the $|E\rangle$ state

If we denote the angle between $|E\rangle$ and $|x\rangle$ as $\phi$ then after this reflection, our new state $|x_2\rangle$ would have an angle of $2\theta+\phi$ with $|E\rangle$. Using all the information we have gathered so far, we need to focus on finding the angle between our final state and the original state.

Take a look at the upper half (first and second quadrants) of the diagram given below, the sum of the angles should be equal to $\pi$ radians.

$$2\phi + 2\theta + 2 \Delta = \pi$$

Let’s have a look at $-|x_2\rangle$ because that’s essentially the same state (ignoring global phase, the $-1$ sign), which is now closer to $|w\rangle$. Remember that this state is simply in the opposite direction. Geometrically, the angle between $|x_2\rangle$ and $-|x_2\rangle$ will be $\pi$ radians.

We already know from our previous step that:

$$\pi = 2\phi + 2\theta + 2 \Delta$$

We need to find the unknown angle between the original state and the final state after one Grover iteration. We can do this by summing up the angles between $|x_2\rangle$ and $-|x_2\rangle$ ...