Ελαχιστοποίηση Εκφράσεων Αποκλειστικού Ή - Κβαντικοί Αλγόριθμοι

Abstract

Με την πολυπλοκότητα των ολοκληρωμένων κυκλωμάτων να αυξάνεται, ενώ παράλληλα το μέγεθος τους να μειώνετα, παρουσιάστηκε η ανάγκη για αυτοματοποιημένα εργαλεία σύνθεσης και αποδοτικούς αλγορίθμους βελτιστοποίησης του μεγέθους τους. Το μέγεθος ενός τέτοιου κυκλώματος εξαρτάται, σε μεγάλο βαθμό, από το μέγεθος της λογικής έκφρασης που θα απεικονίσει. Στη συγκεκριμένη διδακτορική διατριβή εξετάζονται μέθοδοι ανάλυσης, απεικόνισης και κυρίως βελτιστοποίησης λογικών εκφράσεων «αποκλειστικού ή» αλλά και εφαρμογές τους σε άλλους τομείς, όπως της κρυπτογραφίας. Η πιο γνωστή τέτοια κατηγορία εκφράσεων είναι οι λεγόμενες εκφράσεις ESOP (Exclusive or Sum Of Products), όπου μια λογική συνάρτηση εκφράζεται ως άθροισμα XOR λογικών γινομένων. Ο κύριος στόχος στη συγκεκριμένη διδακτορική διατριβή είναι η βελτιστοποίηση εκφράσεων ESCT κυρίως με κβαντικούς, αλλά και συμβατικούς (Exclusive or Sum of Complex Terms), οι οποίες μπορούν να θεωρηθούν ως επέκταση των ESOP, αφού πλέον οι όροι ονομάζονται σύνθετοι (complex terms) και δεν περιλαμβάνουν μόνο τη λογική πράξη AND ανάμεσα στα literals των μεταβλητών αλλά εν γένει οποιαδήποτε λογική πράξη (συνάρτηση δύο εισόδων μιας εξόδου). Παρουσιάζεται το απαραίτητο θεωρητικό υπόβαθρο καθώς και συμβατικοί και κβαντικοί αλγόριθμοι τόσο για την ESCT ελαχιστοποίηση συναρτήσεων μίας ή πολλών εξόδων, πλήρως ή ατελώς ορισμένων. Τα πειραματικά αποτελέσματα από τους αλγορίθμους που στηρίζονται στα παραπάνω πορίσματα καταδεικνύουν την ανωτερότητα τους σε σχέση με αντίστοιχους της διεθνούς βιβλιογραφίας. Τέλος, οι ESCT εκφράσεις βρίσκουν με επιτυχία εφαρμογή σε σχήματα κρυπτογράφησης.