Intermediate10 min read
Grover's Search: Quantum Speedup
Find a marked item in an unsorted database quadratically faster than any classical algorithm.
The Speedup
| Items | Classical | Grover |
|---|---|---|
| 4 | ~2 | 1 |
| 1,000 | ~500 | 32 |
| 1,000,000 | ~500,000 | 1,000 |
The Code
grover.ql
# Grover's Algorithm - Search for |11⟩QUBIT q0, q1c0 = 0c1 = 0 # SuperpositionH(q0)H(q1) # Oracle (marks |11⟩)CZ(q0, q1) # Diffusion operatorH(q0)H(q1)X(q0)X(q1)CZ(q0, q1)X(q0)X(q1)H(q0)H(q1) # MeasureMEASURE q0 -> c0MEASURE q1 -> c1How It Works
1. Superposition
Hadamard gates create equal superposition of all 4 states (00, 01, 10, 11) - each with 25% probability.
2. Oracle
The CZ gate "marks" the target state |11⟩ by flipping its phase. This is invisible but crucial.
3. Diffusion
The diffusion operator amplifies the marked state while suppressing others. After one iteration, |11⟩ has 100% probability!
Key Insight
Grover's algorithm achieves quadratic speedup: O(√N) vs O(N). For a database of 1 million items, that's 1,000 quantum operations vs 500,000 classical checks.
Try It Yourself
python qubitlang_cli.py run grover.ql --shots 1024Request Files