Some say that there are just two quantum algorithms today: Grover’s and Shor’s. While Shor’s gets all the headlines, Grover’s stands out because of its elegant simplicity. See a beautiful video explaining its operation here, created by 3Blue1Brown.
By way of history, Lov Grover published his search algorithm in 1996, and it remains one of the foundational results in quantum computing. The problem it solves is simple: given an unsorted collection of items and a way to check whether any given item is the one you want, find the correct item. A classical computer must check items one at a time. Grover’s algorithm finds the answer using roughly the square root of the attempts a classical approach would need.
Think of searching for a specific card in a shuffled deck. A classical computer needs, on average, 26 checks for a 52-card deck. Grover’s algorithm finds the same card in about 7 checks, roughly the square root of 52.
The algorithm begins by creating a superposition that assigns equal amplitude to every possible answer. It then repeatedly applies two operations. First, an oracle marks the correct answer by flipping its quantum phase, turning its amplitude negative while leaving all other amplitudes unchanged. Second, a diffusion operator compares every amplitude to the overall average and reflects them around it. Because the correct answer’s amplitude was flipped negative, this reflection pushes it sharply upward while suppressing the incorrect answers. This is quantum interference in action: the mathematical structure of waves causes wrong answers to cancel out while the right answer reinforces with each iteration.
After about seven iterations for our 52-card example, the correct answer’s amplitude dominates, and a measurement will return it with high probability. If the problem has multiple correct answers, the algorithm still works and actually converges faster, since more marked states means more amplitude to reinforce.
Two important limitations apply. The square root speedup is provably the best possible for unstructured search, making it a polynomial rather than exponential advantage. And the algorithm requires an oracle that can recognize correct answers, meaning you must be able to verify a solution even if you cannot find one directly.
While running Grover’s algorithm on large problems requires more capable quantum hardware than exists today, its underlying technique of amplitude amplification has become a building block inside many other quantum algorithms, from optimization to cryptography.
Subscribe on Substack at qubitguy.substack.com
Looking for a more detailed description? Find it at quera.com/glossary