The Exercise

A unitary $U$ acts on a quantum system $S$. An extra qubit, the control, is prepared in $|0\rangle$ beside a state $|\psi\rangle$ of $S$. A Hadamard gate acts on the control, then a controlled gate applies $U$ to $S$ when the control is $|1\rangle$ and leaves $S$ alone when it is $|0\rangle$, and a second Hadamard acts on the control before the control is measured in the computational basis. Find the joint state just before that measurement. Then take $S$ to be a qubit and $U$ the Pauli $Z$ or $X$: write the circuit as a controlled-NOT gate (CNOT), with Hadamard gates around it in the case of $X$, and evaluate it on the eigenstates of $U$.

Systems and States

A quantum system $S$ comes with a state space, a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of $S$ is a vector of unit norm in the state space of $S$.^✦

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.^✦ For pure states $|\psi\rangle$ of $S$ and $|\varphi\rangle$ of $T$, the product $|\psi\rangle \otimes |\varphi\rangle$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two vectors.^✦

The qubit is the quantum system whose state space is $\mathbb{C}^2$.^✦ Its basis states $|0\rangle$ and $|1\rangle$ are the pure states whose vectors are the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$.^✦

Unitaries and Gates

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$^✦; it carries a pure state $|\psi\rangle$ of $S$ to the pure state $U|\psi\rangle$.^✦ Two unitaries $U$ and $V$ of $S$ compose to the unitary $UV$, which applies $V$ first and then $U$^✦, and the identity $1$ of $S$ is itself a unitary.^✦ Given a unitary $U$ of $S$ and a unitary $V$ of $T$, their product unitary $U \otimes V$ is the unitary of $S \otimes T$ whose operator is the tensor product of the two operators.^✦ A gate $U$ on the first factor alone is $U \otimes 1$^✦, and a gate $V$ on the last factor alone is $1 \otimes V$.^✦

The Hadamard gate $H$ and the Pauli gates $X$ and $Z$ are the unitaries of the qubit whose matrices in the computational basis are $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1) The states $|+\rangle$ and $|-\rangle$ are the pure states of the qubit $$|\pm\rangle = \frac{1}{\sqrt{2}} \bigl( |0\rangle \pm |1\rangle \bigr),$$(2) the eigenvectors of $X$ with eigenvalues $+1$ and $-1$.

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite $\mathrm{qubit} \otimes S$ of a control qubit and a target $S$ given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(3)^✦ The CNOT gate is the controlled gate $C(X)$ on two qubits.^✦

The SWAP of two copies of a system $S$ is the unitary of $S \otimes S$ that exchanges the factors, $\mathrm{SWAP}\,(|a\rangle \otimes |b\rangle) = |b\rangle \otimes |a\rangle$.^✦ The reversed CNOT $\mathrm{CNOT}^{\mathrm{rev}}$, the CNOT with control below, is the unitary of two qubits that takes the second qubit as control and the first as target; in terms of the swap it is $$\mathrm{CNOT}^{\mathrm{rev}} = \mathrm{SWAP}\;\mathrm{CNOT}\;\mathrm{SWAP}.$$(4)^✦

The Circuit

For a unitary $U$ of a system $S$, the circuit $M_U$ measuring $U$ is the unitary of $\mathrm{qubit} \otimes S$ that places $C(U)$ between two Hadamard gates on the control: $$M_U = (H \otimes 1)\, C(U)\, (H \otimes 1).$$(5)^✦

The Claim

When $U$ is Hermitian as well, its eigenvalues are $\pm 1$ and $P_\pm = \tfrac{1}{2}(1 \pm U)$ are the projectors onto its two eigenspaces. For a state $|\psi\rangle$ of $S$, the control then reads $0$ with probability $\langle \psi | P_+ | \psi \rangle$ and $1$ with probability $\langle \psi | P_- | \psi \rangle$, and $S$ is left in the normalised projection of $|\psi\rangle$: the circuit followed by a measurement of the control measures $U$. On an eigenstate of $U$ one branch of (6) vanishes, and the control ends in a basis state with $S$ unchanged. The Pauli gates $Z$ and $X$ are Hermitian. With a second qubit as target the circuit becomes a controlled-NOT gate.

What Is Checked

The claims are stated over the circuit $M_U$ of (5), built from the Hadamard gate and the controlled gate of (3), for an arbitrary unitary $U$ and for the Pauli gates of (1); over the CNOT with control below of (4); and over product states of $|0\rangle$, $|1\rangle$ and the states $|\pm\rangle$ of (2).

About these constructions the library proves that $C(U)$ is unitary for every unitary $U$, $C(U)^\dagger C(U) = C(U)\, C(U)^\dagger = 1$^✦, and that the matrices of $H$, $X$ and $Z$ are unitary. It proves that composites and tensor products of unitaries are unitary, which makes $M_U$ a unitary of $\mathrm{qubit} \otimes S$, and that SWAP, an isometry of the state space of $S \otimes S$ onto itself, is a unitary. It proves as well that a unitary carries a unit vector to a unit vector, and that the tensor product of two unit vectors has unit norm.