The Exercise

The controlled NOT (CNOT) and the single qubit gates form a universal set: every unitary on a register of qubits is a product of CNOT gates, each acting on an ordered pair of wires, and of single qubit unitaries, each acting on one wire. The problem asks for the same reach from a different set of resources. Single qubit unitaries are applied directly, the CNOT between any two wires is realized by gate teleportation, and a protocol runs such steps one after another. The question is whether every unitary of the register is implemented by some protocol.

The library poses the problem on a register of $n + 2$ qubits, for any $n \geq 0$, with the universality of the CNOT and single qubit gates on that register as its hypothesis.

Systems and Registers

A quantum system $S$ is given by its state space, a finite dimensional complex Hilbert space.^✦ The qubit $Q$ is the two level system whose state space is the model space $\mathbb{C}^2$ itself.^✦ 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, and the composite $\bigotimes_p S_p$ of a finite family of systems is formed in the same way. The tensor power $S^{\otimes m}$ of a system $S$ is the composite of $m$ copies of $S$, one on each of the wires $1, \dots, m$; a register of $m$ qubits is $Q^{\otimes m}$.^✦

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$; its inverse $e^{-1}$ identifies $T$ with $S$. A bijection $\pi$ between the wires of two tensor powers of $S$ with equally many wires gives the relabelling of wires, the identification that reindexes the composite and moves the factor on wire $p$ to wire $\pi(p)$.^✦ Splitting $S^{\otimes(a+b)}$ into its first $a$ and its last $b$ wires identifies it with $S^{\otimes a} \otimes S^{\otimes b}$, through the isometry that divides the wires into two blocks: $$|\psi_1\rangle \otimes \cdots \otimes |\psi_{a+b}\rangle \longmapsto \bigl(|\psi_1\rangle \otimes \cdots \otimes |\psi_a\rangle\bigr) \otimes \bigl(|\psi_{a+1}\rangle \otimes \cdots \otimes |\psi_{a+b}\rangle\bigr).$$(1)^✦ The head split of $S^{\otimes(m+1)}$ is the identification of $S^{\otimes(m+1)}$ with $S \otimes S^{\otimes m}$ that takes the first wire alone as the first factor and the remaining $m$ wires as the second.^✦

Gates on Chosen Wires

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 the identity evolution of $S$ is the unitary $1$. For two unitaries $U$ and $V$ of $S$, the unitary $UV$ is the composite operator, first $V$ then $U$.^✦ For a unitary $U$ of $S$ and a unitary $V$ of $T$, the product unitary $U \otimes V$ of $S \otimes T$ has the tensor product of the two operators as its operator; $U$ alone on the first factor is $U \otimes 1$.

A unitary $U$ of $S$ is carried along an identification $e$ of $S$ with $T$ to the unitary $e U e^{-1}$ of $T$.^✦ A linear isometric bijection $L$ of the state space of $S$ onto itself gives the unitary of $S$ whose operator is $L$, and for a permutation $\sigma$ of the wires of $S^{\otimes m}$ the wire permutation gate $P_\sigma$ is the unitary whose operator is the relabelling of wires along $\sigma$.

A gate $G$ on $a$ wires, a unitary of $S^{\otimes a}$, is placed on the first $a$ wires of $S^{\otimes(a+b)}$ by carrying $G \otimes 1$ of $S^{\otimes a} \otimes S^{\otimes b}$ along the inverse of the block split (1); this gate is again written $G \otimes 1$.^✦ A permutation $\sigma$ of the $a + b$ wires then places $G$ with its $p$th wire on wire $\sigma(p)$: $$G_\sigma = P_\sigma \, (G \otimes 1) \, P_\sigma^{-1}.$$(2)^✦

A unitary $U$ of the qubit acts on wire $i$ of the register $Q^{\otimes(n+2)}$ as the single qubit gate $U_{(i)}$. It is $U \otimes 1$ of $Q \otimes Q^{\otimes(n+1)}$, carried to the register along the inverse of the head split and then along the relabelling by the transposition $(1\;i)$ that exchanges the first wire with wire $i$: $$U_{(i)} = P_{(1\,i)} \, (U \otimes 1) \, P_{(1\,i)}^{-1}.$$(3)^✦

Controlled NOT Gates

The Pauli $X$, the quantum NOT, is the unitary of the qubit whose matrix is $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$$(4)^✦

The control register $T_k(S)$ of $k$ qubits in front of a system $S$ is defined by $T_0(S) = S$ and $T_{k+1}(S) = Q \otimes T_k(S)$.^✦ The $k$ times controlled gate $C^k(E)$ of a unitary $E$ of $S$ is the unitary of $T_k(S)$ that applies $E$ to $S$ when all $k$ control qubits are in the state $\lvert 1 \rangle$ and acts as the identity otherwise; it is given by $$C^0(E) = E, \qquad C^{k+1}(E) = C\bigl(C^k(E)\bigr),$$(5)^✦ where $C(\cdot)$ is the controlled gate whose control is the qubit in front. Undoing the head split $k$ times identifies $T_k(Q)$ with $Q^{\otimes(k+1)}$, the controls on wires $1, \dots, k$ and the target on wire $k + 1$, and along this identification $C^k(X)$ is a gate on $k + 1$ qubits. In a register of $k + 1 + b$ qubits a permutation $\sigma$ places it by (2), with the controls on wires $\sigma(1), \dots, \sigma(k)$ and the target on wire $\sigma(k+1)$.^✦

Take a set $A$ of $k$ wires and a wire $t$ outside it, in a register of $k + 1 + b$ wires. The gathering permutation sends positions $1, \dots, k$ to the wires of $A$ in increasing order, position $k + 1$ to $t$, and the last $b$ positions to the remaining wires, also in increasing order.^✦ In a register $Q^{\otimes m}$, the controlled NOT with control set $A$ and target $t \notin A$ is $C^k(X)$ placed by this permutation, with $b = m - k - 1$.^✦ With the single control $A = \{i\}$ and a target $j \neq i$ it is the CNOT from wire $i$ to wire $j$, written $\mathrm{CNOT}_{ij}$.

The Claim

A generator of the register $Q^{\otimes(n+2)}$ is a unitary of it that is a CNOT on an ordered pair of distinct wires or a single qubit unitary on one wire.^✦ The generators form the set $$\mathcal{G}_n = \{\mathrm{CNOT}_{ij} : i \neq j\} \cup \{U_{(i)} : 1 \leq i \leq n + 2,\ U \text{ a unitary of } Q\}.$$(6)^✦

The set $\mathcal{R}_n$ of the gates the resources implement is the smallest set of unitaries of the register that contains the identity, every single qubit gate $U_{(i)}$ and every teleported $\mathrm{CNOT}_{ij}$ with $i \neq j$, and that contains $UV$, the protocol for $V$ followed by the one for $U$, whenever it contains $U$ and $V$: $$1 \in \mathcal{R}_n, \qquad U_{(i)} \in \mathcal{R}_n, \qquad \mathrm{CNOT}_{ij} \in \mathcal{R}_n, \qquad U, V \in \mathcal{R}_n \implies UV \in \mathcal{R}_n.$$(7)^✦

What Is Checked

The claim is stated over the register $Q^{\otimes(n+2)}$ and its unitaries: the generators (6), built from the gathered controlled $X$ and from the single qubit gates (3), and the set (7) of the gates the resources implement.

About these constructions the library proves that each is a unitary: the composite $UV$ and the product $U \otimes V$ of two unitaries, the carried unitary $e U e^{-1}$, the unitary of a linear isometric bijection, and the Pauli $X$, whose matrix is unitary. It proves as well the two counts behind the placement of a controlled NOT: in a register of $k + 1 + b$ wires, exactly $b$ wires lie outside a set of $k$ controls and a target, and $k + 1 + (m - k - 1) = m$ when the controls and the target lie among $m$ wires.