Grover's Algorithm Implementation

Grover's Algorithm Implementation

Grover's algorithm searches an unsorted database of N items in O(√N) quantum queries: a quadratic speedup over classical O(N) linear search. For N = 10⁶ items: 1,000 quantum queries vs 1,000,000 classical.

The Search Problem

Given a Boolean function f: {0,1,...,N-1} → {0,1} with exactly one "marked" item x where f(x)=1, find x*. Classical: check each item in turn, expected N/2 queries. Quantum: O(√N) queries.

The oracle $U_f$ is a black box that marks the target: $U_f|x⟩=(-1{)}^{f(x)}|x⟩$. It applies a phase flip to the target without revealing $x^{\ast }$ directly.

The Three Components

1. Initialization: Apply H to all n qubits. This creates the uniform superposition $|+{⟩}^{\otimes n}=(1/\sqrt{N}){\sum }_x|x⟩$. All states start with equal amplitude $1/\sqrt{N}$.

2. Oracle $U_f$: Phase-flip the target state. The target amplitude goes from $+1/\sqrt{N}$ to $-1/\sqrt{N}$. All other amplitudes remain $+1/\sqrt{N}$. This alone does not help: the probabilities are still all $1/N$.

Each Grover iteration rotates the state vector by approximately 2θ in the 2D subspace spanned by the target and all others. After k ≈ π/4 × √N iterations, the target amplitude reaches near 1.

Iteration Count

The optimal number of iterations is: k = ⌊π/4 × √N⌋ (for a single marked item)

Under-iterate: target probability not yet maximal. Over-iterate: amplitude wraps around and decreases again. For N=8 (n=3 qubits): k ≈ 2.