Fast synthesis of exact minimal reversible circuits using group theory

ABSTRACT

We present fast algorithms to synthesize exact minimal reversible circuits for various types of gates and costs. By reducing reversible logic synthesis problems to group theory problems, we use the powerful algebraic software GAP to solve such problems. Our algorithms are not only able to minimize for arbitrary cost functions of gates, but also orders of magnitude faster than the existing approaches to reversible logic synthesis. In addition, we show that the Peres gate is a better choice than the standard Toffoli gate in libraries of universal reversible gates.

REFERENCES

• 1: T. Toffoli, Reversible computing, Tech. Memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980.
• 2: A. De Vos, B. Raa and L. Storme, "Generating the group of reversible logic gates," Journal of Physics A: Mathematical and General, 35, (2002), pages 7063--7078.
• 3: M. Perkowski, M. Lukac, M. Pivtoraiko, P. Kerntopf, M. Folgheraiter, "A hierarchical approach to computer aided design of quantum circuits," 6th International Symposium on Representations and Methodology of Future Computing Technology, pp. 201--209, Trier, Germany, March 2003.
• 4: D. Michael Miller , Dmitri Maslov , Gerhard W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775915]
• 5: L. Storme et al, "Group theoretical aspects of reversible logic gates," Journal of Universal Computer Science, 5 (1999), pp. 307--321.
• 6: J. D. Dixon, and B. Mortimer, Permutation Groups, Springer, New York, 1996.
• 7: M. I. Kargapolov, and Ju. I. Merzljakov, Fundamentals of the Theory of Groups, Springer-Verlag, New York, 1979.
• 8: M. Schonert et. al, GAP-Group, Algorithms, and Programming, Lehrstuhl D fur Mathematik, Rheinisch Westfalische Technische Hochschule, Aachen, Germany, fifth, 1995.
• 9: J. A. Smolin, and D. P. DiVincenzo, "Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate," Physical Review A, 53 (1996), pp. 2855--2856.
• 10: G. Yang, W. N. N. Hung, X. Song, and M. Perkowski. "Majority-based reversible logic gate", 6th International Symposium on Representations and Methodology of Future Computing Technology, pp. 191--200, Trier, Germany, March 2003.
• 11: V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, "Synthesis of Reversible Logic Circuits", IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, Vol. 22, No. 6, June 2003, pp. 710--723.
• 12: S. Lee, J.-S. Lee, T. Kim., S.-J. Lee, J. Biamonte, and M. Perkowski, "The Cost of quantum gate Primitives", submitted to MVL Journal, 2004.
• 13: Technical report, Portland State University.