Past exam of the laser science and quantum information processing course of the University of Oxford / 2015 / 6 / a

Use a classical target bit $t$ and initialized auxiliary bits. The NOT gate maps $t\mapsto 1\oplus t$, the CNOT gate maps $(a,t)\mapsto (a,t\oplus a)$, and the Toffoli gate maps $(a,b,t)\mapsto (a,b,t\oplus ab)$. They are bijections and are their own inverses. Explicit circuits with their retained input wires are:

These maps also give the truth tables for all input combinations. AND and OR are not themselves reversible maps if the inputs are discarded; the retained inputs are what make their implementations reversible. Classical CLONE copies a known orthogonal computational basis alphabet; the no-cloning theorem forbids interpreting it as a copier of arbitrary quantum superpositions.

A Boolean circuit can express any finite Boolean function using AND, OR and NOT. Replace its operations by the reversible versions, keeping inputs and intermediate bits. Copy the final output into a fresh answer register with CNOT gates, then run the entire computing network backward. Intermediate auxiliary bits return to zero, yieldingThis compute-copy-uncompute construction proves universality in the usual model with initialized auxiliary bits. If $f$ is a reversible permutation, compute $f(x)$, use a reversible implementation of $f^{-1}$ to clear $x$, and swap registers, leaving $f(x)$ with clean auxiliaries. The ancillary-resource qualification matters; a blanket claim about all permutations on an arbitrary fixed number of unassisted wires has parity restrictions.