Ελαχιστοποίηση εκφράσεων αποκλειστικού Ή - κβαντικοί αλγόριθμοι
Authors: Σαμψών Μαρίνος 
Published: August 2021

Η σημερινή εποχή χαρακτηρίζεται από την ολοένα αυξανόμενη ενσωμάτωση των ηλεκτρονικών υπολογιστών και των ενσωματωμένων συστημάτων σε όλες τις πτυχές της καθημερινής μας ζωής. Τα ολοκληρωμένα κυκλώματα συνεχώς σμικρύνονται, γίνονται ταχύτερα, απαιτούν όλο και μικρότερα ποσά ενέργειας με τη βοήθεια νέων υλικών και αρχιτεκτονικών. Αυτό έχει ως αποτέλεσμα οι ηλεκτρονικές συσκευές να βρίσκουν όλο και περισσότερες εφαρμογές σε όλους τους τομείς της ζωής μας και με τον καιρό να μετατρέπονται σε ένα αόρατο και απαραίτητο στρώμα διεπαφής μας με το περιβάλλον. Το αντικείμενο με το οποίο ασχολείται μέχρι στιγμής η παρούσα διατριβή είναι η ελαχιστοποίηση λογικών εκφράσεων ’’αποκλειστικού ή” (XOR) για τυχαία λογική συνάρτηση, και πιο συγκεκριμένα με τη μείωση των όρων από τους οποίους αυτή αποτελείται καθώς και με την απεικόνιση τέτοιων εκφράσεων σε αρχιτεκτονικές νέων τεχνολογιών όπως οι κβαντικοί υπολογιστές. Ένα ολοκληρωμένο κύκλωμα αποτελεί την πρακτική υλοποίηση μιας τέτοιας λογικής έκφρασης. Κατά συνέπεια, γίνεται προσπάθεια για την βελτιστοποίηση λογικών κυκλωμάτων. Η πιο γνωστή τέτοια κατηγορία εκφράσεων είναι οι λεγάμενες εκφράσεις ESOP (Exclusive or Sum Of Products), όπου μια λογική συνάρτηση εκφράζεται ως άθροισμα XOR από λογικά γινόμενα. Μια άλλη πιο γενική κατηγορία είναι οι ESCT (Exclusive or Sum of Complex Terms) εκφράσεις, οι οποίες μπορούν να θεωρηθούν ως επέκταση των ESOP, αφού πλέον οι όροι ονομάζονται σύνθετοι (complex terms) και δεν περιλαμβάνουν μόνο τη λογική πράξη ΚΑΙ ανάμεσα στις μεταβλητές, αλλά εν γένει οποιαδήποτε λογική πράξη (συνάρτηση δύο εισόδων μιας εξόδου). Η σημασία των παραπάνω εκφράσεων τονίζεται και από το γεγονός ότι μπορούν, με τετριμμένο τρόπο, να απεικονισθούν σε αντιστρέψιμες αρχιτεκτονικές. Ένα αντιστρέψιμο λογικό κύκλωμα έχει μικρότερες απώλειες ενέργειας σε σχέση με ένα τυπικό λογικό κύκλωμα και για το λόγο αυτό η σύνθεση αντιστρέψιμων κυκλωμάτων θεωρείται το μέλλον στη λογική σχεδίαση. Ένα ακόμα σημαντικό τους πλεονέκτημα είναι ότι μπορούν να χρησιμοποιηθούν και για τη σύνθεση κβαντικών κυκλωμάτων. Η ελαχιστοποίηση αυτών των εκφράσεων καθώς και οι κβαντικές επεκτάσεις τους είναι το κύριο αντικείμενο έρευνας με το οποίο ασχολείται αυτή η εργασία. Η εργασία αυτή ασχολείται καταρχήν, με το θεωρητικό υπόβαθρο της ελαχιστοποίησης τέτοιων εκφράσεων. Αποδεικνύονται θεωρήματα τα οποία υποδεικνύουν μια μεθοδολογία για την εύρεση ελάχιστης ESCT έκφρασης για οποιαδήποτε πλήρως ορισμένη λογική συνάρτηση μοναδικής εξόδου, αλλά με περιορισμό ως προς τον αριθμό των όρων σε μια ελάχιστη έκφρασή της ή με περιορισμό ως προς τον αριθμό των μεταβλητών εισόδου της. Γίνεται, επιπλέον, μελέτη πώς τα παραπάνω συμπεράσματα μπορούν να χρησιμοποιηθούν για ευριστική ελαχιστοποίηση συναρτήσεων που δεν εμπίπτουν στους παραπάνω περιορισμούς. Στη συνέχεια τα παραπάνω πορίσματα επεκτείνονται, ευριστικά, για ατελώς ορισμένες λογικές συναρτήσεις πολλών εξόδων. Η παραπάνω θεωρητική μελέτη του προβλήματος ελαχιστοποίησης εκφράσεων ’’αποκλειστικού ή”, χρησιμοποιείται για την υλοποίηση συμβατικών και κβαντικών αλγορίθμων οι οποίοι, όπως φαίνεται και από τα πειραματικά αποτελέσματα, δίνουν καλύτερα αποτελέσματα από τους αντίστοιχους της διεθνούς βιβλιογραφίας. Πιο συγκεκριμένα, οι κβαντικοί αλγόριθμοι που μπορούν να χρησιμοποιηθούν για την ακριβή ελαχιστοποίηση εκφράσεων ’’αποκλειστικού ή” και καταδεικνύουν τη σαφή υπεροχή των κβαντικών υπολογιστών έναντι των κλασικών τους αναλόγων. Τέλος, πραγματοποιείται εφαρμογή των παραπάνω αποτελεσμάτων στο πεδίο της κρυπτογράφησης και των ασφαλών υπολογισμών. Πιο συγκεκριμένα, γίνεται χρήση των αλγορίθμων ελαχιστοποίησης εκφράσεων ESCT για την επίτευξη έως και 39% λιγότερου κόστους επικοινωνίας σε σχέση με τις υπόλοιπες αντίστοιχες προσπάθειες της βιβλιογραφίας. Κατά τη διάρκεια της εκπόνησης της συγκεκριμένης διατριβής έχουν προκύψει οι δημοσιεύσεις που παρουσιάζονται στον κατάλογο δημοσιεύσεων που ακολoυθεί.