Grover Search with Multiple Targets
How Grover's algorithm behaves when several items are marked, and how to tune iterations when the count is unknown.
Multiple marked items
Basic Grover search assumes a single marked item among N. When M items are marked, the algorithm still works, but the geometry changes. The uniform superposition decomposes into a marked component (equal superposition of the M solutions) and an unmarked component. Grover's operator rotates between them by angle 2*theta per step, where now sin(theta) = sqrt(M/N).
Optimal iteration count
The success probability is sin^2((2k+1)theta) after k iterations. It is maximized when (2k+1)theta is near pi/2, giving the optimal number of iterations k_opt approximately (pi/4) sqrt(N/M) - 1/2. With M solutions instead of one, the optimal iteration count shrinks by a factor of sqrt(M): more targets means fewer steps to a high-probability hit.
Behavior notes
- Overshooting: running past k_opt rotates amplitude back away from the solutions, lowering success probability.
- When M is a large fraction of N, very few iterations (sometimes zero) are needed.
- Measuring after k_opt iterations returns one of the M solutions, chosen roughly uniformly.
Unknown number of solutions
If M is unknown, k_opt cannot be set directly. Two remedies exist. First, estimate M with approximate counting, then set k_opt. Second, use an exponential search schedule: try increasing guesses for the number of iterations (drawn randomly up to a growing bound), which finds a solution in O(sqrt(N/M)) queries even without knowing M. This schedule avoids the overshoot problem by randomizing the iteration count.
Robustness
When the exact number of iterations that lands on pi/2 is not an integer, the peak success probability is slightly below one. Fixed-point Grover methods remove the overshoot risk entirely by monotonically converging to the target, at the cost of some query efficiency. The general operator behind all these variants is amplitude amplification.