4
$\begingroup$

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.

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented Oct 18, 2012 at 1:07
  • 3
    $\begingroup$ CNOT = XOR? I believe the OP means quantum-gates (otherwise, why mention Toffoli gate?) $\endgroup$
    – Ran G.
    Commented Oct 18, 2012 at 2:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – bambinoh
    Commented Oct 18, 2012 at 4:30
  • 1
    $\begingroup$ @bambinoh So your challenge now is to find a bijective function which isn't linear. $\endgroup$
    – Yuval Filmus
    Commented Oct 18, 2012 at 13:47
  • 1
    $\begingroup$ Such as the Toffoli gate; since that gives me x + yz? Thanks :) $\endgroup$
    – bambinoh
    Commented Oct 18, 2012 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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