Simulating a 2-Qubit Grover Search

Run one Grover iteration on a two-qubit register to amplify a marked state and reach it with certainty.

Problem

Grover's algorithm searches an unstructured space of N items in about sqrt(N) queries versus N classically. For two qubits N=4, and a single Grover iteration takes the amplitude of the marked state to 1, so one query finds it with certainty, the special case where the geometry aligns perfectly.

Oracle and diffusion

Start in the equal superposition. The oracle flips the sign of the marked amplitude; the diffusion operator reflects all amplitudes about their mean. Together they rotate the state vector toward the marked state in the 2D plane spanned by marked and unmarked components.

import numpy as np
psi=np.ones(4)/2            # equal superposition
mark=2                      # marked index |10>
# oracle: flip sign of marked amplitude
psi[mark]*=-1
# diffusion: reflect about the mean
m=psi.mean(); psi=2*m-psi
print(np.round(psi,3))      # amplitude 1 on marked, 0 elsewhere
print('prob marked',round(psi[mark]**2,3))

Result

After one oracle-plus-diffusion cycle the amplitude concentrates entirely on the marked index, so measurement returns it with probability 1. The mechanism is a rotation by an angle set by the initial overlap; for N=4 that angle is exactly enough to land on the target in one step. For larger N the optimal iteration count is about (pi/4) sqrt(N), and overshooting rotates past the target.

• Grover gives a quadratic, not exponential, speedup, and it is provably optimal for unstructured search.
• Iterating too many times reduces success probability because the rotation continues past the target.
• Amplitude amplification, Grover's generalization, appears in quantum subroutines Kronos tracks for future materials search problems.