The Toffoli gate (controlled-controlled-NOT) is a 3-qubit gate, and here it will be shown how to implement it with 2-qubit gates. The construction is given by the following quantum circuit.
Here, the unitary gate $V$ is given by
\[
V=\frac{1}{\sqrt{2}}\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}
\]
where $\omega=e^{i\pi/4}$ and $\overline{\omega}=e^{-i\pi/4}$ is the complex conjugate of $\omega$, and thus
\[
V^{\dagger}=V^{-1}=\frac{1}{\sqrt{2}}\begin{pmatrix}
\overline{\omega} & \omega \\
\omega & \overline{\omega}
\end{pmatrix}
\]
Consider the product of $V$ with itself:
\[
V^2=\frac{1}{2}\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}
\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}=
\frac{1}{2}\begin{pmatrix}
\omega^2+\overline{\omega}^2 & \omega\overline{\omega}+\overline{\omega}\omega \\
\overline{\omega}\omega+\omega\overline{\omega} & \overline{\omega}^2+\omega^2
\end{pmatrix}.
\]
Now
\[\begin{align*}
\omega^2+\overline{\omega}^2=& e^{i\pi/2}+e^{-i\pi/2}=i-i=0 \\
\overline{\omega}^2+\omega^2=& e^{-i\pi/2}+e^{i\pi/2}=-i+i=0 \\
\omega\overline{\omega}+\overline{\omega}\omega=&e^{i\pi/4}e^{-i\pi/4}+e^{-i\pi/4}e^{i\pi/4}=1+1=2 \\
\overline{\omega}\omega+\omega\overline{\omega}=&e^{-i\pi/4}e^{i\pi/4}+e^{i\pi/4}e^{i\pi/4}=1+1=2,
\end{align*}\]
and therefore
\[
V^2=
\frac{1}{2}\begin{pmatrix}
\omega^2+\overline{\omega}^2 & \omega\overline{\omega}+\overline{\omega}\omega \\
\overline{\omega}\omega+\omega\overline{\omega} & \overline{\omega}^2+\omega^2
\end{pmatrix}=
\frac{1}{2}\begin{pmatrix}
0&2\\
2&0
\end{pmatrix}
=\begin{pmatrix}
0&1\\
1&0
\end{pmatrix}
=X.
\]
Let $\ket{\psi}=\alpha\ket{0}+\beta\ket{0}$ be an arbitrary 1-qubit state. Note that $VV^{\dagger}=V^{\dagger}V=I$, and that $VV=X$ as shown in (a). Consider how the circuit maps the following states:
\[\begin{align*}
\ket{00}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{00}\ket{\psi}\overset{c_1X_2}\mapsto\ket{00}\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{00}\ket{\psi}\overset{c_1X_2}\mapsto\ket{00}\ket{\psi}\overset{c_2V_3}\mapsto\ket{00}\ket{\psi}=\ket{00}\ket{\psi} \\
\ket{01}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{01}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{01}V\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{01}V^{\dagger}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{01}V^{\dagger}V\ket{\psi}\overset{c_2V_3}\mapsto\ket{01}V^{\dagger}V\ket{\psi}=\ket{01}\ket{\psi}\\
\ket{10}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{10}\ket{\psi}\overset{c_1X_2}\mapsto\ket{11}\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{11}V^{\dagger}\ket{\psi}\overset{c_1X_2}\mapsto\ket{10}V^{\dagger}\ket{\psi}\overset{c_2V_3}\mapsto\ket{10}VV^{\dagger}\ket{\psi}=\ket{10}\ket{\psi} \\
\ket{11}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{11}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{10}V\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{10}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{11}\ket{\psi}\overset{c_2V_3}\mapsto\ket{11}VV\ket{\psi}=\ket{11}X\ket{\psi}
\end{align*}
\]
For each of the four mappings calculated in part (b), observe how $\ket{ab}\ket{\psi}$ is mapped in the two cases where $\ket{\psi}$ is either of the basis states $\ket{0}$ or $\ket{1}$. Since the action is trivially $\ket{ab}\ket{\psi}\mapsto\ket{ab}\ket{\psi}$ in all cases where both $ab$ is $11$, it follows that $\ket{ab}\ket{c}\mapsto\ket{ab}\ket{c}$ for all $ab\in\{00,01,10\}$ and $c\in\{0,1\}$. However, in the case where $ab=11$, and $c\in\{0,1\}$ it is seen that
\[\begin{align*}
\ket{11}\ket{0}\mapsto&\ket{11}X\ket{0}=\ket{11}\ket{1},\\
\ket{11}\ket{1}\mapsto&\ket{11}X\ket{1}=\ket{11}\ket{0}.
\end{align*}\]
Therefore, the circuit leaves the states unchanged unless the first two qubits in the register are in the state $\ket{11}$, in which case the third qubit in the register is flipped to the opposite bit value. By thinking of each of these eight resulting states as column vectors, the matrix representation of the circuit, $T$ can be constructed by making each column of the matrix correspond to the vector that represents the resulting state under the circuit mapping as follows:
\[
T=\begin{pmatrix}
1&0&0&0&0&0&0&0 \\
0&1&0&0&0&0&0&0 \\
0&0&1&0&0&0&0&0 \\
0&0&0&1&0&0&0&0 \\
0&0&0&0&1&0&0&0 \\
0&0&0&0&0&1&0&0 \\
0&0&0&0&0&0&0&1 \\
0&0&0&0&0&0&1&0 \\
\end{pmatrix}.
\]
Here, the unitary gate $V$ is given by
\[
V=\frac{1}{\sqrt{2}}\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}
\]
where $\omega=e^{i\pi/4}$ and $\overline{\omega}=e^{-i\pi/4}$ is the complex conjugate of $\omega$, and thus
\[
V^{\dagger}=V^{-1}=\frac{1}{\sqrt{2}}\begin{pmatrix}
\overline{\omega} & \omega \\
\omega & \overline{\omega}
\end{pmatrix}
\]
Consider the product of $V$ with itself:
\[
V^2=\frac{1}{2}\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}
\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}=
\frac{1}{2}\begin{pmatrix}
\omega^2+\overline{\omega}^2 & \omega\overline{\omega}+\overline{\omega}\omega \\
\overline{\omega}\omega+\omega\overline{\omega} & \overline{\omega}^2+\omega^2
\end{pmatrix}.
\]
Now
\[\begin{align*}
\omega^2+\overline{\omega}^2=& e^{i\pi/2}+e^{-i\pi/2}=i-i=0 \\
\overline{\omega}^2+\omega^2=& e^{-i\pi/2}+e^{i\pi/2}=-i+i=0 \\
\omega\overline{\omega}+\overline{\omega}\omega=&e^{i\pi/4}e^{-i\pi/4}+e^{-i\pi/4}e^{i\pi/4}=1+1=2 \\
\overline{\omega}\omega+\omega\overline{\omega}=&e^{-i\pi/4}e^{i\pi/4}+e^{i\pi/4}e^{i\pi/4}=1+1=2,
\end{align*}\]
and therefore
\[
V^2=
\frac{1}{2}\begin{pmatrix}
\omega^2+\overline{\omega}^2 & \omega\overline{\omega}+\overline{\omega}\omega \\
\overline{\omega}\omega+\omega\overline{\omega} & \overline{\omega}^2+\omega^2
\end{pmatrix}=
\frac{1}{2}\begin{pmatrix}
0&2\\
2&0
\end{pmatrix}
=\begin{pmatrix}
0&1\\
1&0
\end{pmatrix}
=X.
\]
Let $\ket{\psi}=\alpha\ket{0}+\beta\ket{0}$ be an arbitrary 1-qubit state. Note that $VV^{\dagger}=V^{\dagger}V=I$, and that $VV=X$ as shown in (a). Consider how the circuit maps the following states:
\[\begin{align*}
\ket{00}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{00}\ket{\psi}\overset{c_1X_2}\mapsto\ket{00}\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{00}\ket{\psi}\overset{c_1X_2}\mapsto\ket{00}\ket{\psi}\overset{c_2V_3}\mapsto\ket{00}\ket{\psi}=\ket{00}\ket{\psi} \\
\ket{01}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{01}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{01}V\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{01}V^{\dagger}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{01}V^{\dagger}V\ket{\psi}\overset{c_2V_3}\mapsto\ket{01}V^{\dagger}V\ket{\psi}=\ket{01}\ket{\psi}\\
\ket{10}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{10}\ket{\psi}\overset{c_1X_2}\mapsto\ket{11}\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{11}V^{\dagger}\ket{\psi}\overset{c_1X_2}\mapsto\ket{10}V^{\dagger}\ket{\psi}\overset{c_2V_3}\mapsto\ket{10}VV^{\dagger}\ket{\psi}=\ket{10}\ket{\psi} \\
\ket{11}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{11}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{10}V\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{10}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{11}\ket{\psi}\overset{c_2V_3}\mapsto\ket{11}VV\ket{\psi}=\ket{11}X\ket{\psi}
\end{align*}
\]
For each of the four mappings calculated in part (b), observe how $\ket{ab}\ket{\psi}$ is mapped in the two cases where $\ket{\psi}$ is either of the basis states $\ket{0}$ or $\ket{1}$. Since the action is trivially $\ket{ab}\ket{\psi}\mapsto\ket{ab}\ket{\psi}$ in all cases where both $ab$ is $11$, it follows that $\ket{ab}\ket{c}\mapsto\ket{ab}\ket{c}$ for all $ab\in\{00,01,10\}$ and $c\in\{0,1\}$. However, in the case where $ab=11$, and $c\in\{0,1\}$ it is seen that
\[\begin{align*}
\ket{11}\ket{0}\mapsto&\ket{11}X\ket{0}=\ket{11}\ket{1},\\
\ket{11}\ket{1}\mapsto&\ket{11}X\ket{1}=\ket{11}\ket{0}.
\end{align*}\]
Therefore, the circuit leaves the states unchanged unless the first two qubits in the register are in the state $\ket{11}$, in which case the third qubit in the register is flipped to the opposite bit value. By thinking of each of these eight resulting states as column vectors, the matrix representation of the circuit, $T$ can be constructed by making each column of the matrix correspond to the vector that represents the resulting state under the circuit mapping as follows:
\[
T=\begin{pmatrix}
1&0&0&0&0&0&0&0 \\
0&1&0&0&0&0&0&0 \\
0&0&1&0&0&0&0&0 \\
0&0&0&1&0&0&0&0 \\
0&0&0&0&1&0&0&0 \\
0&0&0&0&0&1&0&0 \\
0&0&0&0&0&0&0&1 \\
0&0&0&0&0&0&1&0 \\
\end{pmatrix}.
\]
