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 @W(n@?4^n) and @W(n@?2^n), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.
['Guowu Yang', 'Fei Xie', 'William N. N. Hung', 'Xiaoyu Song', 'Marek A. Perkowski']
Realization and synthesis of reversible functions