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).

  • $\begingroup$ This is exactly what I was looking for. Thanks! $\endgroup$ – Guldam Apr 18 '16 at 21:55
  • $\begingroup$ I'm glad you found my answer helpful. I don't know how this bounty system works. If you accepted my answer, would that automatically mean that you award me the bounty? $\endgroup$ – Cyclone Apr 19 '16 at 12:54
  • $\begingroup$ I don't know neither, too.. $\endgroup$ – Guldam Apr 19 '16 at 19:44
  • $\begingroup$ math.stackexchange.com/help/privileges/set-bounties "How do I award the bounty? You can award a bounty by clicking on the respective button below the upvote/downvote interface. ... You can accept an answer without awarding a bounty to it." $\endgroup$ – Chris Culter Apr 20 '16 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.