The Exercise

A unitary $M$ acting on some data is measured with an ancilla qubit. The ancilla, prepared in $|0\rangle$, passes through a Hadamard gate, controls $M$ on the data, passes through a second Hadamard and is read out in the computational basis. In the fault tolerant version the ancilla is a cat state of three qubits, each of which controls a copy of the gate on its own block of data, and the result is read from the sign of the cat state under $X \otimes X \otimes X$.

The exercise is about phase flips $Z$ on the ancilla qubits. The data is untouched.

Qubits and Gates

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ 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.^✦ A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$^✦, and a nonzero vector $v$ of that space has the normalized pure state $v / \lVert v \rVert$.^✦ For pure states $|\psi\rangle$ of $S$ and $|\varphi\rangle$ of $T$, the product state $|\psi\rangle \otimes |\varphi\rangle$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two.^✦

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

A unitary $U$ of $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$.^✦ For two unitaries $U$ and $V$ of $S$, $UV$ is the unitary of $S$ that applies $V$ first and then $U$^✦, and the identity $1$ is a unitary of every system.^✦ For unitaries $U$ of $S$ and $V$ of $T$, the product unitary $U \otimes V$ is the unitary of $S \otimes T$ whose operator is the tensor product of theirs.^✦ The gate $U \otimes 1$ applies $U$ to the first factor alone.^✦

The gates of the qubit come from the Pauli matrices and the Hadamard matrix, $$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}, \quad H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.$$(1) The Hadamard $H$ and the phase flip $Z$ are the unitaries of the qubit with these matrices. For a unitary $U$ of $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$, a control qubit and the target $S$, given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U.$$(2)^✦

The Measurement Circuit

For a unitary $M$ of $S$, the measurement circuit $W_Z(M)$ with a phase error is the unitary of $Q \otimes S$ that applies a Hadamard on the ancilla, the controlled gate $C(M)$, a phase flip on the ancilla and a second Hadamard on the ancilla, in that order: $$W_Z(M) = (H \otimes 1)\,(Z \otimes 1)\,C(M)\,(H \otimes 1).$$(3)^✦

The Cat State

The three qubit register $R$ is the composite system $Q \otimes (Q \otimes Q)$.^✦ For bits $q_1$, $q_2$, $q_3$, its basis state $|q_1 q_2 q_3\rangle$ is the product state $|q_1\rangle \otimes (|q_2\rangle \otimes |q_3\rangle)$.^✦ For a bit $\sigma$, the cat state of the register is the normalization of the vector $|000\rangle + (-1)^\sigma |111\rangle$, $$|\mathrm{cat}_\sigma\rangle = \frac{1}{\sqrt{2}} \bigl( |000\rangle + (-1)^\sigma |111\rangle \bigr).$$(5)^✦

An observable $A$ of $S$ is a self adjoint operator on the state space of $S$.^✦ A pure state $|\psi\rangle$ of $S$ is an eigenstate of $A$ with eigenvalue $\mu$, a real number, when $A|\psi\rangle = \mu|\psi\rangle$.^✦ For observables $A$ of $S$ and $B$ of $T$, the observable $A \otimes B$ of $S \otimes T$ has for its operator the tensor product of theirs.^✦ For a real vector $\vec{n}$ in three dimensions with components $n_x$, $n_y$, $n_z$, the Pauli observable $\vec{n} \cdot \vec{\sigma}$ of the qubit is the observable with matrix $n_x X + n_y Y + n_z Z$^✦, and the observable $X$ is the Pauli observable of the unit vector $\hat{n} = (1, 0, 0)$.^✦ The block observable $X \otimes X \otimes X$ of the register measures $X$ on each of its three qubits.^✦

The phase flip $Z_i$ on qubit $i$ of the register, for $i = 1, 2, 3$, is the unitary of $R$ that applies $Z$ to that qubit and the identity to the other two.^✦

The Transversal Coupling

In the fault tolerant measurement each ancilla qubit sits in a block with its own data system. For a unitary $M'$ of a system $D$, the transversal coupling is the unitary of three such blocks, $(Q \otimes D) \otimes \bigl((Q \otimes D) \otimes (Q \otimes D)\bigr)$, in which each ancilla qubit controls $M'$ on the data of its block: $$T(M') = C(M') \otimes C(M') \otimes C(M').$$(7)^✦ For $i = 1, 2, 3$, the phase error $E_i$ on ancilla qubit $i$ is the unitary of $(Q \otimes D) \otimes \bigl((Q \otimes D) \otimes (Q \otimes D)\bigr)$ that applies $Z$ to that qubit and the identity everywhere else: $$E_1 = (Z \otimes 1) \otimes 1 \otimes 1, \qquad E_2 = 1 \otimes (Z \otimes 1) \otimes 1, \qquad E_3 = 1 \otimes 1 \otimes (Z \otimes 1).$$(8)

What Is Checked

The claim (4) is stated over the circuit $W_Z(M)$, built from the gates $H$ and $Z$ and the controlled gate $C(M)$; the claim (6) over the cat states, the block observable and the phase flips $Z_i$ of the register; and the claim (9) over the transversal coupling and the phase errors $E_i$.

The library proves that the vector $|000\rangle + (-1)^\sigma |111\rangle$ is nonzero for both values of $\sigma$, which makes its normalization, the cat state $|\mathrm{cat}_\sigma\rangle$, a pure state.^✦