The Exercise

An oracle holds a string $X$ of $N$ bits $X_i$, and a quantum computer is to find their OR, $\mathrm{OR}(X) = 0$ if every bit is $0$ and $\mathrm{OR}(X) = 1$ if some bit is $1$. The computer learns about $X$ only by querying the oracle. The zero error query complexity $Q_0(\mathrm{OR})$ is the least number of queries with which a quantum algorithm finds $\mathrm{OR}(X)$ with certainty for every string $X$, and the exercise is to show that $Q_0(\mathrm{OR}) \geq N$.

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\rangle$ of $S$ is a unit vector in the state space of $S$, and it determines the state $|\psi\rangle\langle\psi|$, the projector onto that vector. The closed evolutions of $S$ are its unitaries: a unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦

The Query Register

A query register on $S$ is an orthonormal basis of the state space of $S$, the computational basis $$|i, b, j\rangle, \qquad i \in \Sigma, \quad b \in \{0, 1\}, \quad j \in \Omega,$$(1)^✦ where $\Sigma$ is a finite set of $N$ indices, one for each bit of the oracle, $b$ is the value of the answer qubit, and $\Omega$ is a finite set labelling the states of the workspace. A string $X$ assigns a bit $X_i$ to each index $i \in \Sigma$, and its oracle is the unitary $O_X$ of $S$ that adds $X_i$ to the answer qubit modulo two, $$O_X |i, b, j\rangle = |i, b \oplus X_i, j\rangle.$$(2)^✦

Queries and the Read Out

An algorithm starts from a pure state $|\psi\rangle$ of $S$ and alternates unitaries $U_0, U_1, U_2, \dots$ of $S$, which do not depend on $X$, with calls to the oracle. For a unitary $O$ in the place of the oracle, the state after $t$ queries is $$|\psi_0\rangle = U_0 |\psi\rangle, \qquad |\psi_{t+1}\rangle = U_{t+1}\, O\, |\psi_t\rangle,$$(3) The query state $|\psi_t(X)\rangle$ of the algorithm on the string $X$ is the state $|\psi_t\rangle$ after $t$ queries with $O = O_X$.

After the last query the register is measured. A measurement on $S$ with a finite set of outcomes is a family of measurement operators $M_k$ on the state space of $S$, one for each outcome $k$, satisfying the completeness relation $\sum_k M_k^\dagger M_k = 1$.^✦ The positive operator-valued measure (POVM) of this measurement is the family of effects $E_k = M_k^\dagger M_k$, and the probability of the outcome $k$ when the measurement is performed on a state $\rho$ of $S$ is given by the Born rule, $$p(k) = \operatorname{Tr}(M_k \rho M_k^\dagger) = \operatorname{Tr}(E_k \rho).$$(4) The projective measurement in an orthonormal basis $\{|e_k\rangle\}$ is the measurement whose operator for the outcome $k$ is the projector $|e_k\rangle\langle e_k|$.^✦ The read out of the query register is the projective measurement in the computational basis (1), with the labels $k = (i, b, j)$ as its outcomes.^✦

The Claim

Let $p_X(k)$ be the probability (4) of the outcome $k$ when the read out is performed on $|\psi_T(X)\rangle\langle\psi_T(X)|$. The answer is read from the outcome: a set $A_0$ of labels stands for the answer $\mathrm{OR}(X) = 0$, and the algorithm gives that answer with probability $P_X(A_0) = \sum_{k \in A_0} p_X(k)$. The string of zeros is written $X = 0$.

What Is Checked

The claim is stated over the query register, the oracle (2), the query states (3) and the probabilities (4) of the read out in the computational basis. About these constructions the library proves that $O_X$ is a unitary. It proves that the projectors $|e_k\rangle\langle e_k|$ of an orthonormal basis satisfy the completeness relation, each projector $P$ having $P^\dagger P = P$ and all of them summing to the identity, so the read out is a measurement; and that the effects $E_k$ of any measurement are positive. The projector onto a unit vector is a density operator, so $|\psi_T(X)\rangle\langle\psi_T(X)|$ is a state of $S$.