Grover in depth: oracle and diffusion

Take apart the two pieces of Grover’s algorithm: the oracle that marks the answer and the diffusion that amplifies it. Change the oracle and find a different answer.

Two steps: mark and amplify

Grover’s algorithm does two things in each round. The oracle flips the phase of the marked state (makes its amplitude negative); the probabilities don’t change and the mark is invisible. The diffusion step then reflects all amplitudes about their average: the negative amplitude shoots far above the average and the others shrink.

This “inversion about the average” is a calculated use of interference. Each round makes the right answer’s amplitude a little larger.

Changing the oracle

On two qubits the CZ gate flips the sign of the state 11 only. To mark another state we put X gates on both sides of the CZ: apply X to q0 and undo it after the CZ, and the state with q0 = 0 is flipped to 1, marked and flipped back. This marks 10.

The diffusion part (H, X, CZ, X, H) does not depend on which answer we are looking for. To adapt the algorithm to a new question, changing the oracle is enough.

How many rounds?

With N options the best result comes after about (π/4)·√N rounds. With four options that is one round and the result is 100%. More rounds spoil the result: the amplitude overshoots and shrinks again. Choosing the right number of rounds matters in Grover.

Try it yourself

In the “find 10” example (Grover: 10’u bul) remove the CZ in the oracle (the fourth gate): nothing is marked and all four results stay at 25%. Diffusion alone can’t find anything.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

The oracle flips the phase of the marked state; the probabilities don’t change.
Diffusion amplifies the marked state by reflecting amplitudes about the average.
To search for another answer only the oracle changes.
With N options about (π/4)·√N rounds are needed; more spoils the result.

Test yourself

What do you see if you apply only Grover’s oracle and measure?

The marked answer at 100%
All results equally likely
No result at all

Show the answer

All results equally likely. The oracle only flips a phase; without diffusion the probabilities don’t change, so all results stay equal.

← Bernstein–Vazirani: find the hidden string in one go · The quantum Fourier transform: catching the period →