Vitaly G. Deibuk; Andrij V. Biloshytskyi

Design of a Ternary Reversible/Quantum Adder using Genetic Algorithm

Full Text (PDF, 540KB), PP.38-45

Views: 0 Downloads: 0

Author(s)

Vitaly G. Deibuk ^1,* Andrij V. Biloshytskyi ¹

1. Department of Computer Systems and Networks, Chernivtsi National University, 2 Kotsubinsky str., Chernivtsi 58012, UKRAINE

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2015.09.06

Received: 3 Jan. 2015 / Revised: 13 Apr. 2015 / Accepted: 1 Jun. 2015 / Published: 8 Aug. 2015

Index Terms

Multiple-valued logic, ternary logic, ternary reversible adder, reversible logic

Abstract

Typical methods of quantum/reversible synthesis are based on using the binary character of quantum computing. However, multi-valued logic is a promising choice for future computer technologies, given a set of advantages when comparing to binary circuits. In this work, we have developed a genetic algorithm-based synthesis of ternary reversible circuits using Muthukrishnan-Stroud gates. The method for chromosomes coding that we present, as well as a judicious choice of algorithm parameters, allowed obtaining circuits for half-adder and full adder which are better than other published methods in terms of cost, delay times and amount of input ancillary bits. A structure of the circuits is analyzed in details, based on their decomposition.

Cite This Paper

Vitaly G. Deibuk, Andrij V. Biloshytskyi, "Design of a Ternary Reversible/Quantum Adder using Genetic Algorithm", International Journal of Information Technology and Computer Science(IJITCS), vol.7, no.9, pp.38-45, 2015. DOI:10.5815/ijitcs.2015.09.06

Reference

[1]M. Nielsen, I. Chuang, Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000.

[2]A. De Vos, Y. van Rentergem, “Multiple-valued reversible logic circuits,” J. Multiple-Valued Logic and Soft Comput., vol.15, no.4-5, pp.489-505, 2009.

[3]A. Muthukrishnan, C. R. Stroud, Jr., “Multivalued logic gates for quantum computation,” Physical Review A, vol. 62, no. 5, pp. 052309/1-8, 2000..

[4]A. B. Klimov, R. Guzman, J. C. Retamal, C. Saavedra, “Qutrit quantum computer with trapped ions,” Physical Review A, vol. 67, no. 6, 062313/1-7, 2003.

[5]D. McHugh, J. Twamley, “Trapped-ion qutrit spin molecule quantum computer”, New J. Physics, vol. 7, no. 1, pp. 174/1-9,2005.

[6]D. M. Miller, M. A. Thornton, Multiple Valued Logic: Concepts and Representations. Morgan & Claypool Publishers, 2008.

[7]M. Lukac, M. Perkowski, H. Goi, M. Pivtoraiko, C. H. Yu, K. Chung, H. Jee, B-G. Kim, Y-D. Kim, “Evolutionary approach to Quantum and Reversible Circuits synthesis,” Artificial Intelligence Review, vol. 20, no. 3-4, pp. 361-417, 2003.

[8]D.M. Miller, D. Maslov, G.W. Dueck, ”Synthesis of Quantum Multiple-Valued Circuits”, J. Multiple-Valued Logic and Soft Comput., vol. 12, no. 5-6, pp. 431-450, 2006.

[9]D.M. Miller, R. Wille, R. Drechsler, ”Reducing Reversible Circuit Cost by Adding Lines”, J. Multiple-Valued Logic and Soft Comput., vol. 9, no. 1-3, pp. 185-201, 2012.

[10]M. Lukac M. Perkowski and M. Kameyama, “Evolutionary quantum logic synthesis of boolean reversible logic circuits embedded in ternary quantum space using structural restrictions”, Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010), Barcelona, Spain, 18-23 July 2010, pp. 1-8.

[11]M. H. A. Khan, M. A. Perkowski, M. R. Khan, and P. Kerntopf, “Ternary GFSOP Minimization using Kronecker Decision Diagrams and Their Synthesis with Quantum Cascades,” J. Multiple-Valued Logic and Soft Comput., vol. 11, no. 5-6, pp. 567-602, 2005.

[12]M.H.A. Khan, M.A. Perkowski, ”Quantum Ternary Parallel Adder/Subtractor with Partially-Look-Ahead Carry,” J. Systems Architecture, vol.53, no.7, pp. 453-464, 2007.

[13]M. H. A. Khan, “Design of Reversible/Quantum Ternary Comparator Circuits,” Engineering Letters, vol. 16, no. 2, pp. 178-164, 2008.

[14]R. Khanom, T. Kamal, M. H. A. Khan, ”Genetic Algorithm Based Synthesis of Ternary Reversible/Quantum Circuits,” Proceedings of 11th IEEE Int. Conf. on Computer and Information Technology (ICCIT 2008), Khulna, Bangladesh, 25-27 December, 2008, pp. 270-275.

[15]V.E. Zobov, D.I. Pekhterev, “Adder on ternary base elements for a quantum computer,” JETP Letters, vol. 89, no. 5, pp. 260-263, 2009.

[16]R. P. Zadeh, M. Haghparast, “A New Reversible/Quantum Ternary Comparator,” Australian J. Basic and Applied Sciences, vol. 5, no. 12, pp. 2348-2355, 2011.

[17]T. Satoh, S. Nagayama, R. Van Meter, “A Reversible Ternary Adder for Quantum Computation,” Asian Conf. on Quantum Information Science (AQIS-07). Kyoto, Japan, 3-6 September, 2007.

[18]X. Li, G. Yang, D. Zheng, ?Logic Synthesis of Ternary Quantum Circuits with Minimal Qutrits,” Journal of Computers, vol. 8, no. 8, pp. 1941-1946, 2013.

[19]Y.-M. Di, and H.-R. Wie, “Synthesis of Multivalued Quantum Logic Circuits by Elementary Gates,” Physical Review A, vol. 87, no. 1, pp. 012325/1-8, 2013.

[20]R. S. Zebulum, M. C. Pachecco, M. M. Vellasco, Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. CRC Press, 2002.

[21]L. Spector, Automatic Quantum Computer Programming: A Genetic Programming Approach. Kluwer Academic Publishers, 2004.

[22]A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing. Springer-Verlag, 2013.

International Journal of Information Technology and Computer Science (IJITCS)