Grover's Algorithm

Grover's algorithm, published by Lov Grover in 1996, provides a quadratic speedup for unstructured search problems. Classically, finding a specific item in an unsorted database of N items requires checking O(N) items on average. Grover's algorithm accomplishes this in O(√N) quantum queries by using quantum amplitude amplification — iteratively boosting the probability amplitude of the target state while suppressing all others.

The algorithm initializes all qubits in a uniform superposition (using Hadamard gates), then repeatedly applies two operations: an oracle that marks the target item by flipping its phase, and a diffusion operator that amplifies the marked item's amplitude. After approximately π/4 × √N iterations, measuring the qubits yields the target item with high probability. This process is optimal — Grover's lower bound proves no quantum algorithm can search an unstructured database faster.

While a quadratic speedup is less dramatic than the exponential speedup of Shor's algorithm, Grover's algorithm has broad applicability because many computational problems reduce to search. Applications include database search, SAT solving, optimization, and cryptographic key search (where it effectively halves the security level of symmetric ciphers — AES-256 provides 128-bit security against quantum attack). However, the practical impact of Grover's algorithm is limited by the need for a coherent quantum computation over √N steps, which for large databases requires a fault-tolerant quantum computer with substantial circuit depth.