Abstract:
We discussed simple properties of the reversible computing model. In this model, only reversible operations are allowed. A reversible circuit consists of preparing input bits and working bits (ancillaries), a sequence of reversible gates over the bits, and finally forgetting the garbage and reading the output. Any Boolean circuit can be efficiently rewritten as an equivalent reversible circuit, with the size and depth of the circuit increasing by no more than a constant factor, and possibly requiring the use of a constant amount of additional memory. The Toffoli gate is universal in the class of reversible computations; it can be used to implement arbitrary permutations of bit strings, while some reversible functions require an exponential number of Toffoli gates.
