  In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates
are studied. Several asymptotically optimal by the order of magnitude synthesis
methods are described. Some circuit's complexity reduction approaches are
considered. Implementation of discrete logarithm within a reversible circuit is
discussed. The main conclusion in the paper is that the usage of additional
inputs (additional memory) in reversible circuits almost always allow to reduce
their complexity, depth and weight.

Emerging Technologies