Size of reversible circuits as a measure of even permutation complexity

The article considers even permutation complexity by estimating the size of reversible circuits composed of NOT, CNOT and 2-CNOT gates implementing these permutations. It is proved that every even permutation of Zⁿ₂ set can be implemented by a reversible circuit with the gate complexity equivalent up to about n2ⁿ/log₂n order, without the use of additional inputs; all other even permutations can be implemented by reversible circuit with less gate complexity, without the use of additional inputs. It is established that every even permutation of Zⁿ₂ set can be implemented by a reversible circuit with < 2ⁿ⁺¹ gate complexity, using ~ 5 • 2ⁿ/n additional inputs. For every even permutation usage of additional inputs allows decreasing the gate complexity of reversible circuits by implementing them.

References

[1] Shannon C.E. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J., 1949, vol. 28, no. 1, pp. 59-98.

[2] Yablonskiy S.V. Vvedenie v diskretnuyu matematiku [Introduction to discrete mathematics]. Moscow, Nauka Publ., 1986. 384 p.

[3] Interlando J.C. Toward a theory of one-way functions via gate complexity of boolean functions. Ph. D. Dissertation, USA, Indiana, University of Notre Dame, 2006. 100 p.

[4] Feynman R. Quantum mechanical computers. Optics News, 1985, vol. 11, no. 2, pp. 11-20. Available at: http://dx.doi.org/10.1364/ON.11.2.000011 (accessed 07.05.2014).

[5] Maslov D.A. Reversible Logic Synthesis. Ph. D. Dissertation, Canada, N.B., University of New Brunswick Fredericton, 2003. 165 p.

[6] Zakablukov D.V. Reduction of the reversible circuits gate complexity without using the equivalent replacement tables for the gate compositions. Jelektr. Nauchno-Tehn. Izd. "Nauka i obrazovanie" MGTU im. N.E. Baumana [El. Sc.-Tech. Publ. "Science and Education" of Bauman MSTU], 2014, no. 3. (in Russ.). DOI: 10.7463/0314.0699195

[7] Shende V.V., Prasad A.K., Markov I.L., Hayes J.P. Synthesis of reversible logic circuits. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2003, vol. 22, no. 6, pp. 710-722.

[8] Zakablukov D.V., Zhukov A.E. Research circuit from reversible logic elements. Sb. Tr. Molodykh Uchenykh, Aspirantov i Studentov "Informatika i sistemy upravleniya v XXI veke" [Collect. Pap. of Young Scientists, Post-graduates and Students "Informatics and Control Systems in the XXI Century"]. Moscow, MGTU im. N.E. Baumana Publ., 2012, iss. 9, pp. 148-157 (in Russ.).

[9] Zakablukov D.V. Fast algorithm for the synthesis of reversible circuits based on the theory of permutation groups. Prikl. Diskretnaya Mat. [J. Appl. Discrete Math.], 2014, no. 2, pp. 101-109 (in Russ.).

[10] Khlopotine A.B., Perkowski M.A., Kerntopf P Reversible logic synthesis by iterative compositions. Proc. of the Int. Workshop on Logic Synthesis, New Orleans, LA, USA, 2002, pp. 261-266.

[11] Yang G., Song X., Hung W.N., Perkowski M.A. Fast synthesis of exact minimal reversible circuits using group theory. Proc. of the 2005 Asia and South Pacific Design Automation Conf - ASP-DAC’05, China, Shanghai, 2005, pp. 1002-1005. DOI: 10.1145/1120725.1120777

[12] Miller D.M., Maslov D.A., Dueck G.W. A transformation based algorithm for reversible logic synthesis. Proc. of the 40th annual Design Automation Conf. -DAC’03, Anaheim, CA, USA, 2003, pp. 318-323. DOI: 10.1145/775832.775915

[13] Miller D.M. Spectral and two-place decomposition techniques in reversible logic. Proc. of the 45th Midwest Symp. on Circuits and Systems Conf. - MWSCAS’02, USA, OK, Tulsa, 2002, pp. 493-496. DOI: 10.1109/MWSCAS.2002.1186906

[14] Saeedi M., Sedighi M., Zamani M.S. A novel synthesis algorithm for reversible circuits. Proc. of Int. Conf. on Computer-Aided Design - ICCAD’07, USA, CA, San Jose, 2007, pp. 65-68. DOI:10.1109/ICCAD.2007.4397245

[15] Yang G., Song X., Hung W.N., Xie F., Perkowski M.A. Group theory based synthesis of binary reversible circuits. Proc. of the Third Int. Conf. on Theory and Applications of Models of Computation - TAMC’06, China, Beijing, 2006, pp. 365-374. DOI: 10.1007/11750321_35