The Exercise

A search over $N$ items, the indices $x = 0, 1, \dots, N-1$, is posed by a function $f$ that assigns each index a bit; $x$ is a solution when $f(x) = 1$. The oracle $O$ is a unitary that flips an oracle qubit $r$ exactly when the index register, a system with $N$ levels whose basis states are the indices, holds a solution. Adjoin an extra qubit $q$ to the index, so that the items become the $2N$ pairs $(x, q)$. The exercise asks for an augmented oracle $O'$, made from $O$ and elementary gates, that marks the pair $(x, q)$ with a minus sign when $x$ is a solution and $q = 0$, and leaves every other pair unmarked.

Systems and States

A quantum system $S$ is described by its state space, a finite dimensional complex Hilbert space.^✦ The composite system $S \otimes T$ of two systems $S$ and $T$ is the system whose state space is the tensor product of their state spaces.^✦ The qudit with $d$ levels is the system with state space $\mathbb{C}^d$, and the qubit is the two level system, with state space $\mathbb{C}^2$.

A pure state $|\psi\rangle$ of a system $S$ is a unit vector in the state space of $S$.^✦ For a level $i$ of the qudit with $d$ levels, the computational basis state $|i\rangle$ is the pure state whose vector is the standard basis vector of $\mathbb{C}^d$ with entry $1$ at $i$ and $0$ elsewhere; on the qubit these are $|0\rangle$ and $|1\rangle$.^✦ Given pure states $|\psi\rangle$ of $S$ and $|\varphi\rangle$ of $T$, their product $|\psi\rangle \otimes |\varphi\rangle$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two vectors.^✦

The oracles act on the composite system of an index register, the qudit with $N$ levels, and the two qubits $q$ and $r$. The basis states of this composite system are the products $|x\rangle|a\rangle|b\rangle = |x\rangle \otimes (|a\rangle \otimes |b\rangle)$ of an index $x$ with a bit $a$ for $q$ and a bit $b$ for $r$.

Unitaries and Gates

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$, and it carries a pure state $|\psi\rangle$ of $S$ to the pure state $U|\psi\rangle$. The identity $1$ is a unitary of every system.^✦ Of two unitaries $U$ and $V$ of $S$, the product $UV$ is the unitary that applies $V$ first and then $U$.^✦ Given unitaries $U$ of $S$ and $V$ of $T$, the product unitary $U \otimes V$ of $S \otimes T$ is the tensor product of their operators; in particular $1 \otimes V$ acts with $V$ on the last factor and leaves the first alone.

The Pauli gate $X$, the quantum NOT, and the Hadamard gate $H$ are the unitaries of the qubit whose matrices in the computational basis are $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.$$(1) For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite of a control qubit with the target $S$ given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(2)^✦ The controlled NOT gate (CNOT) is the gate $C(X)$ of two qubits, which flips the second qubit when the first is $|1\rangle$.^✦

Three gates act on the two qubits of the oracles alone, $X$ and $H$ on the oracle qubit and CNOT with $q$ as control and $r$ as target: $$X_r = 1 \otimes (1 \otimes X), \qquad H_r = 1 \otimes (1 \otimes H), \qquad \mathrm{CNOT}_{q \to r} = 1 \otimes \mathrm{CNOT}.$$(3)

The Oracle and Its Augmentation

A unitary $O$ of the index register and the two qubits is a bit flip oracle for $f$ when, for every index $x$ and all bits $a$ and $b$, $$O\,|x\rangle|a\rangle|b\rangle = |x\rangle|a\rangle|b \oplus f(x)\rangle ,$$(4)^✦ with $\oplus$ addition modulo $2$. The augmented oracle $O'$ of $O$ is the unitary $$O' = X_r \, \mathrm{CNOT}_{q \to r} \, H_r \, O \, H_r \, \mathrm{CNOT}_{q \to r} \, X_r .$$(5)^✦

The Claim

A pure state $|\psi\rangle$ of a system $S$ is an eigenstate of a unitary $U$ of $S$, with eigenvalue a complex number $\mu$, when $U|\psi\rangle = \mu|\psi\rangle$.^✦

What Is Checked

The claim is stated over a bit flip oracle $O$ for an arbitrary $f$, defined by (4), and over the augmented oracle (5) built from it with the gates (3), on the basis states $|x\rangle|q\rangle|0\rangle$ of the index register and the two qubits.

About these constructions the library proves that the controlled gate $C(U)$ of (2) is unitary for every unitary $U$, and that the matrices (1) are unitary. Products $UV$ and $U \otimes V$ of unitaries are again unitary.