The Exercise

Let $m$ and $n$ be positive integers and $f$ a classical function from $m$ bits to $n$ bits, sending each $x \in \{0, \dots, 2^m - 1\}$ to $f(x) \in \{0, \dots, 2^n - 1\}$. A unitary $U_f$, built from $T$ classical reversible gates on a register of $m$ qubits and a register of $n$ qubits, computes $f$: on $|x\rangle|0\rangle$ it leaves the first register as it is and writes $f(x)$ into the second. The problem asks for a circuit of $2T + n$ gates that multiplies $|x\rangle$ by the phase $e^{-2\pi i f(x)/2^n}$, with the second register in $|0\rangle$ before and after.

Registers and Their States

A quantum system is given by its state space, a finite dimensional complex Hilbert space, and a pure state $|\psi\rangle$ of a system $S$ is a unit vector in the state space of $S$. The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ with its standard inner product; its computational basis state $|i\rangle$, for $i \in \{0, \dots, d - 1\}$, is the pure state given by the $i$th standard basis vector. The qudit with $2^m$ levels is a register of $m$ qubits.

The composite system $A \otimes B$ of two systems $A$ and $B$ has as its state space the tensor product of their state spaces.^✦ For pure states $|\psi\rangle$ of $A$ and $|\varphi\rangle$ of $B$, the product state $|\psi\rangle \otimes |\varphi\rangle$ is the pure state of $A \otimes B$ whose vector is the tensor product of the two vectors.^✦ The two registers form one composite system, and $|x\rangle|0\rangle$ is the product of the basis states $|x\rangle$ and $|0\rangle$.

Unitaries

A unitary $U$ of a system $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 = 1$; it carries a pure state $|\psi\rangle$ of $S$ to the pure state $U|\psi\rangle$.^✦ For unitaries $U$ and $V$ of $S$, $U$ after $V$ is the unitary $UV$ of $S$, which applies $V$ first and then $U$, and the adjoint $U^\dagger$ is the unitary of $S$ whose operator is the adjoint of that of $U$. For a unitary $U$ of $A$ and a unitary $V$ of $B$, the product unitary $U \otimes V$ is the unitary of $A \otimes B$ whose operator is the tensor product of those of $U$ and $V$.^✦

A pure state $|\psi\rangle$ of $S$ is an eigenstate of a unitary $U$ of $S$ with eigenvalue $\mu \in \mathbb{C}$ when $$U|\psi\rangle = \mu\,|\psi\rangle.$$(1)^✦

The Circuit

For $k \in \{0, \dots, 2^n - 1\}$, the phase angle $\theta_k$ is $$\theta_k = -\frac{2\pi k}{2^n}.$$(2)^✦ For real angles $\alpha_0, \dots, \alpha_{d-1}$, the diagonal phase gate $D$ is the unitary of the qudit with $d$ levels that is diagonal in the computational basis: $$D|i\rangle = e^{i\alpha_i}\,|i\rangle.$$(3)^✦

For a unitary $U_f$ of a register of $m$ qubits together with a register of $n$ qubits, and the identity unitary $1$ of the first register, whose operator is the identity, the computable phase shift circuit $C$ is the unitary that applies $U_f$, then $D$ with the angles $\theta_k$ of (2) on the second register, then $U_f^\dagger$: $$C = U_f^\dagger\,(1 \otimes D)\,U_f.$$(4)^✦

Counting Gates

Gates come in two kinds. The first are the classical reversible gates, NOT gates with at most two control qubits and the target outside them: the NOT, the controlled NOT and the Toffoli gate. A unitary $U$ of a register counts as $t$ gates of the first kind when it acts on the computational basis states as a circuit of $t$ classical reversible gates acts on bit strings. A gate of the second kind is a single qubit unitary $g$ on one qubit, or $g$ or $g^\dagger$ controlled by a second qubit.

A unitary $U$ meets the gate budget $(t, s)$, written $U \in \mathcal{G}(t, s)$, when it is a product of such pieces with at most $t$ gates of the first kind and at most $s$ of the second, up to identifications between systems, such as that of the two registers with one register of $m + n$ qubits.^✦

The Claim

For a unitary $U_f$ that computes $f$ from $T$ classical reversible gates, the two theorems give the circuit the problem asks for, with the phase on $|x\rangle$ as the eigenvalue of $C$ on $|x\rangle|0\rangle$ and the $2T + n$ gates split by kind.

What Is Checked

The claims are stated over the circuit $C$ of (4), which composes $U_f$, the product unitary $1 \otimes D$ with the angles (2) and the adjoint $U_f^\dagger$; over the product states $|x\rangle|0\rangle$ of computational basis states; and over the eigenstate condition (1) and the gate budget.

About these constructions the library proves that $U$ after $V$, the adjoint of a unitary, the product unitary and the diagonal phase gate are unitaries, the last since its diagonal entries $e^{i\alpha_i}$ have modulus one. It proves that a unitary applied to a pure state is again a unit vector, since a unitary preserves norms, and that so is the product of two pure states, since the norm of a product vector is the product of the norms.