Time Complexity Analysis - Grover

Let’s learn why Grover's Algorithm runs in O(sqrt(N)) time.

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(N)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|x\rangle could be measured from the superposition, and it lies in between w|w\rangle and E|E\rangle in the state space. The x|x'\rangle state is orthogonal to w|w\rangle and the angle between x|x'\rangle and E|E\rangle is Δ\Delta

Get hands-on with 1200+ tech skills courses.