[Solved]: Universality of NOT and CNOT

Problem Detail: 

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.

Asked By : bambinoh

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6139

3.2K people like this

 Download Related Notes/Documents