Grover's Algorithm

Grover's Algorithm

Grover's algorithm is the canonical quantum search routine: given black-box (oracle) access to a function f that marks a single target item x' out of N unsorted possibilities, it finds x' using only O(sqrt(N)) oracle queries, a quadratic speedup over the O(N) queries any classical search would require. This Cirq example builds the full circuit for the two-bit case, where a single application of the Grover operator suffices to identify the marked basis state with high probability. It constructs an oracle that flips the phase of the secret bit string, sandwiches it between Hadamard layers and a diffusion (inversion-about-the-mean) operator that amplifies the marked amplitude, and then measures the input register to recover the hidden string. The script prints the secret sequence, the resulting circuit diagram, the sampled measurement counts, and confirms that the most frequently observed bit string matches the planted target. Beyond search, the amplitude-amplification primitive at the heart of Grover's algorithm underpins many other quantum speedups, making this a foundational example for understanding how interference is engineered to concentrate probability onto a desired answer.

Run it

pip install -r requirements.txt
python grover.py

Source and license

Imported from examples/grover.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.