The Exercise

The exercise is to show that four gates, together with measurement, are universal for quantum computation. The gates are the Hadamard gate $H$ and the phase gate $S$ on one qubit, the controlled NOT (CNOT) on two qubits and the Toffoli gate on three. Measurement enters through the circuit of Figure 4.17 of the book. A target qubit and two ancillas prepared in $|0\rangle$ pass through Hadamard gates on the ancillas, a Toffoli gate, $S$ on the target, a second Toffoli gate and Hadamard gates on the ancillas again; then both ancillas are measured in the computational basis. When both outcomes are $0$, the target has undergone a fixed single qubit gate. Universality asks that every unitary of $n+1$ qubits be approximated, up to a global phase and as closely as one likes, by circuits of these gates and of that measured gate, each placed on any of the qubits.

A Register of Qubits

A quantum system $A$ is given by its state space, a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of $A$ is a unit vector in the state space of $A$, determined physically up to a global phase.^✦ The qubit is the two level system whose state space is $\mathbb{C}^2$, the standard two dimensional complex Euclidean space; its basis states $|0\rangle$ and $|1\rangle$ are the pure states given by the standard basis vectors of $\mathbb{C}^2$.

The composite system $A \otimes B$ of systems $A$ and $B$ has as its state space the tensor product of their state spaces, and the product $|\psi\rangle \otimes |\varphi\rangle$ of a pure state of $A$ and a pure state of $B$ is the pure state of $A \otimes B$ whose vector is the tensor product of the two vectors. For a family of systems indexed by a finite set, the composite $\bigotimes_i A_i$ has the tensor product of all their state spaces as its state space.^✦ The tensor power $A^{\otimes m}$ is the composite of $m$ copies of $A$, one on each of the wires $0, \dots, m-1$.^✦

Gates with controls act on a register built one qubit at a time. The register of $n$ control qubits around a system $A$ is the system $Q_n(A)$ with $$Q_0(A) = A, \qquad Q_{n+1}(A) = \mathrm{qubit} \otimes Q_n(A),$$(1)^✦ and $Q_n = Q_n(\mathrm{qubit})$ is a register of $n+1$ qubits.

An identification $e$ of a system $A$ with a system $B$ is a linear isometric bijection from the state space of $A$ onto that of $B$, and its inverse $e^{-1}$ identifies $B$ with $A$.

The reindexing of a composite along a bijection $e$ of index sets is the identification that moves the factor at position $i$ to position $e(i)$; on tensor powers it relabels the wires.^✦ The split of $A^{\otimes(a+b)}$ is the identification of $A^{\otimes(a+b)}$ with $A^{\otimes a} \otimes A^{\otimes b}$ that divides the wire labels into a first block of $a$ and a last block of $b$ and sends a product of $a+b$ factors to the product of the first $a$ with the product of the last $b$. The register $Q_n$ is identified with the tensor power $\mathrm{qubit}^{\otimes(n+1)}$ by the identification $\iota_n$, defined by recursion: $\iota_0$ takes the qubit to its tensor power of one factor, and $\iota_n$ is the identity on the first qubit and $\iota_{n-1}$ on the rest, followed by the inverse of the split of $\mathrm{qubit}^{\otimes(n+1)}$ into $\mathrm{qubit} \otimes \mathrm{qubit}^{\otimes n}$.^✦

Gates

A unitary $U$ of a system $A$ is an operator on the state space of $A$ with $U^\dagger U = U U^\dagger = 1$; it carries a pure state $|\psi\rangle$ of $A$ to the pure state $U|\psi\rangle$. For unitaries $U$ and $V$ of $A$, $U$ after $V$ is the unitary $UV$, first $V$ and then $U$, and the identity evolution is the unitary $1$. For unitaries $U$ of $A$ and $V$ of $B$, the product unitary $U \otimes V$ of $A \otimes B$ is the tensor product of the two operators; $U \otimes 1$ is the gate $U$ on the first wires and $1 \otimes V$ the gate $V$ on the last wires. Along an identification $e$ of $A$ with $B$, a unitary $U$ of $A$ is carried to the unitary $e U e^{-1}$ of $B$.^✦ A linear isometric bijection of the state space of $A$ onto itself is a unitary of $A$.^✦

On the qubit, the Hadamard gate, the phase gate and the Pauli $X$ are the unitaries with the matrices $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}, \qquad X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$(2) in the computational basis $|0\rangle, |1\rangle$.

For a unitary $U$ of a system $A$, the controlled gate $C(U)$ is the unitary of $\mathrm{qubit} \otimes A$ given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U ,$$(3)^✦ with the qubit as control and $A$ as target. The CNOT gate is $C(X)$.^✦ The doubly controlled gate $C^2(U) = C(C(U))$ acts on three qubits, and the Toffoli gate is $C^2(X)$. With $n$ controls, $C^n(U)$ is the unitary of $Q_n(A)$ given by $C^0(U) = U$ and $C^{n+1}(U) = C(C^n(U))$.^✦ The NOT gate with $k$ controls, $X_k$, is $H S^2 H$ for $k = 0$, which is $X$ since $S^2 = \operatorname{diag}(1, -1)$, and $C^k(X)$ for $k \ge 1$.^✦

A single qubit gate $g$ acts on wire $i$ of $Q_n$, for $0 \le i \le n$, as the unitary $g_{(i)}$ that applies $g$ to the qubit at position $i$ and the identity to the others.^✦ On $Q_0$ it is $g$, and on $Q_n = \mathrm{qubit} \otimes Q_{n-1}$ it is $g \otimes 1$ for $i = 0$ and $1 \otimes g_{(i-1)}$ for $i \ge 1$.^✦

Gates on several wires are placed on tensor powers. For a permutation $\sigma$ of the wires of $A^{\otimes m}$, the wire permutation gate $P_\sigma$ is the unitary given by the isometry that moves the tensor factor on wire $i$ to wire $\sigma(i)$.^✦ For a gate $G$ of $A^{\otimes a}$ and $b$ further wires, the gate $G$ on the front block of $A^{\otimes(a+b)}$ is $G \otimes 1$ on $A^{\otimes a} \otimes A^{\otimes b}$, carried to $A^{\otimes(a+b)}$ by the inverse of the split, and for a permutation $\sigma$ of the wires the gate $G_\sigma$ of $A^{\otimes(a+b)}$, which applies $G$ on the wires $\sigma(0), \dots, \sigma(a-1)$, is $$G_\sigma = P_\sigma \, (G \otimes 1) \, P_{\sigma^{-1}} .$$(4)

The reversible generators of $Q_n$ are the NOT, the CNOT and the Toffoli gate on any ordered choice of one, two or three of its $n+1$ qubits, the gates $$\iota_n^{-1} \bigl( \iota_k X_k \iota_k^{-1} \bigr)_\sigma \, \iota_n , \qquad k \le 2 ,$$(5)^✦ where $\sigma$ is a permutation of the $k+1+b = n+1$ wires of (4), relabelled as the wires of $Q_n$. We write $\mathcal{X}_n$ for their set.

The Measured Gadget

A measurement on a system $A$ with a finite set of outcomes is a family of operators $M_i$ on the state space of $A$, one for each outcome $i$, satisfying the completeness relation $\sum_i M_i^\dagger M_i = 1$.^✦ The projective measurement in an orthonormal basis $\{|b_i\rangle\}$ has the operators $|b_i\rangle\langle b_i|$.^✦ A measurement on $A$ gives the measurement on the first wires of $A \otimes B$, with operators $M_i \otimes 1$, and the measurement on the last wires of $B \otimes A$, with operators $1 \otimes M_i$. The cascade of two measurements $L$ and $M$ on one system, first $L$ and then $M$, is the measurement with outcomes $(l, m)$ and operators $M_m L_l$.^✦

The measurement of the control qubit of $\mathrm{qubit} \otimes A$ is the projective measurement of the qubit in the computational basis on the first wires, with operators $|i\rangle\langle i| \otimes 1$.^✦ On three qubits, the measurement of the two ancillas measures the first qubit and then the second, and its operator for the outcome $(i, j)$ is $$N_{ij} = \bigl(1 \otimes |j\rangle\langle j| \otimes 1\bigr) \bigl(|i\rangle\langle i| \otimes 1 \otimes 1\bigr) = |i\rangle\langle i| \otimes |j\rangle\langle j| \otimes 1 .$$(6)^✦

The circuit of Figure 4.17 is the unitary $$K = W D W, \qquad W = H \otimes H \otimes 1, \qquad D = \mathrm{Toffoli}\,(1 \otimes 1 \otimes S)\,\mathrm{Toffoli}$$(7)^✦ of $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$, the two ancillas followed by the target.

The interference amplitude of the ancilla outcome $a'b'$ for the target bit $t$ is $$\lambda_{a'b'}(t) = \Bigl(\frac{1}{\sqrt{2}}\Bigr)^{4} \sum_{a, b \in \{0, 1\}} i^{\,t \oplus ab} \, (-1)^{a a'} \, (-1)^{b b'} ,$$(8)^✦ with $t \oplus ab$ the sum modulo $2$.

The circuit of Figure 4.17 followed by the measurement of its two ancillas is the gadget. A single qubit gate $G$ is realised by the gadget when there is a complex number $c$ with $|c|^2 = 5/8$ such that, for $t = 0$ and $t = 1$, $$N_{00}\, K \bigl( |0\rangle \otimes |0\rangle \otimes |t\rangle \bigr) = \lambda_{00}(t)\, |0\rangle \otimes |0\rangle \otimes |t\rangle , \qquad \lambda_{00}(t)\, |t\rangle = c\, G |t\rangle .$$(9)^✦ For any target state $|\psi\rangle$, the outcome $00$ then has probability $5/8$ and leaves the target in $G|\psi\rangle$.

We write $\mathcal{F}$ for the set of gates realised by the gadget.

The Claim

The set $\mathcal{R}_n$ of gates of $Q_n$ reachable with the four gates and measurement consists of the products of generators, namely $$\mathcal{R}_n = \bigl\{ E_1 E_2 \cdots E_m :\ m \ge 0,\ E_j \in \{ g_{(i)} : g \in \{H, S\} \cup \mathcal{F},\ 0 \le i \le n \} \cup \mathcal{X}_n \bigr\} ,$$(10) the empty product being the identity.

What Is Checked

The claim is stated over the unitaries of the register $Q_n$ and the reachable gates (10), measurement entering through the condition (9) on the circuit (7) and the measurement (6) of its ancillas.

The library proves that the controlled gate $C(U)$ of (3) is unitary for every unitary $U$ of any system, and with it every gate $C^k(X)$.^✦ It proves as well that a product and a tensor product of unitaries are unitary, and that the cascade of two measurements satisfies the completeness relation.