The Exercise

Fix a real number $\alpha$. The gate $G$ acts on three qubits: when the first two are both in the state $|1\rangle$ it applies $iR_x(\pi\alpha)$ to the third, the rotation by the angle $\pi\alpha$ about the $\hat x$ axis multiplied by $i$, and otherwise it leaves the three qubits alone.^✦ The exercise is to show that $G$ is universal for quantum computation whenever $\alpha$ is irrational: circuits made of copies of $G$ alone approximate any unitary operation on any number of qubits.

Gates on Qubits

A quantum system $S$ is given by its state space, a finite dimensional complex Hilbert space, and a pure state $\psi$ of $S$ is a unit vector of that space. The composite system $S \otimes T$ of two systems $S$ and $T$ is the system whose state space is the tensor product of theirs.^✦ A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ For a unitary $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; with $V$ the identity, $U$ acts on the first factor alone.^✦

The qubit is the system with state space $\mathbb{C}^2$, and its computational basis states $|0\rangle$ and $|1\rangle$ are the pure states given by the two standard unit vectors. For a vector $\vec n$ in three dimensions, $\vec n \cdot \vec\sigma = n_x X + n_y Y + n_z Z$ combines the Pauli matrices $X$, $Y$, $Z$ of (1) with the components of $\vec n$ as coefficients, and the rotation $R_{\hat n}(\theta)$ by an angle $\theta$ about a unit vector $\hat n$ is the unitary of the qubit given by the exponential: $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \qquad R_{\hat n}(\theta) = \exp\Bigl(-\frac{i\theta}{2}\,\hat n \cdot \vec\sigma\Bigr).$$(1) The rotation about the $\hat x$ axis is $R_x(\theta) = R_{\hat n}(\theta)$ with $\hat n = (1,0,0)$, so $R_x(\theta) = \exp(-i\theta X/2)$, and $iR_x(\theta)$ is the unitary of the qubit whose matrix is $i$ times that of $R_x(\theta)$.

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of $\mathrm{qubit} \otimes S$ that acts on $S$ as the identity when the control qubit is $|0\rangle$ and as $U$ when it is $|1\rangle$; iterating it gives the doubly controlled gate: $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U, \qquad C^2(U) = C\bigl(C(U)\bigr).$$(2) The gate $G$ of the exercise, the Deutsch gate, is the unitary of $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$ $$G = C^2\bigl(iR_x(\pi\alpha)\bigr).$$(3)^✦

The Register

The circuits act on a register of $M$ qubits whose wires are split into $m$ data wires and $n$ ancilla wires. The qudit with $D$ levels is the system with state space $\mathbb{C}^D$, and its computational basis $\{|i\rangle\}$ is made of the standard unit vectors; a unitary $D \times D$ matrix $N$ gives the gate of the qudit that acts as $N$ in this basis. The register is the qudit with $D = 2^M$ levels, its basis states $|y\rangle$ labelled by the bit strings $y$ of its $M$ wires. The data register is the qudit with $d = 2^m$ levels, its basis states $|x\rangle$ labelled by the bit strings $x$ of the data wires.

Extending a data string $x$ by the value $1$ on every ancilla wire gives a string $(x,\mathbf 1)$ of the register.^✦ The states $|x,\mathbf 1\rangle$ span the data subspace, where the data sit beside ancillas all in $|1\rangle$. A $D \times D$ matrix $N$ preserves the data subspace when it maps it into itself, $$\langle y|\,N\,|x,\mathbf 1\rangle = 0 \quad \text{whenever } y \text{ is not of the form } (x',\mathbf 1),$$(4) and its compression to the data subspace is the $d \times d$ matrix $$\Gamma(N)_{x x'} = \langle x,\mathbf 1|\,N\,|x',\mathbf 1\rangle .$$(5) The action $\Gamma(E)$ of a unitary $E$ of the register on the data register is the operator on $\mathbb{C}^d$ with matrix $\Gamma(N)$, where $N$ is the matrix of $E$.

Circuits of the Deutsch Gate

A matrix $W$ acting block by block on a single wire $c$ of the register is fixed by a $2 \times 2$ matrix $B(y)$ for each value of the wires other than $c$: the element $\langle y|W|y'\rangle$ is $B(y)_{y_c\,y'_c}$ when $y$ and $y'$ agree on every wire but $c$, and zero otherwise.^✦ For a set $K$ of control wires and a $2 \times 2$ matrix $\tilde U$, the multiply controlled gate $C^K_c(\tilde U)$ is the one with $B(y) = \tilde U$ when $y_k = 1$ for every $k$ in $K$, and $B(y) = 1$ otherwise.^✦ For wires $a$, $b$ and $c$, the placed powers of $G$ are the gates of the register with controls $a$ and $b$ and target $c$ built from the powers $i^k R_x(k\pi\alpha)$ of $iR_x(\pi\alpha)$: $$C^{\{a,b\}}_c\bigl(i^k R_x(k\pi\alpha)\bigr), \qquad k \in \mathbb{Z}.$$(6)^✦

A reachable gate is a $D \times D$ matrix that preserves the data subspace, (4), and is a limit of the placed powers (6) for some wires $a$, $b$ and $c$.^✦ The reachable circuits are the finite products of gates of unitary reachable gates, the identity among them as the empty product; they form the set $\mathcal R_\alpha$ of unitaries of the register.^✦

An identification $e$ of two systems is a linear isometric bijection between their state spaces, and a unitary $U$ is carried along it as $eUe^{-1}$. Numbering the basis states $|i\,j\,k\rangle$ of three qubits as $|4i+2j+k\rangle$ identifies three qubits with the qudit with $8$ levels and makes $G$ a unitary of that qudit.^✦ With $r = 2^{M-3}$, sending $|ri+l\rangle$ to the product basis state $|i\rangle \otimes |l\rangle$ identifies the register, the qudit with $8r$ levels, with the composite of the qudits with $8$ and $r$ levels, and along it $G \otimes 1$ becomes a unitary of the register.^✦ For an ordered choice of three wires, let $\sigma$ be the renumbering of the register’s basis states that puts these wires first, and $P_\sigma$ the unitary of the register that permutes the computational basis by it, $|i\rangle \mapsto |\sigma(i)\rangle$.^✦ Then $P_\sigma^{-1}(G \otimes 1)P_\sigma$ is $G$ on the chosen wires, the first two its controls, and the identity on the other $M-3$.

The Claim

What Is Checked

The claim is stated over the Deutsch gate $G$ of (3), the reachable circuits $\mathcal R_\alpha$ built from its placed powers, and the action $\Gamma$ of a circuit on the data register.

About these constructions the library proves that $C(U)$ is unitary for every unitary $U$, so that $G$ is a unitary of three qubits, and that a unitary carried along an identification, or tensored with another unitary, is again unitary, so that $P_\sigma^{-1}(G \otimes 1)P_\sigma$ is a unitary of the register. The matrices that preserve the data subspace include the identity and are closed under multiplication.^✦