Universal Reversible Logic Gates

The question which Landauer failed to ask in 1961 [land61] and which was answered first by Bennett in 1973 [benu73] and later, independently, by Predkin [fredkiu82], is whether irreversible logic gates are essential to computation. Might it be possible to construct a universal set out of reversible gates ... 

Consider a logic gate with 3-iiiput and 3-output lines. Edward Fredkin, motivated by a deep conviction in a fundamental connection between a discrete, finite physics and reversible computation [wrightSS], discovered a simple universal 3-input/ 3-output logic function that now bears his name [fredkin82]. 

When used together, the three gates NOT, CONTROLLED NOT and CONTROLLED CONTROLLED NOT constitute a universal reversible set, and can thus be used to construct an arbitrary logical circuit. 

Obviously that B and C can be recovered by applying the gate to B and C. Tha-efore, the gate is reversible. Fredkin gate can be used to built an universal set of classical logic gates. 

Note that since the Fredkin-Toffoli gate is reversible and all the states are normalized, U(l) is unitary. Other universal gates like the NAND-gate which is common in classical logic are not reversible. As a consequence, they cannot be described by a unitary matrix and are not directly realizable by quantum means. 

---