= Solution
Allow clean workspace bits, as in standard <reversible computation>. <Boolean algebra> expresses any <Boolean function> as XORs of ANDs and constants. A <Toffoli gate> maps $(a,b,c)$ to $(a,b,c\oplus ab)$, so an initially zero target computes an <logical conjunction>[AND] without erasing the inputs. A <CNOT gate> accumulates XORs, and a <Pauli X gate>[NOT gate] supplies complemented bits or constants. Intermediate products can be computed into workspace, XORed into an output, and then <uncomputation>[uncomputed] by reversing the workspace computation. This realizes the reversible embedding $(x,y)\mapsto(x,y\oplus f(x))$ for any <Boolean function> and, with reversible clean-up, universal reversible classical computation.
The <Fredkin gate>[Fredkin] transformation has control $a$ and targets $b,c$. A network of three gates, shown in <4/b/i>, is
$$
\boxed{\operatorname{CNOT}_{b\to c}\ ;\quad
\operatorname{Toffoli}_{a,c\to b}\ ;\quad
\operatorname{CNOT}_{b\to c},}
$$
where the sequence is executed left to right. After the first gate $c_1=c\oplus b$; after the second $b_1=b\oplus a(c\oplus b)$; and the last gives $c_2=c\oplus b\oplus b_1$. If $a=0$, $(b_1,c_2)=(b,c)$; if $a=1$, $(b_1,c_2)=(c,b)$. Thus the circuit is exactly a <Fredkin gate>.
The workspace qualification matters for the unrestricted universality claim. On four or more wires, every embedded NOT, <CNOT gate>[CNOT] and <Toffoli gate> is an even permutation of all computational states. Without <ancilla>[ancillary wires] they cannot implement, for example, a permutation swapping just $0000$ and $0001$ while fixing the other four-bit strings. Clean <ancilla>[ancillas] remove this obstruction on the designated input subspace.
Back to article page
