# Universality of NOT and CNOT

I'm trying to figure out why NOT and CNOT gates are not sufficient to create all bijective functions in classical circuits. I have been struggling on this for hours, and just can't make sense of it.

I feel it has something to do with the Toffoli gate, as it contains an (implicit) AND operation, and I feel that's what missing in the NOT and CNOT gates. However I can't find a proper way to actually 'show' this.

• It would be helpful if you could explain that CNOT is the same as XOR. – Yuval Filmus Oct 17 '12 at 23:32
• does this question shed some light? – Ran G. Oct 18 '12 at 2:55
• Assuming CONT = XOR... A XOR A = NOT A, so basically this is the same as asking why XOR isn't sufficient. – Danny Varod Oct 18 '12 at 18:49

## 1 Answer

Edit: This is a proof for the non-quantum version.

Suppose we want to compute $x \land y$ from $x,y,0,1$ using the operations NOT and CNOT (=XOR). Prove by induction that any such expression is equal to one of the following forms: $$0,1,x,y,\lnot x, \lnot y, x\oplus y, \lnot(x\oplus y).$$ It is more helpful to write it in the form $\alpha \oplus (\beta \land x) \oplus (\gamma \land y)$, where $\alpha,\beta,\gamma \in \{0,1\}$. Yet more helpful is to switch notation so that this expression is written $\alpha + \beta x + \gamma y$; this should be suggestive enough.

• Another way to see what Yuval is claiming is that negations can be "pulled out" of exclusive or, so you can bunch them all in the front, where they cancel each other in pairs. You are then left with a possible negation of a large xor. Then you can simplify the xor easily. – Andrej Bauer Oct 18 '12 at 1:07
• CNOT = XOR? I believe the OP means quantum-gates (otherwise, why mention Toffoli gate?) – Ran G. Oct 18 '12 at 2:17
• Thanks for your reply, I'm still not seeing it though. For one you suggest to prove that you can't compute x&y, but that's not a bijection, whereas the question states that it's about bijective functions... I am talking about classical circuits btw, not quantum ones From what you wrote it seems reasonable to assume that any combination of NOT and CNOT can never get you x&y (it can only get you linear combinations of x,y) ; but that's not a bijection so that doesn't really answer the question. Right? – bambinoh Oct 18 '12 at 4:30
• @bambinoh So your challenge now is to find a bijective function which isn't linear. – Yuval Filmus Oct 18 '12 at 13:47
• Such as the Toffoli gate; since that gives me x + yz? Thanks :) – bambinoh Oct 18 '12 at 18:20