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

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?

• 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". Oct 1, 2020 at 8:23
• 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. Oct 1, 2020 at 8:25
• (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?) Oct 2, 2020 at 6:17
• Please check (0,0,1)→(0,1,1) - a single pair of (inputs, outputs) isn't enough to specify a bundle of boolean functions. Oct 2, 2020 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.

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.

• 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. Sep 30, 2020 at 23:33
• Oh, I see. I'll edit my answer. Sep 30, 2020 at 23:47
• If you need more outputs then you add extra inputs which have to be 0. Oct 1, 2020 at 17:47

### "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.