Designing of Reversible Functions in Classical and Quantum Domains

• Autorzy: Skorupski Andrzej , Romaniuk Ryszard

Identyfikatory

DOI

10.24425/ijet.2024.149572

• Języki publikacji: EN

Abstrakty

EN

First sections of the paper contain some considerations relevant to the reversibility of quantum gates. The Solovay-Kitayev theorem shows that using proper set of quantum gates one can build a quantum version of the non-deterministic Turing machine. On the other hand the Gottesmann-Knill theorem shows the possibility to simulate the quantum machine consisting of only Clifford/Pauli group of gates. This paper presents also an original method of designing the reversible functions. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm leads to cascade with minimal number CNT gates. This solution is called optimal reversible circuits. The paper is organized as follows. Section 5 recalls basic concepts of reversible logic. Section 6 contain short description of CNT set of the reversible gates. In Section 7 is presented form of result of designing as the cascade of gates. Section 8 describes the algorithm and section 9 simple example.

Słowa kluczowe

EN

reversible logic; reversible circuits; reversible gate; CNT set of the gates

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2024
• Tom: Vol. 70, No. 2
• Strony: 501--508
• Opis fizyczny: Bibliogr. 27 poz. rys.

Twórcy

autor

Skorupski Andrzej

• Warsaw University of Technology, Institute of Computer Science, and Institute of Electronic Systems, Poland

autor

Romaniuk Ryszard

• Warsaw University of Technology, Institute of Computer Science, and Institute of Electronic Systems, Poland

Bibliografia

• [1] R. Landauer, Irreversibility and heat generation in the computing process. IBM Journal of Research and Development , 5(3):183-191, July 1961. https://doi.org/10.1147/rd.53.0183.
• [2] M. Nielsen, I. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000. https://doi.org/10.1017/CBO9780511976667.
• [3] B. Desoete, A. De Vos, M. Sibinski, T. Widerski, Feynman’s reversible gates implemented in silicon, 6th International Conference MIXDES, pages 496-502, 1999.
• [4] M. Veldhorst, C. H. Yang, J. C. C. Hwang, W. Huang, J. P. Dehollain, J. T. Muhonen, S. Simmons, A. Laucht, F. E. Hudson, K. M. Itoh, A. Morello, A. S. Dzurak, A two-qubit logic gate in silicon, Nature, 526, 410-414, October 2015.
• [5] P. Picton, Opoelectronic, multivalued, conservative logic, International Journal of Optical Computing, 2:19-29, 1991.
• [6] R. C. Merkle, K. E. Drexler, Helical logic, Nanotechnology, 7:325-339, 1996. https://doi.org/10.1088/0957-4484/7/4/004.
• [7] E. Fredkin T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21:219-253, 1982.
• [8] R. Feynman. Quantum mechanical computers. Optic News, 11:11-20, 1985.
• [9] T. Toffoli. Reversible computing. Tech memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980.
• [10] P. Kerntopf, Maximally efficient binary and multi-valued reversible gates, International Workshop on Post-Binary ULSI Systems, pp. 55-58, Warsaw, Poland, May 2001.
• [11] K. Iwama, Y. Kambayashi, S. Yamashita, Transformation rules for designing CNOT-based quantum circuits, Design Automation Conference, New Orleans, Louisiana, USA, June 10-14 2002. https://doi.org/10.1109/DAC.2002.1012662.
• [12] D. M. Miller, D. Maslov, W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the Design Automation Conference, pages 318-323, June 2003. https://doi.org/10.1145/775832.775915.
• [13] K. Fazel, M. A. Thornton, J. E. Rice, ESOP-based Toffoli Gate Cascade Generation, Proc. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 206-209, 2007. https://doi.org/10.1109/PACRIM.2007.4313212.
• [14] M. H. A. Khan, M. A. Perkowski, Multi-output ESOP Synthesis with Cascades of New Reversible Gate Family, Proc Int. Symp. On Representations and Methodology of Future Comp. Technology, pp.43-55,2003.
• [15] R. Wille, R. Drechsler, BDD-based synthesis of reversible logic for large functions, Design Automation Conf. , pp. 270-275, 2009. https://doi.org/10.1145/1629911.1629984.
• [16] M. Hawash, M. Perkowski, N. Alhagi, Synthesis of Reversible Circuits with No Ancilla Bits for Large Reversible Functions, Proc. ISMVL, 2010, p. 1-7. https://doi.org/10.1109/ISMVL.2010.16.
• [17] D. Wang, S. Sun, H. Chen, Matrix-based algorithm for 4-qubit reversible logic circuits synthesis, Energy Procedia, vol. 13, pp. 365-371, 2011. https://doi.org/10.1016/j.egypro.2011.11.052.
• [18] O. Golubitsky, D. Maslov, A study of optimal 4-bit reversible Toffoli circuits and their synthesis, IEEE Transactions on Computers, vol. 61, no. 9, 2012,. pp. 1341-1353. https://doi.org/10.1109/TC.2011.144.
• [19] A. Khlopotine, M. Perkowski, P. Kerntopf, Reversible logic synthesis by iterative compositions, International Workshop on Logic Synthesis, 2002.
• [20] M. Soeken, N. Abdessaied, G. De Micheli, Enumeration of reversible functions and its application to circuit complexity, Conference on Reversible Computation, 2016, 255-270.
• [21] P. Gupta, A. Agrawal, N. K. Jha. An algorithm for synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, pp. 2317-2330, 2006. https://doi.org/10.1109/TCAD.2006.871622.
• [22] P. Kerntopf. A new heuristic algorithm for reversible logic synthesis. ACM/IEEE DAC, pages 834-837, 2004. https://doi.org/10.1145/996566.996789.
• [23] A. Barenco, et al., 1995, Elementary gates for quantum computation, https://doi.org/10.48550/arXiv.quant-ph/9503016.
• [24] R. Romaniuk, 2021, Quantum gates, Elektronika 62(12): 17-25, https://doi.org/10.15199?13.2021.4 (in Polish).
• [25] A. Pathak, 2013, Non-Hermitian quantum gates are more common than Hermitian quantum gates. https://doi.org/10.48550/arXiv.1309.4037.
• [26] D. Deutsch, P. Hayden, 1999, Information flow in entangled quantum systems, https://doi.org/10.48550/arXiv.quant-ph/9906007.
• [27] D. Gross, et al., 2009, Most quantum states are too entangled to be useful as computational resources, https://doi.org/10.48550/arXiv.0810.4331.