Running Grover Search on Three Qubits

Search an 8-item unstructured database in a single Grover iteration, amplifying the marked state from 1/8 to near-certainty.

The problem

Grover's algorithm finds a marked item among N=2^n with about (pi/4)*sqrt(N) queries instead of N/2 classically. With n=3, N=8, and the optimal count is round((pi/4)*sqrt(8)) = 2 iterations. We walk one iteration to show the mechanics, then note the second.

Step 1 - uniform superposition

Apply H to all three qubits from |000>. Every basis state has amplitude 1/sqrt(8), so each is measured with probability 1/8.

Step 2 - oracle

Say the marked item is |101>. The oracle flips the sign of that amplitude only: it becomes -1/sqrt(8) while the others stay +1/sqrt(8). This is a phase flip, invisible to measurement on its own.

Step 3 - diffusion (inversion about the mean)

Reflect every amplitude about the average. The mean is (7 - 1)/(8*sqrt(8)) = 6/(8 sqrt(8)). Reflecting a about mean m gives 2m - a. The marked amplitude jumps up while the others shrink.

import numpy as np
n=3; N=8; psi=np.ones(N)/np.sqrt(N)
mark=0b101
def iterate(psi):
    psi=psi.copy(); psi[mark]*=-1          # oracle
    m=psi.mean(); psi=2*m-psi              # diffusion
    return psi
psi=iterate(psi)
print(np.round(psi**2,3))  # P(101) ~ 0.781 after 1 iter
psi=iterate(psi)
print(np.round(psi**2,3))  # P(101) ~ 0.945 after 2 iters

Result

After one iteration the marked state has probability about 0.78; after the optimal two it reaches about 0.945. Running too many iterations overshoots and the probability falls again - Grover is a rotation, not a monotone climb, so counting iterations correctly matters.