Realization and synthesis of reversible functions

Abstract: Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any -bit reversible function, we present a constructive synthesis algorithm. Given any -bit reversible function, there are distinct input patterns different from their corresponding outputs, where , and the other input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most ‘’-CNOT gates and NOT gates. The time and space complexities of the algorithm are and , respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms. [Copyright &y& Elsevier]