# Prove that it is impossible to construct the toffoli gate using only CNOT gates

Show that it is not possible to construct the toffoli gate using only CNOT gates, given we are allowed to choose any number of ancilla bits.

My Attempt

The action of a toffoli gate can be defined as,

\begin{align} f_{toffoli}:(x,y,z)= &(x,y,z\oplus xy)\\ =&(x,y,z\overline{xy}\vee\bar{z}xy)\\ =&(x,y,z(\bar{x}\vee\bar{y})\vee\bar{z}xy)\\ =&(x,y,z\bar{x}\vee z\bar{y}\vee\bar{z}xy) \end{align}

Therefore, the simulation of the toffoli gate requires the CNOT gate to carry out AND, OR, and NOT operations.

The action of a CNOT gate produces, $$f_{cnot}:(x,y)\to (x,x\oplus y)$$. Hence, the possible operations achievable by CNOT gate along with ancilla bits are

\begin{align} f_{cnot}(x,y)&=(x,x\oplus y)=(x\bar{y}\vee \bar{x}y)\\ f_{cnot}(x,0)&=(x,x)\\ f_{cnot}(x,1)&=(x,\bar{x}) \end{align}

A NOT gate can be created using CNOT gate, whilist AND gate cannot be created using CNOT gate alone. Since OR gate can be decomposed of AND and NOT gates, the inability to construct AND gate with CNOT gate alone proves that toffoli gate cannot be constructd using CNOT gates even with ancilla bits.

Is it a complete and concrete proof? or is there a better way to prove it?

• No, this is not complete because there might be a very complicated method to simulate toffoli without the OR gate. You need to find an invariant to rule that out. Feb 11 at 14:15

Study the gates as functions over the field GF(2), where XOR is addition and AND is multiplication.

All of the bits of the CNOT gate are linear functions of the input.

The Toffoli gate has an output bit with the non-linear term $$xy$$.

Since all combinations of linear functions are themselves linear, you can conclude you can not construct the Toffoli gate from the CNOT gate.

• What if allow additional ancilla bits ? Feb 11 at 22:03
• @SoorajS Irrelevant. You still can't construct $xy$ since it's a non-linear term.
– orlp
Feb 12 at 18:14
• Could you please elaborate this a bit more as I am not that much familiar with this kind of approach to logic gates. Feb 14 at 3:40