The Exercise

The Toffoli gate acts on three qubits. It flips the third qubit, the target, exactly when the first two, the controls, are both $\lvert 1 \rangle$.^✦ The exercise is to show that a circuit of seven gates implements the Toffoli gate up to relative phases: four rotations of the target about the $y$ axis, by angles $\pm\pi/4$, alternating with three controlled NOT (CNOT) gates whose target is the third qubit. The library states this for each computational basis input in turn.

Three Qubits

A quantum system $S$ is a physical system described by its state space, a finite dimensional complex Hilbert space.^✦ Two systems $A$ and $B$ form the composite system $A \otimes B$, whose state space is the tensor product of theirs.^✦ The qubit $Q$ is the two level system with state space $\mathbb{C}^2$, and three qubits form the composite system $Q \otimes (Q \otimes Q)$.

A pure state $\lvert\psi\rangle$ of a system $S$ is a unit vector in the state space of $S$.^✦ For pure states $\lvert\psi\rangle$ of $A$ and $\lvert\varphi\rangle$ of $B$, the product state $\lvert\psi\rangle \otimes \lvert\varphi\rangle$ is the pure state of $A \otimes B$ whose vector is the tensor product of the two vectors.^✦ The basis states $\lvert 0 \rangle$ and $\lvert 1 \rangle$ of the qubit are the pure states given by the standard basis vectors $(1, 0)$ and $(0, 1)$ of $\mathbb{C}^2$.^✦ For bits $q_1$, $q_2$ and $q_3$, the basis state of three qubits is the product $$\lvert q_1 q_2 q_3 \rangle = \lvert q_1 \rangle \otimes \bigl( \lvert q_2 \rangle \otimes \lvert q_3 \rangle \bigr),$$(1)^✦ and the eight of them form the computational basis of the three qubits.

Two pure states $\lvert\psi\rangle$ and $\lvert\varphi\rangle$ of $S$ differ by a relative phase with respect to a family of pure states $\lvert e_k \rangle$ of $S$, such as an orthonormal basis, if for every index $k$ there is a real number $\theta_k$, which may depend on $k$, with $\langle e_k \vert \psi \rangle = e^{i\theta_k} \langle e_k \vert \varphi \rangle$.^✦

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 $\lvert\psi\rangle$ of $S$ to the pure state $U \lvert\psi\rangle$. The composite $UV$ of unitaries $U$ and $V$ of $S$ is the unitary of $S$ that applies first $V$ and then $U$.^✦ For unitaries $U$ of $A$ and $V$ of $B$, the product unitary $U \otimes V$ is the unitary of $A \otimes B$ whose operator is the tensor product of theirs.^✦ For a system $A$ and a unitary $V$ of $B$, the unitary $1 \otimes V$ of $A \otimes B$, with the identity $1$ of $A$ as first factor, applies $V$ to $B$ and leaves $A$ alone.^✦

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$, with the qubit as control and $S$ as target, whose operator is $$C(U) = \lvert 0 \rangle\langle 0 \rvert \otimes 1 + \lvert 1 \rangle\langle 1 \rvert \otimes U .$$(2)^✦ For a unitary $U$ of the qubit, the doubly controlled gate $C^2(U) = C(C(U))$ is the unitary of three qubits in which the first qubit controls the two qubit gate $C(U)$ on the other two.^✦

The Pauli matrices are $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix},$$(3) and the Pauli $X$ gate, the quantum NOT, is the unitary of the qubit whose matrix in the basis $\lvert 0 \rangle$, $\lvert 1 \rangle$ is $X$. For a real vector $\vec{n} = (n_x, n_y, n_z)$ and a real angle $\theta$, the rotation $R_{\vec n}(\theta)$ is the $2 \times 2$ matrix built from the Pauli matrices (3) as $$R_{\vec n}(\theta) = \exp\Bigl( -\frac{i\theta}{2}\, \vec{n} \cdot \vec{\sigma} \Bigr), \qquad \vec{n} \cdot \vec{\sigma} = n_x X + n_y Y + n_z Z ,$$(4)^✦ written $R_{\hat n}(\theta)$ when the axis is a unit vector $\hat{n}$. For the unit vector $\hat{y} = (0, 1, 0)$, the rotation $R_{\hat y}(\theta) = R_y(\theta) = e^{-i\theta Y/2}$ is the rotation about the $y$ axis, and the $y$ rotation gate is the unitary of the qubit with matrix $R_y(\theta)$.

The Circuit

The Toffoli gate $T$ is the unitary $C^2(X)$ of three qubits, the doubly controlled NOT.^✦ The CNOT gate is the unitary $C(X)$ of two qubits, with the first as control; in the circuit $1 \otimes \mathrm{CNOT}$ acts on the second and third qubits.^✦ The CNOT from the first qubit to the third is $\mathrm{CNOT}_{13} = C(1 \otimes X)$, in which the first qubit controls the Pauli $X$ on the third and the second is left alone.^✦ A rotation of the third qubit alone is $R_3(\theta) = 1 \otimes \bigl( 1 \otimes R_y(\theta) \bigr)$.^✦ The relative phase Toffoli circuit $\tilde{T}$ is the product $$\tilde{T} = R_3(-\tfrac{\pi}{4})\, (1 \otimes \mathrm{CNOT})\, R_3(-\tfrac{\pi}{4})\, \mathrm{CNOT}_{13}\, R_3(\tfrac{\pi}{4})\, (1 \otimes \mathrm{CNOT})\, R_3(\tfrac{\pi}{4}),$$(5)^✦ a unitary of three qubits.

The Claim

What Is Checked

The claim is stated over two unitaries of three qubits, the circuit $\tilde{T}$ of (5) and the Toffoli gate $T = C^2(X)$, applied to the basis states (1) and compared by the relation of a relative phase in the computational basis.

The library proves that the controlled gate $C(U)$ of (2) is unitary for every unitary $U$, and that the matrices $X$ and $R_y(\theta)$ are unitary. Composites and tensor products of unitaries are again unitary. A unitary takes a pure state to a unit vector, since it preserves norms, and the product of two pure states is a unit vector, since the norm of a product vector is the product of the norms.