05 / Algorithms · LESSON 12 / 27 · 20 MIN
Grover search and amplitude amplification.
Follow oracle marking and reflection about the mean.
Uniform → mark |11⟩ phase → diffusion → |11⟩
Mark without measuring
For four candidates, H on both qubits creates amplitudes [1/2,1/2,1/2,1/2]. A phase oracle for 11 negates only its amplitude, yielding [1/2,1/2,1/2,−1/2]. The probability bars have not changed yet.
Reflect about the mean
The diffuser D=2|s⟩⟨s|−I transforms each amplitude a into 2ā−a, where ā is their arithmetic mean. After marking 11 the mean is 1/4, so unmarked amplitudes become 0 and the marked amplitude becomes 1.
Do not over-rotate
For one marked item among N, the query count is about (π/4)√N. Excess iterations rotate away from the target again. Oracle construction and fault-tolerant costs are separate from this ideal query count.
CHECK YOUR UNDERSTANDING
Lesson quiz
Answer all 2 questions correctly. Unlimited retries.
0/2 answered
Checking your account…
