# Grover search and amplitude amplification {#grover}

**Learning goals.** Implement two reflections, derive the two-dimensional rotation, choose iteration counts, and include oracle and sampling costs.

## The search problem

A predicate marks M of N candidates. We can coherently implement
$O|x\rangle=-|x\rangle$ for marked x and $|x\rangle$ otherwise.
For simplicity let $N=2^n$ and prepare

$$|s\rangle=\frac1{\sqrt N}\sum_{x=0}^{N-1}|x\rangle.$$

One measurement of this state succeeds with probability M/N. Grover's algorithm increases that probability using the oracle and the diffusion operation

$$D=2|s\rangle\langle s|-I.$$

D is a reflection: it keeps $|s\rangle$ and reverses components orthogonal to it. It is unitary because $D^2=I$. It can be implemented using Hadamards and a phase operation on $|0^n\rangle$, up to global phase.

For amplitudes $a_x$, define their mean $\bar a=N^{-1}\sum_xa_x$. Then

$$(D|\psi\rangle)_x=2\bar a-a_x.$$

The “reflection about the mean” description refers to amplitudes, which may be complex; it does not reflect probabilities.

## Four-item worked example

Let N=4 and mark 10. Start with amplitudes $(1,1,1,1)/2$. The oracle gives

$$\left(\tfrac12,\tfrac12,-\tfrac12,\tfrac12\right),\qquad
\bar a=\frac{\tfrac12+\tfrac12-\tfrac12+\tfrac12}{4}=\frac14.$$

Diffusion maps an unmarked amplitude to
$2(1/4)-1/2=0$, and the marked one to
$2(1/4)-(-1/2)=1$. Thus one iteration gives $|10\rangle$ exactly. This special small case illustrates interference but is not the general iteration count [@grover].

## Rotation in a two-dimensional subspace

Define normalized uniform marked and unmarked states $|G\rangle,|B\rangle$. Then

$$|s\rangle=\sin\theta|G\rangle+\cos\theta|B\rangle,\qquad
\sin^2\theta=M/N.$$

The oracle reverses the good component. Diffusion reflects about $|s\rangle$. Their product $DO$ rotates the state in this plane by $2\theta$ toward the marked subspace. After k iterations,

$$|\psi_k\rangle=
\sin((2k+1)\theta)|G\rangle+
\cos((2k+1)\theta)|B\rangle,$$
$$P_k=\sin^2((2k+1)\theta).$$

Choose a nonnegative integer k near $\pi/(4\theta)-1/2$ and compare the neighboring integer values. When $M\ll N$, this is approximately $(\pi/4)\sqrt{N/M}$ iterations. Additional iterations can rotate past the target and reduce success.

For N=8,M=1, after one iteration

$$\sin(3\theta)=3\sin\theta-4\sin^3\theta
=\frac3{\sqrt8}-\frac4{8\sqrt8}
=\frac5{2\sqrt8},$$

so $P_1=25/32$. After two, $P_2=121/128$. The algorithm does not monotonically improve forever.

![Grover success probability oscillates with iteration count.](figures/grover.svg)

## General amplitude amplification

Suppose an algorithm A prepares
$A|0\rangle=\sqrt p|G\rangle+\sqrt{1-p}|B\rangle$.
Replace the uniform-state reflection by
$A(2|0\rangle\langle0|-I)A^\dagger$.
Alternating it with a phase flip of successful outcomes amplifies the initial success amplitude. The cost includes calls to both A and $A^\dagger$ as well as the success test [@amplification].

Unknown M complicates choosing k. Randomized iteration schedules, counting methods, or fixed-point variants can address this, with their own guarantees and costs. Applying the known-M formula to an unknown success rate is not an exact algorithm.

## What the speedup does and does not establish

Grover achieves a quadratic improvement in black-box query complexity and is optimal in that setting [@zalka]. A practical runtime includes preparation, reversible predicate computation, workspace, fault tolerance, and repetitions. Searching an ordinary database is not automatically one cheap quantum query: data access must be defined.

For an n-bit key with an efficient verification predicate, unstructured quantum search has the query scale $2^{n/2}$. That observation is not a complete cryptanalytic resource estimate. Parallelism, oracle circuits, reversible memory, and error-correction overhead affect the physical cost.

Grover also does not solve NP-complete problems in polynomial time in general. Replacing a $2^n$ exhaustive search by $2^{n/2}$ remains exponential in n. Structure-specific classical or quantum algorithms may perform differently; the black-box lower bound does not apply to every structured task.

::: {.lab #lab-grover}
**Laboratory L15 — Amplitude amplification.** Choose register size, marked items, iterations, shots, and seed. Inspect signed amplitudes after each iteration and the complete success curve. Deliberately over-rotate.
:::

## Exercises

:::: {.exercise #ex11-1}
**11.1.** For N=4,M=1, calculate success after two iterations.

::: {.solution}

$\theta=\pi/6$, so $P_2=\sin^2(5\pi/6)=1/4$. The second iteration undoes the perfect success of the first.
:::

::::

:::: {.exercise #ex11-2}
**11.2.** For M=N/2, does the ordinary iteration improve success?

::: {.solution}

$\theta=\pi/4$, so $\sin^2((2k+1)\pi/4)=1/2$ for every integer k. This reflection schedule cannot improve it.
:::

::::

:::: {.exercise #ex11-3}
**11.3.** Prove D preserves the vector norm.

::: {.solution}

Let $P=|s\rangle\langle s|$, with $P^2=P=P^\dagger$. Then $D^\dagger D=(2P-I)^2=4P^2-4P+I=I$.
:::

::::

:::: {.exercise #ex11-4}
**11.4.** A state preparation costs 100 gates, its inverse costs 100, and a success oracle costs 500. Estimate gate work for 20 amplification iterations, excluding reflection overhead.

::: {.solution}

$20(100+100+500)=14{,}000$ gates, plus the initial preparation and omitted reflections. Counting only 20 oracle queries would conceal most details.
:::

::::

:::: {.exercise #ex11-5}
**11.5.** With independent success probability P per run, how many runs make failure at most $\delta$?

::: {.solution}

Failure is $(1-P)^r$. For $0<P<1$, choose
$r\ge\log\delta/\log(1-P)$ and round up. Verification of the proposed answer must also be included.
:::

::::

