# Grover's algorithm
**Grover's algorithm** is a quantum search algorithm that finds a marked element in an unstructured database of $N$ items in $O(\sqrt{N})$ queries. It was invented by Lov Grover in 1996 and provides a quadratic speedup over classical brute-force search, which requires $O(N)$ queries in the worst case.

The algorithm works with a phase oracle $U_f$ that marks the target state $\lvert x^*\rangle$ by flipping its phase: $U_f\lvert x\rangle = -\lvert x\rangle$ if $x = x^*$, and $U_f\lvert x\rangle = \lvert x\rangle$ otherwise. Starting from the uniform superposition $\lvert s\rangle = H^{\otimes n}\lvert 0\rangle^{\otimes n}$, repeated Grover iterations amplify the amplitude of $\lvert x^*\rangle$ until it can be measured with high probability.

## Grover iteration
A single Grover iteration $G$ consists of two operations. First, the oracle $U_f$ flips the sign of the target state's amplitude. Second, the diffusion operator $D = 2\lvert s\rangle\langle s\rvert - I$ reflects the state about the uniform superposition, amplifying the target amplitude and suppressing all others.

$$G = D \cdot U_f \qquad D = 2\lvert s\rangle\langle s\rvert - I = H^{\otimes n}(2\lvert 0\rangle\langle 0\rvert - I)H^{\otimes n}$$

## Optimal number of iterations
Starting from $\lvert s\rangle$, after $k$ Grover iterations the probability of measuring $\lvert x^*\rangle$ is $\sin^2((2k+1)\theta)$ where $\sin\theta = 1/\sqrt{N}$. The optimal number of iterations before measuring is $k^* = \lfloor\frac{\pi}{4}\sqrt{N}\rceil$, giving a success probability close to 1.

## Optimality
Grover's algorithm is provably optimal: no quantum algorithm can search an unstructured database faster than $\Omega(\sqrt{N})$ queries. The quadratic speedup is therefore the best possible for unstructured search.