The Exercise

Three qubits have the computational basis states $|q_0 q_1 q_2\rangle$, with $q_0, q_1, q_2 \in \{0, 1\}$. Let $\tilde U$ be a unitary of a single qubit, with matrix $$\tilde U = \begin{pmatrix} a & c \\ b & d \end{pmatrix}$$(1) in the basis $|0\rangle, |1\rangle$. The exercise asks for a circuit of one qubit gates and controlled NOT gates (CNOTs) that implements the two level unitary of three qubits built from $\tilde U$ on the states $|010\rangle$ and $|111\rangle$. On their span it acts as $\tilde U$, with $|010\rangle$ in the place of $|0\rangle$ and $|111\rangle$ in the place of $|1\rangle$; the other six basis states stay fixed.

The library builds one such circuit: the doubly controlled gate $C^2(\tilde U)$ between two copies of a routing unitary $W$ made of three CNOTs.

Three Qubits

A quantum system $S$ is a physical system whose state space is 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.^✦ A pure state $\psi$ of $S$ is a unit vector in the state space of $S$, and for pure states $\psi$ of $S$ and $\varphi$ of $T$ the product $\psi \otimes \varphi$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two vectors.

The qubit is the two level system with state space $\mathbb{C}^2$.^✦ Its basis states $|0\rangle$ and $|1\rangle$ are the pure states whose vectors are the standard basis vectors $e_0$ and $e_1$.^✦ Three qubits form the composite system $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$, and its basis state $$|q_0 q_1 q_2\rangle = |q_0\rangle \otimes \bigl(|q_1\rangle \otimes |q_2\rangle\bigr)$$(2) is a product of three basis states of the qubit. In a circuit the three qubits sit on wires $0$, $1$ and $2$, from the top.

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$; it carries a pure state $\psi$ of $S$ to the pure state $U\psi$. For two unitaries $U$ and $V$ of $S$, $U$ after $V$ is the unitary $UV$ of $S$, first $V$ and then $U$, and the identity evolution of $S$ is the unitary $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 theirs.^✦ Placed on the first wires of $S \otimes T$, a unitary $U$ of $S$ becomes $U \otimes 1$; placed on the last wires, a unitary $V$ of $T$ becomes $1 \otimes V$. The SWAP of two copies of $S$ is the unitary of $S \otimes S$ that exchanges the factors, $\mathrm{SWAP}(x \otimes y) = y \otimes x$.^✦

The Gates

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of $\mathrm{qubit} \otimes S$, a control qubit and the target $S$, with operator $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(3)^✦ The Pauli $X$ is the unitary of the qubit with matrix $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, and the CNOT gate is $C(X)$ on two qubits: it flips the second qubit when the first is $|1\rangle$. With the control below, $$\mathrm{CNOT}^{\mathrm{rev}} = \mathrm{SWAP}\,\mathrm{CNOT}\,\mathrm{SWAP}$$(4)^✦ is the CNOT controlled by the second qubit with the first as target. On three qubits the doubly controlled gate $C^2(U) = C\bigl(C(U)\bigr)$ of a unitary $U$ of the qubit applies $U$ to the qubit on wire $2$ exactly when the qubits on wires $0$ and $1$ are both $|1\rangle$.^✦

A gate $G$ of a three qubit circuit is either a one qubit gate, a unitary $g$ of the qubit on a chosen wire, or a CNOT with a chosen control wire and target wire; its evolution $U_G$ is a unitary of the three qubits.^✦ A one qubit gate $g$ on wire $0$, $1$ or $2$ has the evolution $g \otimes 1$, $1 \otimes (g \otimes 1)$ or $1 \otimes (1 \otimes g)$.^✦ A CNOT with control wire $0$ and target wire $1$ or $2$ is $C(X \otimes 1)$ or $C(1 \otimes X)$, conditioned on wire $0$ with $X$ on the target wire; with control wire $1$ and target wire $2$ it is $1 \otimes \mathrm{CNOT}$, and every other pair of wires gives the identity.^✦ The evolution of a list $G_1, \dots, G_k$ of gates is the product of their evolutions in the order given, $$U_{G_1} U_{G_2} \cdots U_{G_k} .$$(5)^✦

The Circuit

The routing $W$ is a product of three CNOTs, each with its control below its target: the outer two are $1 \otimes \mathrm{CNOT}^{\mathrm{rev}}$ and the middle one is the CNOT $R$ with its control on wire $1$ and its target on wire $0$, $$W = \bigl(1 \otimes \mathrm{CNOT}^{\mathrm{rev}}\bigr)\, R\, \bigl(1 \otimes \mathrm{CNOT}^{\mathrm{rev}}\bigr) .$$(6)^✦ The outer two act as $|q_0 q_1 q_2\rangle \mapsto |q_0,\, q_1 \oplus q_2,\, q_2\rangle$, where $\oplus$ is addition modulo $2$, and the middle one as $|q_0 q_1 q_2\rangle \mapsto |q_0 \oplus q_1,\, q_1,\, q_2\rangle$.

To define the middle CNOT $R$ one regroups the three qubits, since $\mathrm{CNOT}^{\mathrm{rev}} \otimes 1$ acts on $(\mathrm{qubit} \otimes \mathrm{qubit}) \otimes \mathrm{qubit}$. An identification $e$ of a system $S$ with a system $T$ is a linear isometric bijection from the state space of $S$ onto that of $T$, and its inverse $e^{-1}$ identifies $T$ with $S$. Along $e$ a unitary $U$ of $S$ becomes the unitary $e\,U\,e^{-1}$ of $T$.^✦ The regrouping of three systems $A$, $B$ and $C$ identifies $A \otimes (B \otimes C)$ with $(A \otimes B) \otimes C$ by $u \otimes (v \otimes w) \mapsto (u \otimes v) \otimes w$.^✦ The middle CNOT $R$ is $\mathrm{CNOT}^{\mathrm{rev}} \otimes 1$, a unitary of $(\mathrm{qubit} \otimes \mathrm{qubit}) \otimes \mathrm{qubit}$, carried along the inverse of the regrouping to $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$.^✦

The two level unitary circuit is $W\,C^2(\tilde U)\,W$.^✦

The Claim

What Is Checked

The claim is stated over the evolution (5) of a list of gates of a three qubit circuit and over the two level unitary circuit $W\,C^2(\tilde U)\,W$, built from the controlled gate (3), the reversed CNOT (4) and the routing (6), acting on the product basis states (2).

The library proves that the controlled gate is unitary: for every unitary $U$ of a system $S$, the operator (3) satisfies $C(U)^\dagger C(U) = C(U)\,C(U)^\dagger = 1$. It proves too that products and tensor products of unitaries are unitary, as is a unitary carried along an identification, so that the gates and the circuit $W\,C^2(\tilde U)\,W$ are unitaries of the three qubits.