Materials in quantum information often emphasize that one and two bit classical reversible gates cannot achieve universality for the classical reversible computation, whereas universal quantum computing can be achieved only using one or two qubits gates.
I want to understand why classical reversible computing cannot be achieved with only one and two bits classical reversible gates. I consulted with some of the materials, but all the materials I consulted with only 'illustrated' why it was difficult or seemed to be impossible to simulate some kinds of classical reversible gates only using one and two bits classical reversible gates, never giving a satisfactory clear mathematical proof as to that impossibility.
Specifically, I wonder if there is any mathematically clear proof for the claim that Toffoli gate cannot be achieved only using one and two bits classical reversible gates.
Thanks in advance.
The proof uses the fact that the Toffoli gate is non-affine, but all 1 and 2 bit classical reversible gates are affine. Here we go:
Definition: Let $B=F_2$=({0,1},+,$\cdot$) be the smallest field. The map $\theta_3: (x,y,z)\to (x,y,xy+z)$ where the vector $(x,y,z)\in B^3$, is called "Toffoli gate".
Lemma: Let $f:B^2\to B^2$ be bijective. Then f is affine, i.e. $\forall \mathbf{x}\in${0,1}$^2$, $f(\mathbf{x})$ satisfies $$ \phantom{texttexttext}f(\mathbf{x}) = \mathbf{M}\mathbf{x} +\mathbf{a} \phantom{texttexttext}(*), $$ where $\mathbf{a} \in B^2$ and $\mathbf{M} \in \mathrm{GL}_2(B)$, i.e. an invertible 2x2 matrix whose entries are from $B$.
Proof: There are $24=4!$ distinct bijective maps f. Now, there are also $24=4\times 6$ maps generated from () by the 4 distinct vectors $\mathbf{a}$ and 6 invertible 2x2 $B$-valued matrices $\mathbf{M}$. Now we only need to show that all 24 of these maps are indeed distinct, so we can conclude that all maps $f$ are of the form (). Assume $$ f=f' \Leftrightarrow f(\mathbf{x})=f'(\mathbf{x})\phantom{x} \forall \mathbf{x}\in B \Leftrightarrow (\mathbf{M}-\mathbf{M}')\mathbf{x} +(\mathbf{a}-\mathbf{a}') =0 \text{ } \forall \mathbf{x}\in B $$ Letting $\mathbf{x} =\mathbf{0}$, this implies that $\mathbf{a} = \mathbf{a}'$. Thus, upon substituting $\mathbf{x} = (0,1)$ and $\mathbf{x}=(1,0)$, it follows that $\mathbf{M}=\mathbf{M}' \text{ }\square$.
Remark: Any composition of affine functions is affine.
Corollary: The Toffoli gate is not affine since it may be written as $\theta_3 = id + \Delta$, where $\Delta(x,y,z)=(0,0,xy)$ and since $id $ is affine, the assumption that $\theta_3$ is affine leads to a contradiction because $\Delta$ isn't affine. Therefore, one cannot construct the Toffoli gate from 1 and 2 bit reversible classical gates $\square$.
This means that one and two bit reversible classical gates are not "universal", i.e. they're not a basis for arbitrary gates. Such a basis may however be constructed from generalised Toffoli gates (where "generalised" means that they may need to have auxiliary bits).