Academy K

Grover's Diffusion Operator

InterviewDerivationGrover's algorithmamplitude amplification

Related module: Search and amplitude amplification

Problem statement

In Grover's search, the diffusion operator is D=2∣s⟩⟨s∣−ID = 2|s\rangle\langle s| - I where ∣s⟩=1N∑x=0N−1∣x⟩|s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle is the uniform superposition.

  1. Show that DD reflects amplitudes about their mean.
  2. If before diffusion the marked state has amplitude ama_m and unmarked states have amplitude aua_u, what are the amplitudes after one application of DD?

Hints

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.