The Exercise

A search space holds $N$ items, of which $M$ are solutions, with $0 < M \le N/2$. Let $|\alpha\rangle$ be the normalized sum of the basis states of the $N - M$ items that are not solutions, and $|\beta\rangle$ the normalized sum of those of the $M$ solutions. The search starts in the uniform superposition of all $N$ items, which in these two vectors is $$|\psi\rangle = \cos\frac{\theta}{2}\,|\alpha\rangle + \sin\frac{\theta}{2}\,|\beta\rangle,$$(1)^✦ with $\sin(\theta/2) = \sqrt{M/N}$.

Each Grover iteration $G$ rotates this state in the plane of $|\alpha\rangle$ and $|\beta\rangle$ through the angle $\theta$. After $R$ iterations the state makes the angle $(2R+1)\theta/2$ with $|\alpha\rangle$, and measuring it finds a solution with probability $\sin^2\bigl((2R+1)\theta/2\bigr)$. The exercise is to show that some number of iterations no larger than $\frac{\pi}{4}\sqrt{N/M}$ brings this probability to one half or more.

A Qubit for the Plane

The library takes that plane for a qubit. A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space, and the qubit is the two level system whose state space is $\mathbb{C}^2$ itself. The standard basis vector $|i\rangle$ of $\mathbb{C}^d$ is the vector with entry $1$ in place $i$ and $0$ in every other place.^✦ On the qubit, $|0\rangle$ stands for $|\alpha\rangle$ and $|1\rangle$ for $|\beta\rangle$.

For a vector $|u\rangle$ of $\mathbb{C}^n$, the reflection about $|u\rangle$ is the $n \times n$ complex matrix $$2|u\rangle\langle u| - I,$$(2)^✦ which for a unit vector $|u\rangle$ reflects every vector about the line through $|u\rangle$. The oracle $O$, which flips the sign of every solution, is on the qubit the reflection (2) about $|0\rangle$.^✦

For an angle $\theta$, the Grover iteration $G$ of the qubit is the oracle followed by the reflection about the starting state $|\psi\rangle$ of (1): $$G = \bigl(2|\psi\rangle\langle\psi| - I\bigr)\,O.$$(3)^✦

A pure state $|\varphi\rangle$ of a system $S$ is a unit vector in the state space of $S$.^✦ After $R$ iterations the qubit is in the pure state $|\psi_R\rangle = G^R|\psi\rangle$, the state that is measured below.

Measuring the Qubit

A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦ A pure state $|\varphi\rangle$ of $S$ gives the state $|\varphi\rangle\langle\varphi|$, the projector onto $|\varphi\rangle$.^✦

A measurement on $S$ with a finite set of outcomes is a family of measurement operators $M_i$ on the state space of $S$, one for each outcome $i$, that satisfies the completeness relation $$\sum_i M_i^\dagger M_i = I.$$(4)^✦ The effect of a measurement $\{M_i\}$ for the outcome $i$ is the operator $E_i = M_i^\dagger M_i$, and the family $\{E_i\}$ is its positive operator valued measure (POVM).

When a measurement $\{M_i\}$ on $S$ is performed on a state $\rho$ of $S$, the probability of the outcome $i$ is given by the Born rule, $$p(i) = \operatorname{Tr}(E_i\,\rho) = \operatorname{Tr}(M_i\,\rho\,M_i^\dagger).$$(5)^✦

The projective measurement of $S$ in an orthonormal basis $\{|b_i\rangle\}$ is the measurement whose operator for the outcome $i$ is the projector $|b_i\rangle\langle b_i|$.^✦ The solution measurement is the projective measurement of the qubit in the basis $|0\rangle, |1\rangle$, so that outcome $1$ finds a solution and outcome $0$ an item that is not one.^✦

The Claim

What Is Checked

The claim is stated over the probability (5) of outcome $1$ of the solution measurement on the state $|\psi_R\rangle\langle\psi_R|$, where $|\psi_R\rangle$ comes from $R$ applications of the Grover iteration (3) to the starting state (1) on the qubit.

About these constructions the library proves that $G^R|\psi\rangle$ has unit norm for every angle $\theta$ and every $R$, which makes $|\psi_R\rangle$ a pure state, and that the projector onto a unit vector is positive with unit trace, so that $|\psi_R\rangle\langle\psi_R|$ is a state. It proves the completeness relation (4) for the projectors onto an orthonormal basis, which makes the solution measurement a measurement, and that each effect $M_i^\dagger M_i$ is positive.