How quantum algorithms use interference

A complete four-item example

Prepare the uniform state with amplitudes $(1/2,1/2,1/2,1/2)$. Suppose item 11 is marked. Its phase oracle produces $(1/2,1/2,1/2,-1/2)$.

The mean amplitude is now $1/4$. Diffusion reflects each amplitude a about the mean: $a\mapsto2(1/4)-a$. The first three become 0 and the marked amplitude becomes 1. One ideal iteration therefore finds 11 with certainty in this special four-item case.

L06 · INTERACTIVE LABRuns on your device

Grover search explorer

An oracle flips the marked amplitude. Diffusion reflects amplitudes about their mean. Repetition first increases and then decreases the chance of success.

Make a prediction first

There are four possible items and one marked item. How many Grover iterations will you need?

Experiment controls

Grover iterations1

One marked item. One oracle query per iteration. Oracle construction cost is excluded.

Random seed

Run measurements →Reset

Exact probability

|00⟩

0.0%

|01⟩

0.0%

|10⟩

0.0%

|11⟩

100.0%

Marked item probability 100.0%

Exact ideal-model predictions · run a measurement experiment to compare.

MODEL · Ideal pure-state vector, complex double precisionORDER · q0 is the leftmost bit

Take it further

Choose 3 qubits. Increase the iterations past the best point and explain why the success probability falls.

Prediction: There are four possible items and one marked item. How many Grover iterations will you need? Challenge: Choose 3 qubits. Increase the iterations past the best point and explain why the success probability falls.

The general pattern

For one marked item among N, let $\sin\theta=1/\sqrt N$. After k Grover iterations, success probability is

$$\sin^2((2k+1)\theta).$$

This oscillates. Increasing k forever does not improve the result. A useful iteration count is near $\pi\sqrt N/4$, with rounding and marked-set assumptions handled carefully.

What the lab verifies

The model uses one marked basis state, exact phase marking and exact diffusion. It counts one oracle query per iteration but excludes the cost of constructing that oracle, preparing application data and executing fault-tolerant gates.

A classical simulator calculates all these amplitudes explicitly. Its wall-clock time is not a measurement of a quantum device’s runtime.

Challenge: for eight items, calculate the probabilities at k = 0, 1, 2 and 3. Compare them with the bars, then explain the drop after the best point using the angle formula.

Reference: IBM Quantum — Fundamentals of quantum algorithms.