National Technical University of Athens (NTUA)
Ελαχιστοποίηση εκφράσεων αποκλειστικού Ή - κβαντικοί αλγόριθμοι
Abstract
dc:descriptionThe current era in computer engineering, is characterized by the continuously increasing incorporation of computers and embedded systems in the all aspects of our daily life. The integrated circuits continuously shrink, become faster, require less energy with the help of new materials and architectures. As a result, the electronic appliances find more and more applications in all the aspects of our life and, as the time passes, they become an invisible and essential layer of interface with the environment. The research object with which deals the present thesis is the minimization of logic “eΧclusive OR” or (XOR) expressions for an arbitrary logic function, and more particularly, with the reduction of number of terms that constitute this function, as well as with the mapping of such expressions in architectures of new technologies such as quantum computers. An integrated circuit is the practical realization of such a logic expression. Accordingly, there is great effort for the optimization of logic circuits. The most popular such category of expressions is the so-called ESOP (Exclusive or Sum Of Products) expressions, where a logic function is expressed as XOR sum of products. Another more general category are the ESCT (Exclusive or Sum of Complex Terms) expressions, that can be considered as an extension of ESOPs, since the terms are now complex (complex terms) and do not include only the logic function AND between the variables, but also any logic function (of two inputs and one output). The importance of the above expressions is also stressed by the fact that they can, in a trivial manner, be mapped in reversible architectures. A reversible logic circuit has smaller losses of energy in comparison to a conventional circuit and for this reason the composition of reversible circuits is considered the future in the logic design. Another important advantage, is that they can be also used for the composition of quantum circuits. The minimization of these expressions as well as their quantum extensions are the main object of research in this thesis. This work deals firstly, with the theoretical background of the minimization of such expressions. Theorems are proved, which indicate a methodology for finding a minimal ESCT expression for any completely specified single output logic function, with the restriction of the number of terms in its minimal expression or with the restriction of the number of its input variables. Moreover, it is studied how the above conclusions can be used for heuristic minimisation of functions that do not fall in the above restrictions. Later on, the above conclusions are extended, heuristically, for incompletely specified multi-output logic functions. The above theoretical study of the problem of “exclusive or” minimization, is used for the realization of conventional and quantum algorithms which, as it appears also from the experimental results, give better results than the corresponding of the international bibliography. More specifically, the quantum algorithms that can be used for the exact minimization of “exclusive or” expressions, indicate the explicit supremacy of quantum computers against the conventional ones. Finally, we apply the above results in the field of encryption and secure computation. More specifically, the ESCT minimization algorithms are used to achieve up to 39% less cost of communication against the related corresponding efforts of bibliography.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Sampson, Marinos
- Σαμψών, Μαρίνος
Subjects
dc:subject × 15- Ελαχιστοποίηση
- Εκφράσεις αποκλειστικού Ή
- Αλγόριθμοι, Κβαντικοί
- Κβαντικοί υπολογιστές
- Κρυπτογράφηση
- XOR minimization
- ESCT
- ESOP
- SDD
- Quantum algorithms
- Quantum circuits
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/18284