The Exercise

The circuit acts on three qubits, two controls and a target. For a unitary $U$ of one qubit, the doubly controlled gate $C^2(U)$ applies $U$ to the target exactly when both controls are $\lvert 1 \rangle$.^✦ Figure 4.8 of the book builds it from gates on two qubits, given a unitary $V$ with $V^2 = U$. The second qubit first controls $V$ on the target. A controlled NOT from the first qubit then flips the second, the second qubit controls $V^\dagger$ on the target, and a second controlled NOT undoes the flip. Last, the first qubit controls $V$ on the target. The exercise is to verify that this circuit implements $C^2(U)$.

Qubits and Unitaries

A quantum system $S$ is a physical object whose state space is a finite dimensional complex Hilbert space.^✦ 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 the state spaces of $S$ and $T$.^✦ The qubit is the two level quantum system whose state space is $\mathbb{C}^2$, and the three qubits of the circuit form the composite system $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$: the first qubit beside the pair of the second qubit and the target.

A pure state $\psi$ of a quantum system $S$ is a vector $\psi$ of unit norm in the state space of $S$.^✦ The basis states $\lvert 0 \rangle$ and $\lvert 1 \rangle$ of the qubit are the pure states whose vectors are the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$.^✦

A unitary $U$ of a quantum system $S$, a closed system evolution of $S$, is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ For two unitaries $U$ and $V$ of $S$, the composite $UV$, first $V$ then $U$, is again a unitary of $S$, and so is the adjoint $U^\dagger$, whose operator is the Hilbert space adjoint of that of $U$. The identity evolution of $S$ is the unitary $1$.^✦

For unitaries $U$ of a system $S$ and $V$ of a system $T$, the product unitary $U \otimes V$ is the unitary of $S \otimes T$ whose operator is the tensor product of the operators of $U$ and $V$.^✦ With the identity evolution in one factor it gives the gate $U \otimes 1$ on the first wires of $S \otimes T$, $U$ acting on $S$ and nothing on $T$, and the gate $1 \otimes V$ on the last wires.

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

Controlled 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) = \lvert 0 \rangle\langle 0 \rvert \otimes 1 + \lvert 1 \rangle\langle 1 \rvert \otimes U .$$(2)^✦ The target may itself be a composite system: the controlled NOT from the first of three qubits onto the second is $C(X \otimes 1)$, with $X$ of (1) and $X \otimes 1$ the gate on the first wires of the pair.

For a unitary $U$ of the qubit, the doubly controlled gate $C^2(U)$ is the unitary of $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$ in which the first qubit controls the two qubit gate $C(U)$, itself controlled by the second qubit: $$C^2(U) = C\bigl(C(U)\bigr).$$(3)^✦

The Circuit

For a unitary $V$ of the qubit, the circuit of Figure 4.8 is the unitary $W(V)$ of $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$ $$W(V) = C(1 \otimes V)\, C(X \otimes 1)\, \bigl(1 \otimes C(V^\dagger)\bigr)\, C(X \otimes 1)\, \bigl(1 \otimes C(V)\bigr),$$(4)^✦ whose rightmost factor acts first.

The Claim

What Is Checked

The claim is stated over the circuit (4) and the doubly controlled gate (3), unitaries of three qubits built from the controlled gate (2), the Pauli $X$, adjoints, composites and products of unitaries.