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≤2n, and the other (2n−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 4n2⋅N NOT gates. The time and space complexities of the algorithm are Ω(n⋅4n) and Ω(n⋅2n), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.