Unstructured search by amplitude amplification. Optimal iteration count is round(π/4 · √(N/M) − 1/2).
For N = 2ⁿ items and M marked states, Grover rotates the state in the plane spanned by the uniform superposition and the marked subspace. Each iteration is a phase oracle followed by inversion about the mean (diffusion).
Default: n = 3 so N = 8, one marked item |101⟩, two iterations. Success probability is sin²((2k+1)θ) with θ = arcsin(√(M/N)), here about 94.5%. Extra iterations rotate past the target and the probability falls.
How it works
-
1
Uniform start
H (0,1,2) prepares |s⟩ = 2⁻ⁿ/² Σ|x⟩.
-
2
Oracle
X on zero-bits of the target, multi-controlled Z, then uncompute X. |101⟩ picks up a −1 phase. For |101⟩ that is X on q1 only.
-
3
Diffuse
H, X on all, CZ on all, X, H. This reflects about |s⟩.
-
4
Repeat
LOOP 2 wraps oracle + diffusion. k = round(π/4 · √8 − 1/2) = 2.
H (0,1,2)
LOOP 2 {
X 1
CZ [0,1,2]
X 1
H (0,1,2)
X (0,1,2)
CZ [0,1,2]
X (0,1,2)
H (0,1,2)
}
Function form: Grover(0b101)
State. Amplitude concentrated on |101⟩
P(|101⟩) ≈ 0.945 after two iterations. The other seven basis states share ≈ 0.055.
| Basis | Amplitude | Probability |
|---|---|---|
|101⟩ |
≈ 0.972 |
|
other 7 |
small |
Notes
- Marking alone does not change Z probabilities. Diffusion is what amplifies.
- Multiple targets: pass a list, e.g. Grover((0b101, 0b111)). Iteration count uses √(N/M).
Change parameters
The write-up above is for the default circuit. Use this control to generate other variants and load them in the simulator.