Η μελέτη κρυπτογραφικών αλγορίθμων δημοσίου κλειδιού, οι οποίοι θα είναι ανθεκτικοί και μετά την έλευση των κβαντικών υπολογιστών, αποτελούν ένα πολύ σημαντικό ερευνητικό πεδίο, καθώς οι σημερινοί κλασικοί αλγόριθμοι δημοσίου κλειδιού (RSA, ελλειπτικών καμπυλών κ.α.) δεν θα παρέχουν πλέον καμία ασφάλεια στο νέο αυτό τεχνολογικό περιβάλλον. Ήδη γνωρίζουμε διάφορους κρυπτογραφικούς αλγορίθμους οι οποίοι είναι, ή φέρονται να είναι, ασφαλείς ακόμα και με την υπόθεση ότι διαθέτουμε κβαντικούς υπολογιστές (ήτοι πρόκειται για αλγόριθμους μετακβαντικής κρυπτογραφίας). Ωστόσο πολλά θέματα ως προς τη δυνατότητα υλοποίησής τους παραμένουν ανοιχτά. \nΣτην παρούσα εργασία μελετάται η μετακβαντική κρυπτογραφία και τα συναφή μαθηματικά προβλήματα πάνω στα οποία δομούνται οι μετακβαντικοί αλγόριθμοι, με έμφαση στα προβλήματα που άπτονται της θεωρίας κωδίκων, παρουσιάζοντας και υλοποιώντας το κρυπτοσύστημα McEliece – ένα κλασικό κρυπτογραφικό σύστημα που αποτελεί ήδη έναν από τους υποψήφιους κρυπταλγορίθμους στη διαδικασία προτυποποίησης που έχει εκκινήσει ο οργανισμός NIST. Απώτερος στόχος είναι η συγκριτική αποτίμηση της απόδοσης του McEliece σε εφαρμογές πραγματικού χρόνου, σε σχέση με σημερινούς συμβατικούς κρυπταλγορίθμους. Αρχικά πραγματοποιείται μία βιβλιογραφική επισκόπηση σε θεωρητικά ζητήματα της κλασσικής και μετακβαντικής κρυπτογραφίας αλλά και σε θέματα της θεωρίας της πληροφορίας με έμφαση στον κβαντικό υπολογιστή. Στη συνέχεια παρουσιάζονται τα χαρακτηριστικά του κρυπτοσυστήματος McEliece. Αναπτύσσεται μια υλοποίηση κρυπτοσυστήματος δημόσιου κλειδιού RSA, που αποτελεί και έναν κλασσικό αλγόριθμο, καθώς επίσης και μία αντίστοιχη υλοποίηση κρυπτοσυστήματος δημοσίου κλειδιού με τον αλγόριθμο McEliece: και οι δύο υλοποιήσεις αφορούν μία τυπική εφαρμογή συνομιλίας (chat). Ακολούθως, γίνεται συγκριτική αποτίμηση των δύο υλοποιήσεων. Η μελέτη καταδεικνύει ότι πράγματι ο αλγόριθμος McEliece, ως αλγόριθμος μετακβαντικής κρυπτογραφίας, είναι σημαντικά πιο αργός, αναδεικνύοντας την ανάγκη εύρεσης μεθόδων βελτίωσης της απόδοσης των αλγορίθμων αυτής της κατηγορίας.
Η μελέτη κρυπτογραφικών αλγορίθμων δημοσίου κλειδιού, οι οποίοι θα είναι ανθεκτικοί και μετά την έλευση των κβαντικών υπολογιστών, αποτελούν ένα πολύ σημαντικό ερευνητικό πεδίο, καθώς οι σημερινοί κλασικοί αλγόριθμοι δημοσίου κλειδιού (RSA, ελλειπτικών καμπυλών κ.α.) δεν θα παρέχουν πλέον καμία ασφάλεια στο νέο αυτό τεχνολογικό περιβάλλον. Ήδη γνωρίζουμε διάφορους κρυπτογραφικούς αλγορίθμους οι οποίοι είναι, ή φέρονται να είναι, ασφαλείς ακόμα και με την υπόθεση ότι διαθέτουμε κβαντικούς υπολογιστές (ήτοι πρόκειται για αλγόριθμους μετακβαντικής κρυπτογραφίας). Ωστόσο πολλά θέματα ως προς τη δυνατότητα υλοποίησής τους παραμένουν ανοιχτά. \nΣτην παρούσα εργασία μελετάται η μετακβαντική κρυπτογραφία και τα συναφή μαθηματικά προβλήματα πάνω στα οποία δομούνται οι μετακβαντικοί αλγόριθμοι, με έμφαση στα προβλήματα που άπτονται της θεωρίας κωδίκων, παρουσιάζοντας και υλοποιώντας το κρυπτοσύστημα McEliece – ένα κλασικό κρυπτογραφικό σύστημα που αποτελεί ήδη έναν από τους υποψήφιους κρυπταλγορίθμους στη διαδικασία προτυποποίησης που έχει εκκινήσει ο οργανισμός NIST. Απώτερος στόχος είναι η συγκριτική αποτίμηση της απόδοσης του McEliece σε εφαρμογές πραγματικού χρόνου, σε σχέση με σημερινούς συμβατικούς κρυπταλγορίθμους. Αρχικά πραγματοποιείται μία βιβλιογραφική επισκόπηση σε θεωρητικά ζητήματα της κλασσικής και μετακβαντικής κρυπτογραφίας αλλά και σε θέματα της θεωρίας της πληροφορίας με έμφαση στον κβαντικό υπολογιστή. Στη συνέχεια παρουσιάζονται τα χαρακτηριστικά του κρυπτοσυστήματος McEliece. Αναπτύσσεται μια υλοποίηση κρυπτοσυστήματος δημόσιου κλειδιού RSA, που αποτελεί και έναν κλασσικό αλγόριθμο, καθώς επίσης και μία αντίστοιχη υλοποίηση κρυπτοσυστήματος δημοσίου κλειδιού με τον αλγόριθμο McEliece: και οι δύο υλοποιήσεις αφορούν μία τυπική εφαρμογή συνομιλίας (chat). Ακολούθως, γίνεται συγκριτική αποτίμηση των δύο υλοποιήσεων. Η μελέτη καταδεικνύει ότι πράγματι ο αλγόριθμος McEliece, ως αλγόριθμος μετακβαντικής κρυπτογραφίας, είναι σημαντικά πιο αργός, αναδεικνύοντας την ανάγκη εύρεσης μεθόδων βελτίωσης της απόδοσης των αλγορίθμων αυτής της κατηγορίας.
Στις επικοινωνίες ανάμεσα σε ανοιχτά συστήματα υπάρχουν τέσσερις κύριες κατηγορίες απειλών: Μη εξουσιοδοτημένη απόκτηση της πληροφορίας, Μη εξουσιοδοτημένη τροποποίηση της πληροφορίας, Πλαστοπροσωπία χρήστη, Αποκήρυξη της επικοινωνίας. Ο βασικός μηχανισμός για την παροχή ασφάλειας με τα χαρακτηριστικά που περιγράφηκαν πιο πάνω είναι η κρυπτογραφία. Οι συμμετρικοί αλγόριθμοι κρυπτογραφίας είναι πολύ ασφαλείς, γρήγοροι και έχουν διαδεδομένη χρήση. Ωστόσο, υπάρχουν διάφορες ελλείψεις που σχετίζονται με σχήματα συμμετρικού κλειδιού, όπως το πρόβλημα της διανομής κλειδιού, το μεγάλο πλήθος των κλειδιών που απαιτούνται και επίσης δεν παρέχουν καμία προστασία ενάντια σε επιθέσεις της επικοινωνίας. Τα παραπάνω προβλήματα λύνονται με τη χρήση ασύμμετρων αλγορίθμων ή αλλιώς δημοσίου κλειδιού σε καλά σχεδιασμένα πρωτόκολλα ασφάλειας και ανταλλαγής κλειδιού. Υπάρχουν τρεις κυρίαρχες οικογένειες αλγορίθμων δημοσίου κλειδιού οι οποίες έχουν πρακτικό αντίκρισμα. Μπορούν να ταξινομηθούν με βάση το υπολογιστικό πρόβλημα που τις χαρακτηρίζουν: Συστήματα παραγοντοποίησης ακεραίου, Συστήματα διακριτού λογαρίθμου, Συστήματα ελλειπτικών καμπυλών. Κάθε μία από αυτές τις τρεις οικογένειες μπορούν να παρέχουν τους βασικούς μηχανισμούς δημοσίου κλειδιού, όπως της εγκαθίδρυσης κλειδιού, της μη αποποίησης μέσω ψηφιακών υπογραφών και της κρυπτογράφησης δεδομένων. Ο RSA ανήκει στη κατηγορία των κρυπτογραφικών συστημάτων παραγοντοποίησης ακεραίου και είναι κατάλληλος για κρυπτογράφηση/αποκρυπτογράφηση δεδομένων, για την δημιουργία ψηφιακών υπογραφών και την επαλήθευσή τους καθώς και για την ασφαλή μεταφορά κλειδιών. Ο αλγόριθμος Diffie-Hellman Key Exchange (DHKE) ανήκει στη κατηγορία των κρυπτογραφικών συστημάτων διακριτού λογαρίθμου και αποτελεί μία εντυπωσιακή εφαρμογή του προβλήματος του διακριτού λογαρίθμου. Η θεμελιώδης αυτή τεχνική συμφωνίας κλειδιού υλοποιείται σε πολλά ανοιχτά και εμπορικά κρυπτογραφικά πρωτόκολλα όπως, στο SSH (Secure Shell) και στο IPsec (Internet Protocol Security). Στη τρίτη κατηγορία ανήκει το Elliptic Curve Diffie-Hellman ECDH το οποίο βρίσκεται σε πλήρη αναλογία με τον παραδοσιακό DHKE που αναφέραμε προηγουμένως, μόνο που εδώ πραγματοποιείται ανταλλαγή κλειδιού χρησιμοποιώντας ελλειπτικές καμπύλες. Κάποια από τα πιο γνωστά πρωτόκολλα ασφάλειας πρωτοκόλλων που χρησιμοποιούνται σήμερα κατά κόρον και χρησιμοποιούν ανταλλαγή και εγκαθίδρυση κλειδιού είναι το IPSec σε συνδυασμό με το IKE και το SSL. Ο βασικός στόχος οποιουδήποτε πρωτοκόλλου εγκαθίδρυσης επικυρωμένου κλειδιού είναι να διανέμει δεδομένα κλειδιού με ασφαλή τρόπο χρησιμοποιώντας πρωτόκολλα με έμμεση πιστοποίηση κλειδιού, με ρητή επιβεβαίωση κλειδιού κ.α. Στα πλαίσια της διατριβής αυτής και με σκοπό τη πρακτική μελέτη κάποιων από των πιο διαδεδομένων πρωτοκόλλων κρυπτογράφησης που παρουσιάστηκε και αναλύθηκε στα προηγούμενα κεφάλαια, αναπτύχθηκε μια εφαρμογή σε Java SE. Χρησιμοποιήθηκαν κυρίως το πλαίσιο ανάπτυξης Java Cryptography Architecture (JCA), το περιβάλλον ανάπτυξης λογισμικού netbeans, καθώς και κρυπτογραφικές βιβλιοθήκες JCE provider, και τη συλλογή Bouncy Castle.
Η μελέτη των κρυπτογραφικών αλγόριθμων δημοσίου κλειδιού οι οποίοι θα είναι ασφαλείς και μετά την έλευση των κβαντικών υπολογιστών, αποτελεί σημαντικό ερευνητικό πεδίο, καθώς οι σημερινοί αλγόριθμοι δημοσίου κλειδιού θα είναι επισφαλείς στο νέο τεχνολογικό περιβάλλον. Αλγόριθμοι οι οποίοι θα είναι ασφαλείς ακόμα και μετά την έλευση κβαντικών υπολογιστών ανήκουν στο χώρο της λεγόμενης μετα-κβαντικής κρυπτογραφίας, ωστόσο προκύπτουν συχνά θέματα στην υλοποίησή τους ή/και στην απόδοσή τους. \nΣτόχος της παρούσας διατριβής, είναι να μελετήσει, τα κρυπτογραφικά σχήματα ψηφιακών υπογραφών, στην μετα-κβαντική κρυπτογραφία. Ιδιαίτερη έμφαση θα δοθεί σε σχήματα που βασίζονται σε κρυπτογραφικές συναρτήσεις κατακερματισμού, όπως τα σχήματα ψηφιακών υπογραφών μιας χρήσης των Lamport, Merkle, W-OTS+, Merkle Trees και XMSS. Τα σχήματα αυτά θα αναλυθούν ως προς τον τρόπο λειτουργίας τους, τα χαρακτηριστικά ασφαλείας τους και θα αξιολογηθούν ως προς την απόδοσή τους σε σημερινά συμβατικά υπολογιστικά συστήματα. Για την αξιολόγηση και συγκριτική αποτίμηση της απόδοσής τους, χρησιμοποιούμε τη προγραμματιστική βιβλιοθήκη Bouncy Castle για την υλοποίηση ορισμένων σεναρίων δοκιμών, για τη σύγκριση ενός συμβατικού αλγορίθμου (RSA ψηφιακής υπογραφής), για διάφορες παραμέτρους, και ενός γνωστού αλγορίθμου μετα-κβαντικής κρυπτογραφίας για ψηφιακή υπογραφή (XMSS). \nΑπό τα αποτελέσματα των σεναρίων που πραγματοποιήθηκαν, συμπεραίνουμε ότι όσο μεγαλύτερη είναι η επεξεργαστική ισχύς του υπολογιστή, τόσο μικρότερος είναι ο χρόνος εκτέλεσης των αλγόριθμων που δοκιμάσαμε (όπως εξάλλου αναμενόταν). Ο αλγόριθμος RSA είναι ταχύτερος από τον αλγόριθμο XMSS. Το μέγεθος της υπογραφής, επηρεάζεται στον αλγόριθμο RSA, μόνο από το μήκος των κλειδιών, ενώ στον αλγόριθμο XMSS, επηρεάζεται από το αριθμό εξυπηρέτησης υπογραφών στο σχήμα (μεγαλύτερο ύψος) και την συνάρτηση κατακερματισμού που χρησιμοποιεί ο αλγόριθμος. Συμπερασματικά, οι αλγόριθμοι μετα-κβαντικής κρυπτογραφίας ψηφιακών υπογραφών παραμένουν σαφώς πιο αργοί, ωστόσο προκύπτει ότι είναι ρεαλιστικά υλοποιήσιμοι.
Η σύγχρονη κβαντική επιστήμη και τεχνολογία υπόσχονται στο εγγύς μέλλον την ανάπτυξη συσκευών ικανών να φέρουν επανάσταση σε τομείς όπως η πληροφορική, οι επικοινωνίες, οι αισθητήρες και η αποθήκευση ενέργειας, αξιοποιώντας τις αρχές της κβαντομηχανικής. Στην καρδιά αυτών των εξωτικών εφαρμογών βρίσκεται το πρόβλημα της αποτελεσματικής προετοιμασίας των κβαντικών καταστάσεων. Αυτή η διατριβή αξιοποιεί προηγμένες μεθόδους από τον κβαντικό βέλτιστο έλεγχο για να αντιμετωπίσει βασικές προκλήσεις στην προετοιμασία κβαντικών καταστάσεων, δίνοντας έμφαση στην αναδυόμενη εφαρμογή της κβαντικής αποθήκευσης ενέργειας, προχωρώντας από απλούστερα συστήματα σε συστήματα υψηλότερης πολυπλοκότητας. Ξεκινάμε λύνοντας το πρόβλημα βέλτιστου ελέγχου ελάχιστου χρόνου για τη δημιουργία μιας ομοιόμορφης υπέρθεσης σε ένα κβαντικό σύστημα δύο επιπέδων, μια κατάσταση που χρησιμοποιείται εκτενώς στον αλγόριθμο κβαντικής αναζήτησης του Grover, χρησιμοποιώντας μόνο ένα εγκάρσιο πεδίο ελέγχου περιορισμένου πλάτους. Εξάγουμε αυστηρά βέλτιστες ακολουθίες παλμών τύπου bang-bang για όλους τους λόγους μέγιστου πλάτους ελέγχου και σταθεράς αποσυντονισμού του κβαντικού ψηφίου. Στη συνέχεια, αντιμετωπίζουμε το πρόβλημα της αποτελεσματικής μεταφοράς πληθυσμού σε ένα ατομικό σύστημα τριών επιπέδων τύπου Λ με απώλειες, το οποίο είναι σημαντικό για την κβαντική ανίχνευση. Απεικονίζουμε αυτό το πρόβλημα στο απλούστερο πρόβλημα του βέλτιστου ελέγχου ενός κλασικού αρμονικού ταλαντωτή, το οποίο μπορεί να λυθεί αναλυτικά, και στη συνέχεια επιβεβαιώνουμε αριθμητικά ότι αυτή η λύση μπορεί να επιτύχει σχεδόν βέλτιστη μεταφορά πληθυσμού στο αρχικό κβαντικό σύστημα, προσεγγίζοντας τη βέλτιστη απόδοση για μεγαλύτερες χρονικές διάρκειες. Ακολούθως, στρέφουμε την προσοχή μας στο πρόβλημα της ταχείας φόρτισης κβαντικών μπαταριών, συσκευών που εκμεταλλεύονται τις αρχές της κβαντομηχανικής για την αποθήκευση ενέργειας, αποτελούμενες από συζευγμένα σπιν με αλληλεπίδραση Ising μεταξύ των πλησιέστερων γειτόνων. Μελετάμε δύο κβαντικές μπαταρίες, ένα ζεύγος σπιν και μια αλυσίδα τριών σπιν, στο συνηθισμένο πειραματικό πλαίσιο του πυρηνικού μαγνητικού συντονισμού με σταθερό διαμήκες πεδίο και εγκάρσιο πεδίο ελέγχου με χρονικά εξαρτώμενο πλάτος και φάση. Και για τα δύο συστήματα αναδεικνύουμε τον κρίσιμο ρόλο που παίζει ο λόγος της σύζευξης Ising προς το σταθερό διαμήκες πεδίο στον προσδιορισμό της αρχικής θεμελιώδους κατάστασης και της βέλτιστης διαδικασίας φόρτισης. Για ένα εγκάρσιο πεδίο ελέγχου με φέρουσα συχνότητα που επιλέγεται για να φέρει σε συντονισμό την αρχική κατάσταση με την κατάσταση-στόχο της υψηλότερης ενέργειας, όπου όλα τα σπιν βρίσκονται στην άνω κατάσταση, διακρίνουμε δύο περιπτώσεις. Στην περίπτωση ασθενούς σύζευξης, όπου η αρχική θεμελιώδης κατάσταση είναι αυτή με όλα τα σπιν κάτω, το βέλτιστο πλάτος ελέγχου είναι σταθερά ίσο με τη μέγιστη επιτρεπτή τιμή καθ' όλη τη διάρκεια και η φάση διαμορφώνεται κατάλληλα με τον χρόνο, ενώ η διάρκεια πλήρους φόρτισης τείνει προς το μηδέν καθώς αυξάνεται το άνω όριο του πλάτους. Στην περίπτωση ισχυρής σύζευξης, όπου η αρχική θεμελιώδης κατάσταση είναι μια κατάσταση Bell για το ζεύγος σπιν και η κατάσταση Dicke |W> μίας διέγερσης για την αλυσίδα με τα τρία σπιν, το βέλτιστο πλάτος ελέγχου μπορεί να περιέχει ιδιάζοντα διαστήματα κατά τα οποία μηδενίζεται, οπότε και η φάση του πεδίου σε αυτά δεν παίζει ρόλο. Σε αυτήν την περίπτωση, ο χρόνος πλήρους φόρτισης φαίνεται να τείνει σε μια μη μηδενική τιμή καθώς αυξάνεται το άνω όριο του πλάτους ελέγχου. Συνολικά, τα αποτελέσματα που προέκυψαν από αυτή τη διατριβή ενοποιούν τις θεωρητικές γνώσεις από τον βέλτιστο έλεγχο με σημαντικές εφαρμογές στις κβαντικές τεχνολογίες.
Η ραγδαία πρόοδος των κβαντικών υπολογιστικών απειλεί τη μακροχρόνια ασφάλεια της συμβατικής κρυπτογραφίας και πιο συγκεκριμένα αλγόριθμους όπως ο RSA και αλγόριθμους ελλειπτικών καμπύλων (EC). Οι αλγόριθμοι αυτοί αποτελούν σήμερα τη βάση της ασφαλής επικοινωνίας στο παγκόσμιο διαδίκτυο. Η εξέλιξη αυτή καθιστά επιτακτική τη μετάβαση σε μετακβαντικούς αλγορίθμους, ικανούς να παραμένουν ασφαλείς ακόμη και απέναντι σε κβαντικούς υπολογιστές. Στο πλαίσιο αυτό, η παρούσα διατριβή μελετά τους Μηχανισμούς Ενθυλάκωσης Κλειδιών (Key Encapsulation Mechanisms - KEMs) ως την κεντρική αρχιτεκτονική ανταλλαγής κλειδιών μεταξύ δύο πλευρών στην κλασική και μετα-κβαντική εποχή. Αρχικά, παρουσιάζονται τυπικοί ορισμοί για τα KEMs και αναλύονται οι αντίστοιχες έννοιες ασφάλειας όπως και τα μοντέλα επιθέσεων. Στη συνέχεια εξετάζεται ο ρόλος των αλγόριθμων παραγωγής κλειδιών (Key Derivation Functions) οι οποίοι μετατρέπουν ένα κοινό μυστικό ενός KEM σε τελικά κλειδιά πρωτοκόλλου με κατάλληλο μήκος και ομοιομορφία. Ακολουθεί η μελέτη κλασικών KEMs, όπως ο RSA-KEM, FFDH-KEM και ECDH-KEM, οι οποίοι βασίζονται στα γνωστά μαθηματικά προβλήματα παραγοντοποίησης, διακριτού λογαρίθμου και διακριτού λογαρίθμου σε ελλειπτικές καμπύλες αντίστοιχα, αναδεικνύοντας τόσο τα πλεονεκτήματα όσο και τους περιορισμούς τους υπό την απειλή κβαντικών υπολογιστών. Το κύριο μέρος της διατριβής επικεντρώνεται σε μετα-κβαντικά KEMs που συμμετείχαν ή επιλέχθηκαν στη διαδικασία τυποποίησης του NIST, και συγκεκριμένα στους ML-KEM (πρώην CRYSTALS-Kyber), HQC-KEM και Classic McEliece KEM. Για κάθε σχήμα παρουσιάζονται τα μαθηματικά θεμέλια, οι διαδικασίες παραγωγής κλειδιών, ενθυλάκωσης και αποενθυλάκωσης, καθώς και οι εγγυήσεις ασφάλειας που επιτυγχάνονται μέσω των συγκεκριμένων πρωτοκόλλων. Τέλος, πραγματοποιείται συγκριτική αξιολόγηση των υπό εξέταση KEMs ως προς το μέγεθος δημοσίων κλειδιών, το μέγεθος των κρυπτογραφημένων μηνυμάτων, τους χρόνους για κάθε εσωτερική διαδικασία του αλγορίθμου, καθώς και την καταλληλότητά τους για πραγματικές εφαρμογές (υβριδική δημόσια κρυπτογραφία, πρωτόκολλα ασφαλούς επικοινωνίας τύπου TLS κ.α) ή συμβατικούς υπολογιστές.
Στην παρούσα διατριβή μελετήθηκε η δυνατότητα υλοποίησης συστημάτων κβαντικού υπολογισμού που βασίζονται σε εναλλακτικούς τύπους απεικόνισης κβαντικής πληροφορίας. Μελετήθηκαν δύο κύριες τεχνικές. Η πρώτη βασίστηκε σε αρχιτεκτονική πλέγματος άμεσης γειτνίασης, στην οποία προτάθηκε μηχανισμός εκτέλεσης κβαντικού υπολογισμού με τη χρήση ενός μόνο παλμού σε κάθε υπολογιστικό βήμα. Η εναλλακτική απεικόνιση βασίστηκε στη διαδικασία της τηλεμεταφοράς για την επίτευξη της επιθυμητής διάταξης των κβαντικών μπιτ. Το γεγονός ότι μόνο ένας παλμός εφαρμόζεται σε κάθε βήμα, μπορεί να μειώσει το λάθος που οφείλεται σε αλληλεπιδράσεις κβαντικών μπιτ λόγω διάχυσης του σήματος. Συνεπώς, αν μία υλοποίηση υποστηρίζει αποτελεσματικές πράξεις κβαντικής τηλεμεταφοράς, η μεθοδολογία μπορεί να οδηγήσει σε αρκετά σημαντική μείωση του συνολικού θορύβου. Στη δεύτερη τεχνική, χρησιμοποιήθηκαν τα ανώτερα ενεργειακά επίπεδα ενός κβαντικού μπιτ τύπου τρανσμόν (transmon) για την αποθήκευση κβαντικής πληροφορίας. Μέσω θεωρητικής απόδειξης και πειραμάτων που εκτελέστηκαν στους κβαντικούς επεξεργαστές της IBM Quantum Platform αποδείχθηκε ότι μπορεί να επιτευχθεί διεμπλοκή σε λογικό επίπεδο χρησιμοποιώντας τους βαθμούς ελευθερίας ενός μόνο συστήματος. Αυτό μπορεί να έχει ως αποτέλεσμα τη μείωση των αναγκαίων παλμών σύζευξης, που είναι η κύρια πηγή θορύβου στους σύγχρονους κβαντικούς επεξεργαστές.
Η σημερινή εποχή χαρακτηρίζεται από την ολοένα αυξανόμενη ενσωμάτωση των ηλεκτρονικών υπολογιστών και των ενσωματωμένων συστημάτων σε όλες τις πτυχές της καθημερινής μας ζωής. Τα ολοκληρωμένα κυκλώματα συνεχώς σμικρύνονται, γίνονται ταχύτερα, απαιτούν όλο και μικρότερα ποσά ενέργειας με τη βοήθεια νέων υλικών και αρχιτεκτονικών. Αυτό έχει ως αποτέλεσμα οι ηλεκτρονικές συσκευές να βρίσκουν όλο και περισσότερες εφαρμογές σε όλους τους τομείς της ζωής μας και με τον καιρό να μετατρέπονται σε ένα αόρατο και απαραίτητο στρώμα διεπαφής μας με το περιβάλλον. Το αντικείμενο με το οποίο ασχολείται μέχρι στιγμής η παρούσα διατριβή είναι η ελαχιστοποίηση λογικών εκφράσεων ’’αποκλειστικού ή” (XOR) για τυχαία λογική συνάρτηση, και πιο συγκεκριμένα με τη μείωση των όρων από τους οποίους αυτή αποτελείται καθώς και με την απεικόνιση τέτοιων εκφράσεων σε αρχιτεκτονικές νέων τεχνολογιών όπως οι κβαντικοί υπολογιστές. Ένα ολοκληρωμένο κύκλωμα αποτελεί την πρακτική υλοποίηση μιας τέτοιας λογικής έκφρασης. Κατά συνέπεια, γίνεται προσπάθεια για την βελτιστοποίηση λογικών κυκλωμάτων. Η πιο γνωστή τέτοια κατηγορία εκφράσεων είναι οι λεγάμενες εκφράσεις ESOP (Exclusive or Sum Of Products), όπου μια λογική συνάρτηση εκφράζεται ως άθροισμα XOR από λογικά γινόμενα. Μια άλλη πιο γενική κατηγορία είναι οι ESCT (Exclusive or Sum of Complex Terms) εκφράσεις, οι οποίες μπορούν να θεωρηθούν ως επέκταση των ESOP, αφού πλέον οι όροι ονομάζονται σύνθετοι (complex terms) και δεν περιλαμβάνουν μόνο τη λογική πράξη ΚΑΙ ανάμεσα στις μεταβλητές, αλλά εν γένει οποιαδήποτε λογική πράξη (συνάρτηση δύο εισόδων μιας εξόδου). Η σημασία των παραπάνω εκφράσεων τονίζεται και από το γεγονός ότι μπορούν, με τετριμμένο τρόπο, να απεικονισθούν σε αντιστρέψιμες αρχιτεκτονικές. Ένα αντιστρέψιμο λογικό κύκλωμα έχει μικρότερες απώλειες ενέργειας σε σχέση με ένα τυπικό λογικό κύκλωμα και για το λόγο αυτό η σύνθεση αντιστρέψιμων κυκλωμάτων θεωρείται το μέλλον στη λογική σχεδίαση. Ένα ακόμα σημαντικό τους πλεονέκτημα είναι ότι μπορούν να χρησιμοποιηθούν και για τη σύνθεση κβαντικών κυκλωμάτων. Η ελαχιστοποίηση αυτών των εκφράσεων καθώς και οι κβαντικές επεκτάσεις τους είναι το κύριο αντικείμενο έρευνας με το οποίο ασχολείται αυτή η εργασία. Η εργασία αυτή ασχολείται καταρχήν, με το θεωρητικό υπόβαθρο της ελαχιστοποίησης τέτοιων εκφράσεων. Αποδεικνύονται θεωρήματα τα οποία υποδεικνύουν μια μεθοδολογία για την εύρεση ελάχιστης ESCT έκφρασης για οποιαδήποτε πλήρως ορισμένη λογική συνάρτηση μοναδικής εξόδου, αλλά με περιορισμό ως προς τον αριθμό των όρων σε μια ελάχιστη έκφρασή της ή με περιορισμό ως προς τον αριθμό των μεταβλητών εισόδου της. Γίνεται, επιπλέον, μελέτη πώς τα παραπάνω συμπεράσματα μπορούν να χρησιμοποιηθούν για ευριστική ελαχιστοποίηση συναρτήσεων που δεν εμπίπτουν στους παραπάνω περιορισμούς. Στη συνέχεια τα παραπάνω πορίσματα επεκτείνονται, ευριστικά, για ατελώς ορισμένες λογικές συναρτήσεις πολλών εξόδων. Η παραπάνω θεωρητική μελέτη του προβλήματος ελαχιστοποίησης εκφράσεων ’’αποκλειστικού ή”, χρησιμοποιείται για την υλοποίηση συμβατικών και κβαντικών αλγορίθμων οι οποίοι, όπως φαίνεται και από τα πειραματικά αποτελέσματα, δίνουν καλύτερα αποτελέσματα από τους αντίστοιχους της διεθνούς βιβλιογραφίας. Πιο συγκεκριμένα, οι κβαντικοί αλγόριθμοι που μπορούν να χρησιμοποιηθούν για την ακριβή ελαχιστοποίηση εκφράσεων ’’αποκλειστικού ή” και καταδεικνύουν τη σαφή υπεροχή των κβαντικών υπολογιστών έναντι των κλασικών τους αναλόγων. Τέλος, πραγματοποιείται εφαρμογή των παραπάνω αποτελεσμάτων στο πεδίο της κρυπτογράφησης και των ασφαλών υπολογισμών. Πιο συγκεκριμένα, γίνεται χρήση των αλγορίθμων ελαχιστοποίησης εκφράσεων ESCT για την επίτευξη έως και 39% λιγότερου κόστους επικοινωνίας σε σχέση με τις υπόλοιπες αντίστοιχες προσπάθειες της βιβλιογραφίας. Κατά τη διάρκεια της εκπόνησης της συγκεκριμένης διατριβής έχουν προκύψει οι δημοσιεύσεις που παρουσιάζονται στον κατάλογο δημοσιεύσεων που ακολoυθεί.