ExperimentsExperiment 7 · Quantum search
Multiple-Solution Grover
1, 2, 4 or 8 marked states — how does the distribution change?
- 1. Learn
- 2. Watch
- 3. Interact
- 4. Predict
- 5. Run
- 6. Observe
- 7. Record
- 8. Answer
- 9. Research
① What is the problem?
What if more than one answer is correct?
② How does a classical computer approach it?
With M solutions among N, a random scan needs about N/(M+1) checks on average.
③ How does the quantum approach differ?
Grover needs ≈ (π/4)√(N/M) iterations — fewer when there are more solutions — and the probability is shared equally among the marked states.
④ What is happening mathematically?
sin θ = √(M/N); P(success after k) = sin²((2k+1)θ). Too many iterations over-rotate and the probability falls.
⑤ What does the simulation show?
Probability distribution over all 64 states and the success curve vs iterations — computed live.
⑥ What did we learn?
You must know (or estimate) M to choose the number of iterations.
⑦ What can you experiment with?
With 8 targets, run 6 iterations. What happened?