Quantum algorithms

Grover’s search

Follow an oracle and a reflection as they amplify a marked state.

24 minIntermediate

Intuition

Suppose an oracle identifies a unique marked label among N possible labels. The phase oracle marks by multiplying its amplitude by −1. A computational-basis measurement at that moment still looks uniform.

The diffusion operator reflects the amplitudes about their mean. Together, the oracle and diffusion rotate the state in a two-dimensional plane toward the marked direction. Repeating too many times rotates past it.

Learning objectives

  • Explain the phase oracle
  • Apply inversion about the mean
  • Predict overshoot from excess iterations

Interactive exploration

Use the controls to change the state and see its calculated readout. You can return to this experiment as you work through the derivation.

Sequence

Step 1 / 4
1

Initialize

Prepare every wire in the zero basis state.

BasisAmplitudeProbability
|00⟩1.000100%
|01⟩0.0000%
|10⟩0.0000%
|11⟩0.0000%

Marked-state probability 0%

Mathematical foundation

Let |s⟩ be the uniform superposition and |m⟩ the marked basis vector. The initial angle θ from the unmarked direction has sine 1/√N.

O=I−2∣m⟩⟨m∣,D=2∣s⟩⟨s∣−I,sin⁡θ=1/NO=I-2|m\rangle\langle m|,\qquad D=2|s\rangle\langle s|-I,\qquad \sin\theta=1/\sqrt N

Each DO pair adds 2θ to the initial angle. The success probability after r iterations is the squared marked component. With an efficient oracle, the abstract search uses O(√N) oracle queries for one marked item.

pr=sin⁡2((2r+1)θ)p_r=\sin^2((2r+1)\theta)

Worked example

For four states, all amplitudes begin at 1/2. After the oracle, three are 1/2 and one is −1/2, giving mean 1/4. Diffusion maps the marked amplitude to 1 and the others to zero.

am↦2(1/4)−(−1/2)=1,aj≠m↦2(1/4)−1/2=0a_m\mapsto 2(1/4)-(-1/2)=1,\quad a_{j\ne m}\mapsto 2(1/4)-1/2=0

Guided experiment

Choose two qubits and one iteration. Compare the marked amplitude and probability immediately after the oracle and after diffusion. Try a second iteration.

Go to the controls
Compare with the expected result

One iteration is exact for four labels and one marked item. A second iteration reduces the success probability.

Understanding check

1. Which step first changes basis probabilities after uniform preparation?
2. With one marked item out of four, what is the success probability after one iteration?

Next steps

Want to keep your results? Start your learning journey

Open Algorithm Visualizer