×

Efficient algorithms for optimal 4-bit reversible logic system synthesis. (English) Zbl 1267.68115

Summary: Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space of \(n\)-bit circuits reaches near \(2 \times n!\). This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.

MSC:

68Q12 Quantum algorithms and complexity in the theory of computing
81P68 Quantum computation
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. P. Feynman, “Quantum mechanical computers,” Foundations of Physics, vol. 16, no. 6, pp. 507-531, 1986. · doi:10.1007/BF01886518
[2] E. Fredkin and T. Toffoli, “Conservative logic,” International Journal of Theoretical Physics, vol. 21, no. 3-4, pp. 219-253, 1982. · Zbl 0496.94015 · doi:10.1007/BF01857727
[3] X. Song, G. Yang, M. Perkowski, and Y. Wang, “Algebraic characterization of reversible logic gates,” Theory of Computing Systems, vol. 39, no. 2, pp. 311-319, 2006. · Zbl 1101.68032 · doi:10.1007/s00224-004-1166-2
[4] K. Iwama, Y. Kambayashi, and S. Yamashita, “Transformation rules for designing CNOT-based quantum circuits,” in Proceedings of the 39th Annual Design Automation Conference (DAC ’02), pp. 419-424, New Orleans, La, USA, June 2002.
[5] D. M. Miller, D. Maslov, and G. W. Dueck, “A transformation based algorithm for reversible logic synthesis,” in Proceedings of the 40th Design Automation Conference, pp. 318-323, San Jose, Calif, USA, June 2003.
[6] A. Mishchenko and M. Perkowski, “Logic synthesis of reversible wave cascades,” in Proceedings of 11th IEEE International Workshop on Logic Synthesis, pp. 197-202, New Orleans, La, USA, 2002.
[7] P. Gupta, A. Agrawal, and N. K. Jha, “An algorithm for synthesis of reversible logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 11, pp. 2317-2330, 2006. · Zbl 05448186 · doi:10.1109/TCAD.2006.871622
[8] W. Li, H. Chen, and Z. Li, “Application of semi-template in reversible logic circuit,” in Proceedings of the 11th International Conference on Computer Supported Cooperative Work in Design (CSCWD ’07), pp. 332-336, Melbourne, Australia, April 2007. · doi:10.1109/CSCWD.2007.4281457
[9] V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, “Reversible logic circuit synthesis,” in IEEE/ACM International Conference on Computer Aided Design (ICCAD ’02), pp. 353-360, San Jose, Calif, USA, November 2002. · doi:10.1145/774572.774625
[10] V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, “Synthesis of reversible logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 6, pp. 710-722, 2003. · Zbl 05449657 · doi:10.1109/TCAD.2003.811448
[11] G. Yang, X. Song, W. N. N. Hung, M. A. Perkowski, and C.-J. Seo, “Synthesis of reversible circuits with minimal costs,” Calcolo, vol. 45, no. 3, pp. 193-206, 2008. · Zbl 1173.94469 · doi:10.1007/s10092-008-0150-7
[12] G. Yang, X. Song, and M. Perkowski, “Fast synthesis of exact minimal reversible circuits using group theory,” in Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC ’05), vol. 2, pp. 18-21, Shanghai, China, 2005.
[13] W. N. N. Hung, X. Song, G. Yang, J. Yang, and M. Perkowski, “Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 9, pp. 1652-1663, 2006. · Zbl 05448337 · doi:10.1109/TCAD.2005.858352
[14] G. Yang, X. Song, W. N. N. Hung, and M. A. Perkowski, “Bi-direction synthesis for reversible circuits,” in Proceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design (ISVLSI’05), pp. 14-19, Tampa, Fla, USA, May 2005.
[15] G. Yang, X. Song, W. N. N. Hung, and M. A. Perkowski, “Bi-directionalsynthesis of 4-bit reversible circuits,” Computer Journal, vol. 51, no. 2, pp. 207-215, 2008. · Zbl 05534216 · doi:10.1093/comjnl/bxm042
[16] G. Yang, F. Xie, W. N. N. Hung, X. Song, and M. A. Perkowski, “Realization and synthesis of reversible functions,” Theoretical Computer Science, vol. 412, no. 17, pp. 1606-1613, 2011. · Zbl 1211.81049 · doi:10.1016/j.tcs.2010.11.031
[17] Z. Li, H. Chen, B. Xu, and W. Liu, “Fast algorithm for 4-qubit reversible logic circuits synthesis,” in Proceedings of the IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence) (CEC ’08), pp. 2202-2207, Hongkong, China, 2008.
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.