The Exercise

A search space holds $N$ items, one of which, $x$, is marked, and a quantum computer is to find it. Its register has one basis state for each item, and it learns about $x$ only by calling an oracle, a unitary that depends on $x$. A search algorithm prepares a starting state, alternates $k$ oracle calls with unitaries of its own that do not depend on $x$, and measures the register in the basis of items; it succeeds when the outcome is $x$.

The demand on the algorithm is weak. Its probability of success need not reach one half for every marked item, only on average over the $N$ items: it may fail on some items as long as it succeeds often enough on the others. The exercise is to show that even so the number of oracle calls must grow like $\sqrt{N}$.

A Quantum System

A quantum system $S$ is a physical object whose state space is a finite dimensional complex Hilbert space.^✦ A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦ A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$, and it determines the state $|\psi\rangle\langle\psi|$ of $S$, the projector onto $|\psi\rangle$. A unitary $U$ of $S$, a closed evolution of $S$, is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦

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 satisfy the completeness relation $$\sum_i M_i^\dagger M_i = 1 .$$(1)^✦ The positive operator valued measure (POVM) of a measurement $\{M_i\}$ on $S$ consists of the effects $E_i = M_i^\dagger M_i$, one for each outcome $i$. When the measurement is performed on a state $\rho$, the outcome $i$ occurs with the probability given by the Born rule, $$p(i) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr) = \operatorname{Tr}(E_i \rho) .$$(2)^✦ 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 Search Problem

A quantum search problem on $S$ with $N$ items is an orthonormal basis $|0\rangle, \dots, |N-1\rangle$ of the state space of $S$, the vector $|x\rangle$ standing for the item $x$.^✦ When $x$ is the item sought, the marked state $|x\rangle$ is the pure state given by its basis vector.^✦ The search measurement is the projective measurement in this basis; its outcome is the item found.^✦

An algorithm starts from a pure state $|\psi\rangle$ of $S$ and has a sequence of unitaries $U_0, U_1, \dots$ of $S$. For a pure state $|v\rangle$ of $S$, the state after $k$ oracle queries is $|\psi_k\rangle$, defined by $$|\psi_0\rangle = |\psi\rangle , \qquad |\psi_{j+1}\rangle = U_j \, O_v \, |\psi_j\rangle ,$$(3)^✦ where the oracle $O_v$ is the reflection that reverses the sign of $|v\rangle$ and leaves every vector orthogonal to $|v\rangle$ unchanged, a unitary of $S$. Taking the marked state $|x\rangle$ for $|v\rangle$ gives the state $|\psi^x_k\rangle$ of the algorithm after $k$ calls to the oracle $O_x$.^✦ The search measurement on $|\psi^x_k\rangle\langle\psi^x_k|$ finds the marked item with the probability that (2) assigns to the outcome $x$, $$p_k(x) = |\langle x | \psi^x_k \rangle|^2 .$$(4)

The Claim

What Is Checked

The claim is stated over a quantum search problem and its search measurement, a starting pure state, the unitaries $U_j$ and the oracle calls of (3) that produce the states $|\psi^x_k\rangle$, and the Born probabilities (4) of finding each marked item.

The library proves that the projectors onto the vectors of an orthonormal basis satisfy the completeness relation (1), so that the search measurement is a measurement, and that the Born probabilities of any measurement form a probability distribution. Each vector of an orthonormal basis has unit norm, which makes the marked state $|x\rangle$ a pure state. The projector onto a unit vector is a density operator, and so each $|\psi^x_k\rangle\langle\psi^x_k|$ is a state.