The Exercise

The fault tolerant Toffoli circuit consumes an ancilla, a fixed state $\lvert \Theta_T \rangle$ of three qubits prepared ahead of time. The exercise asks for its expansion in the computational basis and for two facts about three gates on the three qubits, each a Pauli operator on one qubit times a controlled operation on the other two. Each of the three leaves $\lvert \Theta_T \rangle$ unchanged, and up to a global phase no other pure state of the three qubits is left unchanged by all of them.^✦

Three Qubits

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The qubit $Q$ is the two level system with state space $\mathbb{C}^2$.^✦ For two systems $S$ and $T$, the composite $S \otimes T$ is the system whose state space is the tensor product of theirs.^✦ Three qubits form the register $Q \otimes (Q \otimes Q)$, the first qubit composed with the pair of the other two, and the qubits are numbered $1, 2, 3$ from the left.

A pure state $\lvert \psi \rangle$ of $S$ is a unit vector in the state space of $S$.^✦ A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$^✦, and each pure state $\lvert \psi \rangle$ determines the state $\lvert \psi \rangle\langle \psi \rvert$, the rank one projector onto it.^✦ The basis states $\lvert 0 \rangle$ and $\lvert 1 \rangle$ of the qubit are the pure states given by the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$.^✦ For pure states $\lvert \psi \rangle$ of $S$ and $\lvert \varphi \rangle$ of $T$, the product $\lvert \psi \rangle \otimes \lvert \varphi \rangle$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two^✦, and the computational basis of the register consists of the products $$\lvert q_1 q_2 q_3 \rangle = \lvert q_1 \rangle \otimes \bigl( \lvert q_2 \rangle \otimes \lvert q_3 \rangle \bigr), \qquad q_1, q_2, q_3 \in \{0, 1\}.$$(1)^✦

Gates

A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$^✦, where $1$ is the identity operator; it carries a pure state $\lvert \psi \rangle$ of $S$ to the pure state $U \lvert \psi \rangle$.^✦ For two unitaries $U$ and $V$ of $S$, the product $UV$ is the unitary that applies $V$ first and then $U$.^✦ A pure state $\lvert \psi \rangle$ of $S$ is an eigenstate of a unitary $U$ of $S$, with eigenvalue $\mu \in \mathbb{C}$, when $U \lvert \psi \rangle = \mu \lvert \psi \rangle$, and $U$ stabilizes $\lvert \psi \rangle$ when $\mu = 1$.^✦

The Pauli $X$ or quantum NOT, the Pauli $Z$ or phase flip, and the Hadamard $H$ are the unitaries of the qubit with 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}.$$(2)

For a unitary $U$ of $S$ and a unitary $V$ of $T$, the product unitary $U \otimes V$ of $S \otimes T$ is the one whose operator is the tensor product of the operators of $U$ and $V$.^✦ With the identity unitary $1$ in one of the two places it puts a gate on a single factor: $U \otimes 1$ applies $U$ to $S$ and leaves $T$ alone^✦, and $1 \otimes V$ applies $V$ to $T$.^✦ On the register a gate on one qubit carries that qubit’s number, $$X_1 = X \otimes 1, \qquad X_2 = 1 \otimes (X \otimes 1), \qquad Z_3 = 1 \otimes (1 \otimes Z),$$(3) and $H_1$ and $H_2$ are formed in the same way.

For a unitary $U$ of $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$, a control qubit followed by the target $S$, given by $$C(U) = \lvert 0 \rangle\langle 0 \rvert \otimes 1 + \lvert 1 \rangle\langle 1 \rvert \otimes U .$$(4)^✦ The CNOT gate is $C(X)$ on two qubits^✦, and $\mathrm{CNOT}_{23} = 1 \otimes \mathrm{CNOT}$ is the CNOT on qubits 2 and 3 of the register, with qubit 2 as control. Taking qubit 1 as control and the pair as target, $\mathrm{CNOT}_{13} = C(1 \otimes X)$ flips qubit 3 when qubit 1 is $\lvert 1 \rangle$^✦, and the controlled $Z$ on qubits 1 and 2, $\mathrm{CZ}_{12} = C(Z \otimes 1)$, takes $\lvert q_1 q_2 q_3 \rangle$ to $(-1)^{q_1 q_2} \lvert q_1 q_2 q_3 \rangle$.^✦ Iterated, the construction gives the doubly controlled gate $C^2(U) = C(C(U))$ of a unitary $U$ of the qubit, which applies $U$ to qubit 3 exactly when qubits 1 and 2 are both $\lvert 1 \rangle$^✦; the Toffoli gate is $C^2(X)$.^✦

The Ancilla and Its Stabilizers

The preparation circuit $\mathrm{Prep}$ is the unitary of the register that applies a Hadamard to each of qubits 1 and 2 and then the Toffoli gate^✦, and the ancilla is the pure state it makes from $\lvert 000 \rangle$: $$\mathrm{Prep} = \mathrm{Toffoli}\; H_1 H_2, \qquad \lvert \Theta_T \rangle = \mathrm{Prep}\, \lvert 000 \rangle .$$(5)^✦

The three gates of the exercise are the unitaries of the register $$g_1 = X_1\, \mathrm{CNOT}_{23},$$(6)^✦ $$g_2 = X_2\, \mathrm{CNOT}_{13},$$(7)^✦ $$g_3 = Z_3\, \mathrm{CZ}_{12}.$$(8)^✦

The Claim

What Is Checked

The claim is stated over the ancilla (5), the three gates (6), (7) and (8), the eigenstate condition with eigenvalue $1$, and the state $\lvert \psi \rangle\langle \psi \rvert$ of a pure state; the gates are built from (2), (3) and (4).

About these constructions the library proves that the operator (4) is unitary for every unitary $U$, $C(U)^\dagger C(U) = C(U) C(U)^\dagger = 1$^✦, and that the matrices (2) are unitary and so give unitaries of the qubit. A product of unitaries is unitary, both $UV$ and $U \otimes V$.