The Exercise

Two data qubits, numbered $1$ and $2$, share a circuit with an ancilla qubit. An observable $M$ of the data with eigenvalues $\pm 1$, such as the product $X_1X_2$ of Pauli $X$ gates or the product $Z_1Z_2$ of Pauli $Z$ gates on the two data qubits, is measured through the ancilla: it is prepared in $|0\rangle$, a Hadamard gate acts on it, $M$ acts on the data controlled by the ancilla, a second Hadamard gate acts on the ancilla, and the ancilla is read out in the computational basis. Outcome $0$ projects the data onto the $+1$ eigenspace of $M$, outcome $1$ onto the $-1$ eigenspace.

The controlled $M$ acts on all three qubits at once. For these two observables the whole circuit can be rebuilt from gates that touch the ancilla and one data qubit at a time. For $Z_1Z_2$ it is two controlled NOT (CNOT) gates, each with a data qubit as control and the ancilla as target; for $X_1X_2$ each of these CNOTs sits between two Hadamard gates on its data qubit. These are the circuits of Figure 10.17.

Qubits and Gates

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $\psi$ of $S$ is a unit vector $\psi$ in the state space of $S$.^✦ The composite system $S \otimes T$ of two quantum systems $S$ and $T$ is the quantum system whose state space is the tensor product of their state spaces.^✦ The qubit $Q$ is the system whose state space is $\mathbb{C}^2$ itself^✦; its basis states $|0\rangle$ and $|1\rangle$ are the pure states given by the standard basis vectors $e_0$ and $e_1$.^✦ The ancilla and the two data qubits form the system $Q \otimes (Q \otimes Q)$, the ancilla first.

A unitary $U$ of a quantum system $S$ is an operator $U$ on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ The product $UV$ of unitaries $U$ and $V$ of $S$ is the unitary that applies $V$ first and then $U$.^✦ The product unitary $U \otimes V$ of a unitary $U$ of $S$ and a unitary $V$ of $T$ is the unitary of $S \otimes T$ whose operator is the tensor product of theirs.^✦ A unitary $U$ of $S$ acts on $S \otimes T$ as $U \otimes 1$^✦, and a unitary $V$ of $T$ acts on $S \otimes T$ as $1 \otimes V$^✦, where $1$ is the identity operator on the other factor.

The Pauli gates $X$ and $Z$ and the Hadamard gate $H$ are the unitaries of the qubit whose operators are the matrices $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \qquad H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$(1) in the basis $|0\rangle, |1\rangle$. On the data qubits, $X_1X_2 = (X \otimes 1)(1 \otimes X)$ and $Z_1Z_2 = (Z \otimes 1)(1 \otimes Z)$, unitaries of $Q \otimes Q$.

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$, control qubit first, given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(2)^✦ The CNOT gate is $C(X)$ on $Q \otimes Q$.^✦ The SWAP of two copies of a system $S$ is the unitary of $S \otimes S$ given by the isometry $x \otimes y \mapsto y \otimes x$^✦, and the CNOT with control on the second qubit and target on the first is $$\mathrm{CNOT}^{\mathrm{rev}} = \mathrm{SWAP}\; \mathrm{CNOT}\; \mathrm{SWAP} .$$(3)^✦

The measurement circuit $K(U)$ of a unitary $U$ of a system $S$ is the unitary of $Q \otimes S$ that applies a Hadamard gate to the control qubit, then $C(U)$, then a second Hadamard gate to the control: $$K(U) = (H \otimes 1)\, C(U)\, (H \otimes 1) .$$(4)^✦

Gates on Two of Three Qubits

An identification $e$ of a quantum system $S$ with a quantum system $T$ is a linear isometric bijection from the state space of $S$ onto that of $T$.^✦ Identifications have inverses $e^{-1}$, composites $f \circ e$ (first $e$, then $f$) and tensor products $e \otimes f$, which act factor by factor on a composite system; the identity identification $1_S$ of $S$ with itself is the identity map.^✦ The relabelling of a unitary $U$ of $S$ along an identification $e$ of $S$ with $T$ is the unitary of $T$ $$e\, U\, e^{-1} .$$(5)^✦

For three systems $A$, $B$ and $C$, the regrouping $\alpha_{A,B,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$^✦, and the swap $\mathrm{swap}_{A,B}$ identifies $A \otimes B$ with $B \otimes A$ by $u \otimes v \mapsto v \otimes u$.^✦ The left interchange $\lambda_{A,B,C}$ identifies $A \otimes (B \otimes C)$ with $B \otimes (A \otimes C)$ by bringing the middle factor to the front: $$\lambda_{A,B,C} = \alpha_{B,A,C}^{-1} \circ (\mathrm{swap}_{A,B} \otimes 1_C) \circ \alpha_{A,B,C} .$$(6)^✦

Write $\alpha$ and $\lambda$ for $\alpha_{Q,Q,Q}$ and $\lambda_{Q,Q,Q}$. A unitary $W$ of two qubits, relabelled by (5), acts on the ancilla and qubit $1$ as $\alpha^{-1} (W \otimes 1)\, \alpha$, and on the ancilla and qubit $2$ as $\lambda\, (1 \otimes W)\, \lambda^{-1}$, in both cases with the ancilla as its first qubit.

The block $B_X$ for $X_1X_2$ is the unitary of $Q \otimes Q$, ancilla first, that applies a Hadamard gate to the data qubit, then a CNOT from the data qubit into the ancilla, then a second Hadamard gate to the data qubit: $$B_X = (1 \otimes H)\, \mathrm{CNOT}^{\mathrm{rev}}\, (1 \otimes H) .$$(7)

The Claim

What Is Checked

The claim compares unitaries of the three qubits: the circuit (4), built from the Hadamard gate and the controlled gate (2), for the products $X_1X_2$ and $Z_1Z_2$ of Pauli gates on the data qubits; and the reversed CNOT (3) with Hadamard gates, set on pairs of qubits by relabelling (5) along the regrouping and the left interchange (6).

About these constructions the library proves that the operator (2) is unitary for every unitary $U$, $C(U)^\dagger C(U) = C(U)\, C(U)^\dagger = 1$^✦, and that the matrices (1) are unitary. Products and tensor products of unitaries are again unitaries, and so is a unitary relabelled along an identification, its adjoint being its inverse.