Time Complexity Analysis - Grover
Let’s learn why Grover's Algorithm runs in O(sqrt(N)) time.
We'll cover the following
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 .
We will carry forward what we’ve learned from the past lessons and start with the situation where some arbitrary state could be measured from the superposition, and it lies in between and in the state space. The state is orthogonal to and the angle between and is