The Exercise

An unstructured search runs over $N$ items, $M$ of which are marked, with $1 \le M \le N$. The marked set is unknown, and the only access to it is an oracle that flips the sign of the basis states of the marked items. A quantum algorithm prepares a fixed initial state and then alternates calls to the oracle with unitaries of its own; at the end it measures in the computational basis. Show that if the measurement returns a marked item with probability at least one half, whichever $M$ items are marked, then the algorithm calls the oracle $\Omega(\sqrt{N/M})$ times.^✦

A Quantum System

A quantum system $S$ is a physical system 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$ of $S$ is a vector $|\psi\rangle$ of unit norm in that space, and it determines the state $|\psi\rangle\langle\psi|$ of $S$, the projector onto $|\psi\rangle$. A unitary $U$ of $S$, an evolution of $S$ as a closed system, is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = I$.^✦

A measurement on $S$ with a finite set of outcomes $\iota$ is a family of operators $M_i$ on the state space of $S$, one for each outcome $i$, that satisfies the completeness relation $$\sum_{i \in \iota} M_i^\dagger M_i = I .$$(1)^✦ The positive operator valued measure (POVM) of a measurement $\{M_i\}$ on $S$ is the family of positive operators $E_i = M_i^\dagger M_i$, the effects, one for each outcome $i$. Performed on a state $\rho$, the measurement gives the outcome $i$ with the Born probability $$p(i) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr) = \operatorname{Tr}(E_i \rho) .$$(2)^✦ The projective measurement in an orthonormal basis $\{|b_i\rangle\}$ of the state space 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 given by its computational basis, an orthonormal basis $\{|x\rangle\}$ of the state space of $S$ whose vectors are labelled by the $N$ items $x$.^✦ The search measurement of a quantum search problem on $S$ is the projective measurement of $S$ in its computational basis; the outcome $x$ means that the search returns the item $x$.^✦

For a set $s$ of items, the marked projection $P_s$ is the orthogonal projector onto the span of the basis vectors $|x\rangle$ with $x \in s$, and the search oracle for the marked set $s$ is the unitary $$O_s = I - 2 P_s$$(3) of $S$.

Fix an initial pure state $|\psi\rangle$ and a sequence of unitaries $U_0, U_1, \dots$ of $S$, the algorithm’s own steps. With a unitary $O$ in the place of the oracle, the state after $k$ queries is the pure state $|\psi_k\rangle$ given by $$|\psi_0\rangle = |\psi\rangle , \qquad |\psi_{j+1}\rangle = U_j \, O \, |\psi_j\rangle .$$(4)^✦ For $O = O_s$ the pure state $|\psi_k\rangle$ is written $|\psi_k^s\rangle$, the state of $S$ after $k$ queries to the oracle for $s$. Write $p_s(y)$ for the Born probability (2) of the outcome $y$ when the search measurement is performed on $|\psi_k^s\rangle\langle\psi_k^s|$.

The Claim

For large $N/M$ the bound grows as $\sqrt{N/M}/(2\sqrt{2})$, which is the $\Omega(\sqrt{N/M})$ of the exercise.

What Is Checked

The claim is stated over the computational basis of a search problem and its search measurement, the oracles $O_s$ of (3) for the sets $s$ of $M$ items, the states $|\psi_k^s\rangle$ of (4), and the Born probabilities (2) of the search outcomes on $|\psi_k^s\rangle\langle\psi_k^s|$.

Of these constructions the library proves that $O_s$ is unitary, because $P_s$ is an orthogonal projector, $P_s^2 = P_s = P_s^\dagger$. It proves that the projectors $|b_i\rangle\langle b_i|$ of an orthonormal basis satisfy the completeness relation (1), since each projector $P$ has $P^\dagger P = P$ and the projectors sum to the identity.