patternMinor
Universality of NOT and CNOT
Viewed 0 times
andcnotnotuniversality
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#6139, answer score: 4
Revisions (0)
No revisions yet.