= Solution
{c}
An <AND gate> maps four possible pairs to one bit and loses information, so it is not reversible. A reversible embedding retains both inputs and uses a target bit:
$$
\boxed{(a,b,c)\longmapsto(a,b,c\oplus ab).}
$$
This is the <Toffoli gate>; initializing $c=0$ computes $ab$ while preserving enough information to invert the operation.
Classical reversible gates on one or two bits alone cannot synthesize every such operation. Every permutation of two bits is an invertible affine map over the <finite field> $\mathbb F_2$: there are $4\cdot|\mathrm{GL}(2,2)|=4\cdot6=24$ of them, exactly the $4!$ permutations. Their extensions to a larger register and their compositions remain affine. The nonlinear term $ab$ in the <Toffoli gate> therefore cannot be generated. Three-bit reversible gates remove this obstruction, with ancillary bits initialized appropriately.
There is no conflict with quantum universality: one- and two-<qubit> gates may pass through <quantum superpositions> and use relative <phases> at intermediate steps. They are not restricted to permutations of computational <basis> states at every step. For example the <Hadamard gate>, <T gate> and <CNOT gate> can decompose a <Toffoli gate> exactly. Thus the classical affine obstruction does not apply to their intermediate <unitary operators>.
Back to article page
