A Fast Transformation-Based Synthesis Algorithm for Reversible Circuits

In this paper, a simple and fast algorithm for the synthesis of reversible circuits is presented. This algorithm considers the synthesis process as a kind of sorting problem, generating a reversible circuit composed of CNOT-based gates. We prove that the proposed algorithm converges for any given specification. The empirical results of realizing examples discussed in the literature are reported. The results show that the algorithm leads to a near optimum solution for all 3*3 specifications and very good results for other larger specifications in much fewer steps compared to the search based and other previous algorithms.