 Solution

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: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\cdot 6=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.