×

A reversible logical circuit synthesis algorithm based on decomposition of cycle representations of permutations. (English) Zbl 1447.81086

Summary: A reversible function is isomorphic to a permutation and an arbitrary permutation can be represented by a series of cycles. A new synthesis algorithm for 3-qubit reversible circuits was presented. It consists of two parts, the first part used the Number of reversible function’s Different Bits (NDBs) to decide whether the NOT gate should be added to decrease the Hamming distance of the input and output vectors; the second part was based on the idea of exploring properties of the cycle representation of permutations, decomposed the cycles to make the permutation closer to the identity permutation and finally turn into the identity permutation, it was realized by using totally controlled Toffoli gates with positive and negative controls.

MSC:

81P68 Quantum computation
03B30 Foundations of classical theories (including reverse mathematics)
20B05 General theory for finite permutation groups
81P65 Quantum gates
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Saeedi, M; Markov, IL, Synthesis and optimization of reversible circuits—a survey, ACM Comput. Surv., 45, 1-34, (2011) · Zbl 1293.94141 · doi:10.1145/2431211.2431220
[2] Bennett, CH, Logical reversibility of computation, IBM J. Res. Dev., 17, 525-532, (1973) · Zbl 0267.68024 · doi:10.1147/rd.176.0525
[3] Chen, HW; Li, WQ; Ruan, Y; etal., A synthesis algorithm of reversible logic circuit based on the decreasing transform of Hamming distance, Chin. J. Comput., 9, e87682-e87682, (2014)
[4] Ribeiro, A.C., De Figueiredo, C.M.H., Marquezino, F.L., et al.: Cayley graphs and analysis of quantum cost for reversible circuit synthesis. Comput. Sci. In Ramos, RV (ed.): IV Workshop-School on Quantum Computation and Information, Universidade Federal do Ceará, Fortaleza, pp. 71-79 (2012). arXiv:1209.3275
[5] Ribeiro, AC; Kowada, LAB; Marquezino, FL; etal., A new reversible circuit synthesis algorithm based on cycle representations of permutations, Electron. Notes Discrete Math., 50, 187-192, (2015) · Zbl 1348.68056 · doi:10.1016/j.endm.2015.07.032
[6] Li, Z; Chen, H; Zhu, W; etal., Reversible logic circuit synthesis algorithm based on transposition gate library, J. Southeast Univ., 42, 832-836, (2012)
[7] Saeedi, M; Markov, IL, Synthesis and optimization of reversible circuits—a survey, ACM Comput. Surv., 45, 1-34, (2011) · Zbl 1293.94141 · doi:10.1145/2431211.2431220
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.