Realization and synthesis of reversible functions

Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n-bit reversible function, we present a constructive synthesis algorithm. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N <= 2(n), and the other (2(n) - N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2n . N '(n - 1)'-CNOT gates and 4n(2) . N NOT gates. The time and space complexities of the algorithm are Omega(n . 4(n)) and Omega(n . 2(n)), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms. (C) 2010 Elsevier B.V. All rights reserved.