✦Grover search and amplitude amplification

Increase the probability of marked outcomes.

1. Core idea

A phase oracle marks target states with a sign flip. The diffusion operator reflects amplitudes about their mean. Together they rotate the state toward the marked subspace. For one marked item among N, roughly π√N/4 iterations are useful; too many iterations can lower success.

2. Mathematical foundation

The notation describes a precise relationship among states, transformations or probabilities. Identify each symbol, check the dimensions of the objects, and distinguish amplitudes from the probabilities produced by a measurement.

3. Worked example

4. Reasoning flow

1. Prepare the equal superposition |s⟩.
2. Apply a phase flip only to the marked state.
3. Reflect amplitudes about their mean.
4. Repeat an appropriate number of times.
5. Measure and verify the marked candidate.

Qiskit implementation

Run this standalone Python script with Qiskit installed. It uses exact statevector simulation rather than noisy hardware shots.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
qc = QuantumCircuit(2)
qc.h([0, 1])       # equal amplitudes over four candidates
qc.cz(0, 1)       # mark |11> by changing its phase
qc.h([0, 1]); qc.x([0, 1])
qc.cz(0, 1)       # reflection about the uniform state (up to global phase)
qc.x([0, 1]); qc.h([0, 1])
print(qc.draw())
print(Statevector.from_instruction(qc).probabilities_dict())
# Expected: {'11': 1.0}

5. Check your understanding

6. What to watch out for

Ideal-state calculations assume perfect gates and measurements. When assessing an algorithm, separate its mathematical guarantee from the cost of building oracles, preparing inputs, repeating experiments and correcting physical noise.