The Exercise

Let $U$ be any unitary acting on one qubit. The gate $C^2(U)$ acts on three qubits and applies $U$ to the third exactly when the first two are both in the state $\lvert 1 \rangle$.^✦ The exercise asks for a circuit that builds $C^2(U)$, for every $U$, from at most eight one qubit gates and at most six controlled NOT (CNOT) gates.

Qubits and Unitaries

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 quantum system whose state space is the tensor product of their state spaces.^✦ A pure state $\psi$ of $S$ is a unit vector $\psi$ in the state space of $S$, $\lVert \psi \rVert = 1$.^✦

The qubit $Q$ is the two level system whose state space is $\mathbb{C}^2$ itself, the standard two dimensional complex Euclidean space.^✦ Its computational basis states $\lvert 0 \rangle$ and $\lvert 1 \rangle$ are the pure states given by the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$.^✦ Three qubits form the composite system $Q \otimes (Q \otimes Q)$.

A unitary $U$ of a system $S$ is a closed system evolution of $S$: an operator on the state space of $S$ with $$U^\dagger U = U U^\dagger = 1.$$(1)^✦ The identity evolution of $S$ is the unitary whose operator is $1$.^✦ For unitaries $U$ of $S$ and $V$ of $T$, the product unitary $U \otimes V$ is the unitary of $S \otimes T$ whose operator is the tensor product of the two operators.^✦ Acting on the first factor of $S \otimes T$, a unitary $U$ of $S$ becomes $U \otimes 1$, with the identity evolution on $T$; acting on the last factor, a unitary $V$ of $T$ becomes $1 \otimes V$.

Controlled Gates

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$, a control qubit followed by the target $S$, with operator $$C(U) = \lvert 0 \rangle\langle 0 \rvert \otimes 1 + \lvert 1 \rangle\langle 1 \rvert \otimes U.$$(2)^✦

The Pauli $X$ gate, the quantum NOT, is the unitary of $Q$ whose operator is the matrix $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix},$$(3) and the CNOT gate is the controlled gate $C(X)$ of $Q \otimes Q$, with the first qubit as control.

For a unitary $U$ of the qubit $Q$, the doubly controlled gate $C^2(U)$ is the unitary of $Q \otimes (Q \otimes Q)$ obtained by controlling the controlled gate $C(U)$ once more, $$C^2(U) = C\bigl(C(U)\bigr).$$(4)

Three Qubit Circuits

A three qubit circuit is a finite sequence of gates on $Q \otimes (Q \otimes Q)$, whose factors are its wires $0$, $1$ and $2$. Each of its gates is either a one qubit gate, a unitary $g$ of $Q$ on one of the wires, or a CNOT from a control wire $c$ to a target wire $t$.^✦ On the three qubits, a one qubit gate $g$ on wire $0$, $1$ or $2$ is the unitary $$g \otimes 1, \qquad 1 \otimes (g \otimes 1), \qquad 1 \otimes (1 \otimes g)$$(5)^✦ respectively. The CNOTs from wire $0$ to wire $1$, from $0$ to $2$ and from $1$ to $2$ are $$C(X \otimes 1), \qquad C(1 \otimes X), \qquad 1 \otimes \mathrm{CNOT},$$(6)^✦ and a CNOT on any other pair of wires is the identity.

If $G_1, \dots, G_n$ are the unitaries of the gates of a circuit in order, the evolution of the circuit is the product $$G = G_1 G_2 \cdots G_n,$$(7) and its gate counts are $N_1$, the number of its one qubit gates, and $N_{\mathrm{CNOT}}$, the number of its CNOTs.

The Claim

What Is Checked

The claim is stated over the doubly controlled gate (4), built from the controlled gate (2), and over the evolution (7) of a circuit whose gates are the one qubit gates (5) and the CNOTs (6), together with the two counts of its gates.

The library proves that these constructions are unitaries.