Grover's Algorithm: Unstructured Database Search

Introduction

Grover's algorithm, designed by Lov Grover in 1996, is a quantum algorithm that solves the problem of searching an unstructured database or solving an inverted function with $N$ entries in $\mathcal{O}(\sqrt{N})$ steps.

The Speedup

• Classical: Searching an unsorted database of size $N$ requires checking entries one by one, resulting in a linear time complexity of $\mathcal{O}(N)$ on average.
• Quantum: Grover's algorithm solves this in $\mathcal{O}(\sqrt{N})$ evaluations, representing a quadratic speedup.

Core Steps

Grover's algorithm does not look at all entries at once, but rather amplifies the probability amplitude of the correct state through iterative geometry:

1. State Initialization: Prepare an equal superposition of all database indices.
2. Grover Iteration (repeated $\approx \frac{\pi}{4}\sqrt{N}$ times):
   • Oracle: Flips the phase of the target state ($|w\rangle \to -|w\rangle$).
   • Diffusion Operator (Inversion about the mean): Reflects all amplitudes about the average amplitude, amplifying the target and dampening the others.
3. Measurement: Measures the register, yielding the target index with near-100% probability.