Can the 0 gate be built as a circuit using only reversible gates? in other words, is there a classical circuit $C$ of width $n$ (unkown), built entirely from reversible gates, such that its first wire produces output 0 no matter what the input is?
The answer is no!
To see why, let’s look at the function computed by a reversible gate: let $G$ be a reversible gate of width $n$. This means that both the input and the output represent binary numbers with $n$ digits, that is, elements of $\{0,1\}^n$, and we let $$f_G:\{0,1\}^n \into \{0,1\}^n$$ be the function computed by $G$. The reversibility of $G$ implies that $f_G$ is injective.
Now let $C$ be any classical circuit with $n$ input wires and $m$ output wires, and let $$f_C:\{0,1\}^n \into \{0,1\}^m$$ be the function computed by $C$. In general, of course, the function $f_C$ is not injective; for instance, this is necessarily the case if $m < n$. However:
Lemma
If $C$ is built entirely from reversible circuits, then $m=n$ and $f_C$ is injective.
Proof. Let $k$ be the number of reversible gates used to build $C$; we proceed by induction on $k$.
If $k=0$, then the circuit does nothing to the input, so $f_C$ is the identity function; in particular, $f_C$ is injective. So we assume from now on that $k>0$ and that
- (IH)
- the lemma holds for any circuit $C’$ built from at most $k-1$ reversible circuits.
We list the gates used in the construction of $C$ as $G_1, \dots, G_k$ in the order that they appear in the circuit when moving from left to right.
Let now $C’$ be the circuit obtained from $C$ after removing the last gate $G_k$. Since $C’$ is built from $k-1$ reversible gates, the inductive hypothesis (IH) implies that the number of output wires of $C’$ is equal to $n$ and that the map $f_{C’}:\{0,1\}^n \into \{0,1\}^n$ is injective.
Let also $D$ be the part of the circuit $C$ to the right of $C’$. Then $D$ is a circuit whose input wires are the output wires of $C’$ and whose only gate is $G_k$. Some of these $n$ input wires are connected to the inputs of $G_k$, and for each of these there is a corresponding output wire of $G_k$. The input wires of $D$ that are not connected to $G_k$, on the other hand, simply run through $D$ without interference. Therefore, $D$ is a circuit built from 1 reversible gate with $n$ input wires. It follows again from the inductive hypothesis (IH) that $D$ has $n$ output wires and the map $f_D:\{0,1\}^n \into \{0,1\}^n$ is injective.
Since $D$ is the “rightmost” part of the circuit $C$, the output wires of $D$ are also the output wires of $C$. This means that $m=n$, which proves the first part of the lemma for $C$.
Moreover, since the output of $C’$ is the input of $D$, we have that $$f_C(x) = f_{D}(f_{C’}(x)), \quad\text{for } x \in \{0,1\}^n.$$ Since any composition of injective maps is injective, it follows that $f_C$ is injective, which proves the second part of the lemma for $C$. $\qed$
Now that we have proved the lemma, let’s get back to our question: the lemma implies that
Corollary
No circuit built from reversible gates can produce constant 0 output on any of its wires.
Proof. Let $C$ be a circuit of width $n$ built from reversible gates. By the lemma, the map $f_C$ is injective. Since the set $\{0,1\}^n$ has $2^n$ elements, the injectivity of $f_C$ implies that the image of $f_C$ also has at least $2^n$ elements. But the image of $f_C$ is again a subset of $\{0,1\}^n$, and the only $2^n$-element subset of $\{0,1\}^n$ is $\{0,1\}^n$ itself. In other words, $f_C$ is also surjective.
This means that every possible output is obtained as we vary the inputs; in particular, for each output wire we can find inputs $x_1$ and $x_2$ in $\{0,1\}^n$ such that this particular wire has value 0 in the output $f_C(x_1)$, but value 1 in the output $f_C(x_2)$. $\qed$
The upshot of all this? Any universal set of gates will have to contain at least one non-reversible gate. The smallest universal set of gates containing the Toffoli gate $\mathbf{T}$ is therefore $\{\mathbf{1},\mathbf{T}\}$: with $\mathbf{1}$ and $\mathbf{T}$, we can build the NOT gate, and with $\mathbf{1}$ and NOT we can build $\mathbf{0}$; and we already know $\{\mathbf{0}, \mathbf{1}, \mathbf{T}\}$ to be universal.