Grover’s Search Algorithm

Search by rotating probability toward a target

Grover’s algorithm searches a set of N labels using a predicate that recognises good labels. It alternates two reflections. One changes the sign of good amplitudes; the other reflects about the prepared uniform state. Together they rotate the state toward the good subspace. A measurement at a planned stopping point yields a candidate, which should then be checked.

Review the four-item interference example and oracle access. The basic arithmetic uses signed real amplitudes. The geometric description explains why more iterations eventually reduce success rather than improving it indefinitely.

WORKED DIAGRAM · A06Eight labels and one marked item

After marking one of eight labels, diffusion gives amplitude 5a/2 on that label and a/2 on each of the other seven. The probabilities are 25/32 and seven copies of 1/32.

The search contract

The predicate marks M of N basis labels, with zero less than M less than N in the basic analysis. Coherent access is provided by a phase oracle that negates marked components. The output is one marked label, not a list of every solution. Verification evaluates the predicate on the measured candidate.

For one unknown marked item, the quantum query count grows as the square root of N for bounded success probability. Classical unstructured search has linear query growth. This is a quadratic black-box advantage. If an application has exploitable structure, compare with the best classical use of that structure rather than assuming exhaustive search is automatically the right baseline.

Procedure

Prepare the uniform state over all labels. Apply the phase oracle. Apply diffusion, the reflection about the uniform state. Repeat that pair a chosen number of times, then measure and verify. Diffusion on a vector with mean amplitude m maps each entry a to twice m minus a.

When N is a power of two, H on every input qubit prepares the uniform state. The diffusion reflection can be constructed by combining that preparation, a phase reflection about zero and its inverse. Its global sign convention can vary without changing the isolated search probabilities. Keep conventions consistent when embedding the iterate in controlled estimation circuits.

For a worked diagram, use three amplitude panels: all entries positive, one entry negative, then a larger marked entry after diffusion. A separate circular arrow can indicate the two-dimensional rotation and the need to stop near its peak.

Worked example: eight labels, one marked

Initially every amplitude is a equal to one over the square root of eight. After the oracle, seven entries are a and one is negative a. The mean is six a divided by eight, or three a over four. Diffusion maps an unmarked entry to a over two and the marked entry to five a over two.

The marked probability is therefore 25 divided by 32, or 78.125 percent. Each unmarked probability is one divided by 32, and the total probability remains one. This verifies the whole distribution rather than only noticing that the target bar increased.

After two iterations, the marked probability is 121 divided by 128, about 94.53 percent. After three it falls substantially. No observation was made between iterations; the state evolves coherently. A procedure that measures after each oracle and then continues on the collapsed basis state is not Grover’s algorithm.

Why two reflections produce amplification

Let the good direction be the uniform superposition over marked labels, and the bad direction the uniform superposition over unmarked labels. The initial state lies in the plane spanned by those directions. Its good amplitude is the square root of M over N. Define theta by sine theta equal to that quantity.

The phase oracle reflects one direction, and diffusion reflects about the initial vector. Their composition rotates the state by twice theta. After k iterations the good probability is

$$P_{\rm good}(k)=\sin^2((2k+1)\theta),\qquad \sin^2\theta=\frac MN.$$

This formula is a correctness statement for the ideal symmetric setting. Choose an integer k near the first peak. For a small marked fraction, the scale is approximately pi over four times the square root of N over M. Exact stopping depends on the fraction and integer rounding. Unknown M requires a suitable search or estimation strategy rather than a guessed fixed schedule.

Special and boundary cases

Four labels with one marked have theta equal to pi over six, so one iteration reaches the peak exactly. That convenient teaching example is exceptional. Eight labels do not reach certainty at the same iteration count. If no labels are marked, verification never succeeds and the basic nonzero-M analysis does not provide a stopping certificate. If every label is marked, ordinary measurement already succeeds.

Multiple marked items are amplified together. The final measurement returns one of them according to the resulting state, rather than printing all M items. If the application needs many distinct solutions, it must account for additional runs, duplicate handling and the output size. Search and enumeration are different tasks.

Practical costs and limitations

One oracle call may contain a large reversible computation, workspace and uncomputation. Diffusion also has synthesis costs, especially in large registers. Hardware analysis must include native gate counts, connectivity, precision and error correction. A browser simulation stores amplitudes classically and cannot demonstrate a quantum hardware runtime advantage by its own timing.

For an experiment, predict the full eight-entry vector after one iteration, then compare the simulator table. Change only the iteration count and make another prediction. Separately vary shots to observe sampling uncertainty around the fixed ideal probabilities. Keep iteration effects and finite-shot fluctuations conceptually distinct.

Exercises

1. For four labels and one marked item, calculate the mean amplitude after marking and each amplitude after diffusion.

2. A designer doubles the number of Grover iterations whenever the marked histogram bar rises. Explain why that is not a reliable stopping rule, even before hardware noise is considered.

Worked answers

1. The amplitudes are three positive halves and one negative half, so the mean is one quarter. Unmarked entries become zero; the marked entry becomes one. The final measurement succeeds with certainty in this ideal four-item case.

2. Success oscillates with iteration count. More iterations can pass the first peak and reduce the probability. Observing histograms also requires separate circuit runs and finite shots. A stopping strategy must use the known or estimated marked fraction and a planned success analysis, not an assumption of monotonic improvement.

Source

Grover’s original paper introduces the search advantage. The exact rotation and generalised preparation framework are developed further in amplitude amplification and estimation.

Predict and test

Choose three input qubits and one Grover iteration to test the eight-item calculation. Predict the marked probability and every unmarked probability before revealing. Compare later iterations to see why amplification needs a stopping rule.

L06 · INTERACTIVE LABRuns on your device

Grover search explorer

A phase oracle marks one item; diffusion reflects amplitudes about their mean. Amplification can overshoot. Oracle construction and hardware costs are excluded.

Experiment controls

Grover iterations1Random seed

Predict the marked item’s success probability at this register size and iteration count. Explain an expected increase or decrease.

Your prediction

Reveal exact resultsRun measurements →Reset

Record a prediction to enable the results.

Results are hidden.

Prepare your experiment using the controls. Record a prediction, then reveal the statevector or run the experiment.

Changing the preparation or circuit starts a new prediction.

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

Take it further

For four items, trace all amplitudes through one iteration. For eight, compare iterations 0–6 and explain the oscillation.

Initial setup · reference state

Exact probability

|00⟩

0.0%

|01⟩

0.0%

|10⟩

0.0%

|11⟩

100.0%

Marked item probability 100.0%

Statevector before readout · ideal simulation

Basis	Amplitude a + bi	Magnitude	Phase (rad)	Probability
|00⟩	0 + 0i	0.000000	undefined	0.0%
|01⟩	0 + 0i	0.000000	undefined	0.0%
|10⟩	0 + 0i	0.000000	undefined	0.0%
|11⟩	1 + 0i	1.000000	0.000000	100.0%

Signs and complex phases are part of the state. Phase is undefined for a zero amplitude. A shared global phase changes no probabilities; relative phases can affect a later operation. Values are rounded to six decimal places.

Prediction to try: Predict the marked item’s success probability at this register size and iteration count. Explain an expected increase or decrease.

Challenge: For four items, trace all amplitudes through one iteration. For eight, compare iterations 0–6 and explain the oscillation.

Open the live experiment studio

Trace the circuit or amplitudes

WORKED DIAGRAM · F25One complete four-item Grover iteration

Real amplitudes begin at 1/2. The oracle negates the marked component. Reflection about the new mean, 1/4, leaves amplitude 1 on 11 and 0 elsewhere. Negative amplitudes are not negative probabilities.

Check your understanding

PAUSE & THINK

What is the marked probability after one ideal Grover iteration among eight labels?

Choose your answer

1/825/321

Check my answer

Answer: 25/32. The marked amplitude becomes (5/2)/√8, whose squared magnitude is 25/32. The exact-one-iteration result applies to the special four-item case.