For a logic gate to be universal, must it necessarily be able to perform duplication?

Question

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):

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?

Answer 1

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.

EDIT

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.

Answer 2

"AND NOT" Criterion

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?

Yes (well sort of).

Sort of, because AND is not reversible. To simulate it with a reversible circuit you would have to implement a function F such that F(q0,q1,q2) = (q0,q1, q0^q1 XOR q2) where qs are the input bits. q2 then must be restricted to be 0 to run a proper computation.

Yes, because every gate (whether reversible or irreversible) can be constructed from and and not. That implies all the subset of reversible gates can be constructed.

Splitting

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)→(0,1,1) ) a necessary/sufficient condition for universality?

It's neither necessary nor sufficient.

First, just wanted to clarify: For reversible computing, any particular function must be reversible. AND is not reversible, so you must adjust it (such as the F that I described above). This adjustment is a splitting of both inputs along with an XOR operation. Splitting alone will not make it reversible.

Once AND has been adjusted that way, AND + Not are (I think) universal. What makes me think that? The TOFFOLI gate

Splitting is Not necessary

The TOFFOLI gate is universal, reversible, and doesn't require any splitting operations.

Splitting is Not Sufficient

The Identity gate is not universal, no matter how many splittings you do.