Amplitude Amplification Approach

A general feature of the Grover algorithm used in many other quantum algorithms is the notion of “amplitude amplification.” The process increases (amplifies) the amplitude associated with the target state $|w⟩$ while simultaneously decreasing the magnitude of the other states’ amplitudes. It’s like playing with a pair of dice where one is “loaded” to roll a “$1$,” increasing the odds of rolling snake eyes. Geometrically, this is equivalent to getting the superposition state pointing along $|w⟩$.

To see where the $\sqrt{N}$ number of steps comes in, note that the average amplitude for the state $|ψ_{other}⟩$ is about $1/ \sqrt{N}$. For each step, the amplitude for the target state $|w⟩$ increases by about $1/ \sqrt{N}$ (for large $N$). Thus, after $\sqrt{N}$ steps, the amplitude is about equal to $1$ for $|w⟩$ and close to $0$ for all the other states.