×

Computing the number of the equivalence classes for reversible logic functions. (English) Zbl 1447.81079

Summary: Reversible logic function classification plays an important role in reversible logic synthesis. This paper studies the calculation of the number of the equivalence classes for reversible logic functions. In order to do this work, an \(n\)-qubit reversible function is expressed as a permutation in the symmetric group \(S_{2^n}\), so that a universal formula for calculating the number of equivalence classes of reversible logic functions is derived based on group theory. Based on the calculation method of the number of conjugacy classes of permutation groups, an improved method for calculating the number of equivalence classes of reversible logic functions is obtained. In the experiments with GAP software on a laptop, we can compute the NPNP-equivalence classes for up to 13 qubits, LL-equivalence classes for up to 10 qubits and AA-equivalence classes for up to 10 qubits. Experiment results indicate that our scheme for calculating these equivalence classes of more than 6 qubits over previous published methods is a significant advancement.

MSC:

81P68 Quantum computation
81P65 Quantum gates
20B30 Symmetric groups
05A19 Combinatorial identities, bijective combinatorics

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nielsen, M.; Chuang, I., Quantum Computation and Quantum Information (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1288.81001
[2] Bennett, C., Logical reversibility of computation, IBM J. Res. Dev., 17, 6, 525-532 (1973) · Zbl 0267.68024 · doi:10.1147/rd.176.0525
[3] Merkle, RC, Two types of mechanical reversible logic, Nanotechnology, 4, 2, 114-131 (1993) · doi:10.1088/0957-4484/4/2/007
[4] Biryukov, A., Canniere, C., Braeken, A., Bart, P.: A toolbox for cryptanalysis: linear and affine equivalence algorithms. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp 33-50. Springer, Berlin (2003) · Zbl 1038.94521
[5] Agrawal, A., Jha, N.K.: Synthesis of reversible logic. In: Proceedings of the Design, Automation and Test in Europe Conference, pp 1384-1385. IEEE (2004)
[6] Shende, VV; Prasad, AK; Markov, IL, Synthesis of reversible logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22, 6, 710-722 (2003) · doi:10.1109/TCAD.2003.811448
[7] Yang, G.; Hung, WN; Song, X., Exact synthesis of three-qubit quantum circuits from non-binary quantum gates, Int. J. Electron., 97, 4, 475-489 (2010) · doi:10.1080/00207210903325252
[8] Yang, G.; Xie, F.; Hung, WN, Realization and synthesis of reversible functions, Theor. Comput. Sci., 412, 17, 1606-1613 (2011) · Zbl 1211.81049 · doi:10.1016/j.tcs.2010.11.031
[9] Soeken, M., Abdessaied, N., Micheli, G.D.: Enumeration of reversible functions and its application to circuit complexity. In: International Conference on Reversible Computation, pp 255-270. Springer International Publishing (2016) · Zbl 1480.94055
[10] Maslov, D.; Dueck, GW; Miller, DM, Toffoli network synthesis with templates, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24, 6, 807-817 (2005) · doi:10.1109/TCAD.2005.847911
[11] Maslov, D.; Miller, DM; Dueck, GW, Techniques for the synthesis of reversible toffoli network, ACM Trans. Des. Autom. Electron. Syst., 12, 4, 1084-1101 (2006)
[12] Lorens, CS, Invertible boolean functions, IEEE Transactions on Electronic Computers, 5, 529-541 (1964) · Zbl 0248.94048 · doi:10.1109/PGEC.1964.263724
[13] Harrison, MA, The number of classes of invertible boolean functions, J. ACM, 10, 1, 25-28 (1963) · Zbl 0126.00901 · doi:10.1145/321150.321152
[14] Harrison, MA, On the classification of boolean functions by the general linear and affine groups, J. Soc. Ind. Appl. Math., 12, 2, 285-299 (1964) · Zbl 0134.25802 · doi:10.1137/0112026
[15] Primenko, EA, Equivalence classes of invertible boolean functions, Cybernetics, 20, 6, 771-776 (1984) · Zbl 0574.94022 · doi:10.1007/BF01072161
[16] de Bruijn, N.: Polya’s theory of counting. Applied Combinatorial Mathematics, pp 144-184 (1964) · Zbl 0144.00601
[17] Kerntopf, P., Stankovic, R., Vos, A.D., et al.: Early pioneers to reversible computation. In: 23rd International Workshop on Post-Binary ULSI Systems , pp 36-42 (2014)
[18] Kerntopf, P., Podlaski, K., Moraga, C., et al.: Study of reversible ternary functions with homogeneous component functions. In: 47th International Symposium on Multiple-Valued Logic, pp 191-196. IEEE (2017)
[19] Caric, M.; Zivkovic, M., On the number of equivalence classes of invertible boolean functions under action of permutation of variables on domain and range, Publications. de l’Institut Mathematique, 100, 114, 95-99 (2016) · Zbl 1462.05017 · doi:10.2298/PIM1614095C
[20] Sloane, N.J.A.: Invertible boolean functions of n variables. On-line encyclopedia of integer sequences. http://oeis.org/search?q=A000654&language=english&go=Search(2011)
[21] Sloane, N.J.A.: Invertible boolean functions with gl(n,2) acting on the domain and range. http://oeis.org/search?q=A001038&sort=&language=english&go=Search(2012)
[22] Sloane, N.J.A.: Invertible boolean functions with ag(n,2) acting on the domain and range. http://oeis.org/search?q=A001537&sort=&language=english&go=Search(2012)
[23] Yang, G., Song, X., Hung, W.N.N., et al.: Group theory based synthesis of binary reversible circuits. In: International Conference on Theory and Applications of Models of Computation, pp 365-374. Springer, Berlin (2006) · Zbl 1178.68261
[24] Gupta, P.; Agrawal, A.; Jha, NK, An algorithm for synthesis of reversible logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25, 11, 2317-2330 (2006) · doi:10.1109/TCAD.2006.871622
[25] Joyce, D.: Introduction to modern algebra. Clark University, pp 104-105 (2017)
[26] Rotman, J.J.: Advanced modern. Algebra American Mathematical Society (2010) · Zbl 1206.00007
[27] Artin, M., Algebra (2011), New York: Pearson Education Inc.,, New York
[28] Hasselbarth, W.; Ruch, E., Classifications of rearrangement mechanisms by means of double cosets and counting formulas for the numbers of classes, Theor. Chim. Acta, 29, 3, 259-268 (1973) · doi:10.1007/BF00529052
[29] Hulpke, A., Conjugacy classes infinite permutation groups via homomorphic images, Math. Comput., 69, 232, 1633-1651 (2000) · Zbl 0962.20001 · doi:10.1090/S0025-5718-99-01157-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.