It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to split the output of a gate and direct each of the splits to other NAND gates (see the area circled in red): enter image description here

If we make the restriction that all gates are reversible (in particular, we require fixed input/output size), does the AND/NOT criterion still hold? Is the ability to "split" outputs (i.e., a gate that can do AND, NOT, and duplicate a $0$ or $1$, e.g. $(0,0,1) \rightarrow (0,1,1)$ ) a necessary/sufficient condition for universality?

  • 1
    $\begingroup$ Can you define all the concepts formally? When is a gate universal? When is it reversible? What is the ability to "split" outputs? As it stands, your question is quite vague, and it is likely that any answer will face a reply of the sort "I didn't mean that, let me change my question completely to invalidate your answer". $\endgroup$ Oct 1 '20 at 8:23
  • $\begingroup$ Some possibly relevant definitions appear in Mayr and Subramanian, The complexity of circuit value and network stability; also appeared in a journal, but beyond a paywall. $\endgroup$ Oct 1 '20 at 8:25
  • $\begingroup$ (The "split" has been called fan as in fan out for outputs. (fan in was the number of equivalent inputs.) Try something simpler first: What difference does limiting the fan-out (fan-in) to 2 make?) $\endgroup$
    – greybeard
    Oct 2 '20 at 6:17
  • $\begingroup$ Please check (0,0,1)→(0,1,1) - a single pair of (inputs, outputs) isn't enough to specify a bundle of boolean functions. $\endgroup$
    – greybeard
    Oct 2 '20 at 6:51

I'm not sure what you're asking, precisely, but it's certainly not true that a reversible universal gate requires the number of set bits in the output to be the same as in the input. Toffoli gates do not have that property, for example.


Thanks for the clarification. The answer to your question is that any reversible circuit must have at least as many output lines as input lines. As an exercise, prove this. Try using the pigeonhole principle.

So what happens if you need a reversible circuit with fewer output lines than input lines? You just add output lines, the values of which are irrelevant. The circuit still computes what you need it to, it also happens to compute more stuff that you don't care about.

So what I think you're asking about duplication is can there be more output bits than input bits? The answer is "kind of", and it comes down to what model of reversibility you care about.

Such a circuit can clearly be logically reversible. But can it be physically reversible? I'm not a hardware designer, and I don't know.

  • $\begingroup$ Sorry if I wasn't clear: I mean that there is a consistent $k$-bit input and $k$-bit output. Even though the number of set bits isn't the same in a Toffoli gate, we will always have 3 bits of output to deal with, and we can't arbitrarily split/duplicate wires/outputs. Interestingly, Toffoli gates can simulate splitting/duplication ($\operatorname{Toffoli}(x, 1, 0) = (x, 1, x)$), which supports my hypothesis that this might be required to be reversible and universal. $\endgroup$
    – actinidia
    Sep 30 '20 at 23:33
  • $\begingroup$ Oh, I see. I'll edit my answer. $\endgroup$
    – Pseudonym
    Sep 30 '20 at 23:47
  • 1
    $\begingroup$ If you need more outputs then you add extra inputs which have to be 0. $\endgroup$
    – user253751
    Oct 1 '20 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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