The Exercise

A list holds $N \ge 2$ items, one of which, $x$, is marked. The search starts in the uniform superposition $|\psi\rangle$ of all $N$ items and repeats a single step: evolve for a time $\Delta t$ under the Hamiltonian $|x\rangle\langle x|$, then for the same time under $|\psi\rangle\langle\psi|$. The exercise asks for a step time $\Delta t$ for which some number $j$ of steps, of order $\sqrt N$, carries $|\psi\rangle$ to $|x\rangle$ exactly, so that a measurement then finds $x$ with certainty.

Both Hamiltonians act in the plane spanned by $|x\rangle$ and the uniform superposition of the $N-1$ unmarked items. Taken as a qubit, a two level system with basis vectors $|0\rangle$ and $|1\rangle$, this plane has $|0\rangle$ for the marked item and $|1\rangle$ for the superposition of the unmarked ones.

A Quantum System

A quantum system $S$ is described by its state space, a finite dimensional complex Hilbert space.^✦ The qubit is the two level system whose state space is $\mathbb{C}^2$, with basis vectors $|0\rangle$ and $|1\rangle$.^✦

A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$.^✦ A state $\rho$ of $S$, also called a density operator of $S$, is a positive operator of unit trace on the state space of $S$.^✦ A pure state $|\psi\rangle$ of $S$ determines the state $|\psi\rangle\langle\psi|$ of $S$, the rank one projector onto $|\psi\rangle$.^✦

For real angles $\theta$ and $\phi$, the pure state $|\psi(\theta,\phi)\rangle$ of the qubit with polar angle $\theta$ and azimuth $\phi$ is the vector of $\mathbb{C}^2$ with components $\cos(\theta/2)$ and $e^{i\phi}\sin(\theta/2)$, $$|\psi(\theta,\phi)\rangle = \cos\frac{\theta}{2}\,|0\rangle + e^{i\phi}\sin\frac{\theta}{2}\,|1\rangle .$$(1)^✦ At $\theta = \phi = 0$ it is $|0\rangle$.

Hamiltonians and Evolution

An observable $A$ on $S$ is a self adjoint operator on the state space of $S$, $A^\dagger = A$.^✦ The projector Hamiltonian of a pure state $|\chi\rangle$ of $S$ is the observable $|\chi\rangle\langle\chi|$ on $S$, the projector onto $|\chi\rangle$.^✦

A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = UU^\dagger = 1$.^✦ It carries a pure state $|\psi\rangle$ of $S$ to the pure state $U|\psi\rangle$.^✦ Two unitaries $U$ and $V$ of $S$ compose to the unitary $UV$ of $S$, $V$ first and then $U$.^✦

The propagator of an observable $H$ of $S$, with Planck’s constant $\hbar$, from time $t_1$ to time $t_2$ is the unitary $$U(t_1,t_2) = \exp\bigl[-iH(t_2-t_1)/\hbar\bigr],$$(2)^✦ the evolution of $S$ under the Hamiltonian $H$ over that interval.

For real $\theta$ and $\Delta t$, the search step $U(\Delta t)$ is the unitary of the qubit made of the propagators (2) from $0$ to $\Delta t$, with $\hbar = 1$, of the projector Hamiltonians of $|0\rangle$ and of $|\psi(\theta,0)\rangle$, the second after the first: $$U(\Delta t) = e^{-i\Delta t\,|\psi(\theta,0)\rangle\langle\psi(\theta,0)|}\, e^{-i\Delta t\,|0\rangle\langle 0|} .$$(3)^✦

The Claim

With $\cos\theta = 2/N - 1$, the state $|\psi(\theta,0)\rangle$ has weight $\cos^2(\theta/2) = (1+\cos\theta)/2 = 1/N$ on $|0\rangle$, the weight of the marked item in the uniform superposition. It stands for $|\psi\rangle$, and (3) is the step of the exercise in units with $\hbar = 1$.

What Is Checked

The claim is stated over the search step (3) on the qubit, applied $j$ times to the pure state $|\psi(\theta,0)\rangle$, and over the comparison of the result with $|0\rangle$ as states.

The library proves the facts these constructions rest on. The vector (1) has squared norm $\cos^2(\theta/2) + \sin^2(\theta/2) = 1$, since $|e^{i\phi}| = 1$. The projector onto a state vector is self adjoint, the propagator (2) of an observable is unitary, and so is the composite of two unitaries.