Reversible Computing - Reversible Circuits

Reversible Circuits

To implement reversible computation, estimate its cost, and to judge its limits, it is formalized it in terms of gate-level circuits. For example, the inverter (logic gate) (NOT) gate is reversible because it can be undone. The exclusive or (XOR) gate is irreversible because its inputs cannot be unambiguously reconstructed from an output value. However, a reversible version of the XOR gate --- the Controlled NOT gate(CNOT) --- can be defined by preserving one of the inputs. The three-input variant of the CNOT gate is called the Toffoli gate. It preserves two of its inputs a,b and replaces the third c by . With, this gives the AND function, and with this gives the NOT function. Thus, the Toffoli gate is universal and can implement any reversible Boolean function (given enough zero-initialized ancillary bits). More generally, reversible gates have the same number of inputs and outputs. A reversible circuit connects reversible gates without fanouts and loops. Therefore, such circuits contain equal numbers of input and output wires, each going through an entire circuit.

Reversible logic circuits have been first motivated in the 1960s by theoretical considerations of zero-energy computation as well as practical improvement of bit-manipulation transforms in cryptography and computer graphics. Since the 1980s, reversible circuits have attracted interest as components of quantum algorithms, and more recently in photonic and nano-computing technologies where some switching devices offer no signal gain.

Surveys of reversible circuits, their construction and optimization as well as recent research challenges is available.