Fix a number $n$ of qubits. In this post, we show how to build the Toffoli gates $T^{|k\rangle}_{|l\rangle}$ out of 1-gates and the CNOT gate. When combined with this post, we conclude that the set of 1-gates together with CNOT form a universal set of quantum gates.
Since $T^{|k\rangle}_{|l\rangle}$ is built from the Pauli gate $X$ and the Toffoli gates $T^{(n)}_k$ (as in Figure 2), it is enough to show that each $T^{(n)}_k$ can be built from CNOT and 1-gates. By the symmetry of wire switching, it is therefore even enough to show that each Toffoli $n$-gate (see the figure for $n=4$) can be built from CNOT and 1-gates.
Lemma 1
If $n \ge 4$, there is a quantum circuit, with $n-3$ ancillary qubits and consisting only of Toffoli 3-gates, to compute the Toffoli $n$-gate.
Proof. One verifies, by computing the outputs for each computational basis state input, that the following circuit computes the Toffoli 4-gate:
If $n > 4$, we insert after the first Toffoli 3-gate another Toffoli 3-gate with control qubits $|i_3\rangle$ and the first ancillary qubit, and with target qubit the second ancillary qubit; and if $n > 5$, we insert after the last one another Toffoli 3-gate with control qubits $|i_4\rangle$ and the second ancillary qubit, and with target qubit the third ancillary qubit; etc. The last Toffoli 3-gate is the one with control qubits $|i_{n-1}\rangle$ and the last ancillary qubit, and with target qubit $|i_n\rangle$. $\qed$
By Lemma 1, we only need to build the Toffoli 3-gate from CNOT and 1-gates.
Lemma 2
Let $U$ be a 1-gate. Then we can build the 3-gate c-c-$U^2$ using only 1-gates and CNOT.
Proof. One verifies, by computing the outputs for each computational basis state input, that the following circuit computes c-c-$U^2$:
By Corollary 4.2.1 of the book, both c-$U$ and c-$U^\dagger$ can, in turn, be built using only 1-gates and CNOT. This proves the lemma. $\qed$
Lemma 3
There exists a 1-gate $U$ such that $U^2 = X$.
Proof. Direct computation shows that we can take $U = \frac12\begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \end{pmatrix}$. $\qed$
We denote the 1-gate obtained in Problem 11 as $\sqrt{X}$. Since the Toffoli 3-gate is just c-c-$X$, we conclude:
Corollary
The Toffoli 3-gate can be built using $\sqrt{X}$ and CNOT. $\qed$
Combining the corollary with Lemma 1 and this post, we have now proved the following special case of Theorem 4.4.3 of the book:
Theorem
Every $n$-gate can be built from 1-gates and CNOT. $\qed$