Η εκπόνηση της παρούσας διατριβής αφορά το πεδίο της Βελτιστοποίησης Αλγορίθμων και πιο συγκεκριμένα με το πεδίο της συνδυαστικής βελτιστοποίησης. Στην ουσία πραγματεύεται τη διερεύνηση μεθευρετικών μεθόδων που βασίζονται σε συμβατικές ή μη συμβατικές, εμπνευσμένες από τον κβαντικό υπολογισμό τεχνικές με σκοπό την εφαρμογή τους σε αλγόριθμους βελτιστοποίησης για την επίλυση προβλημάτων από τον πραγματικό κόσμο. Πιο συγκεκριμένα, παρουσιάζουμε την κβαντικά εμπνευσμένη μεθευρετική μέθοδο qGVNS (quantum General Variable Neighborhood Search), την οποία χρησιμοποιούμε για να επιλύσουμε το πρόβλημα του πλανόδιου πωλητή (Travelling Salesman Problem, TSP εν συντομία) όπως επίσης και το πρόβλημα του πλανόδιου πωλητή με χρονικά παράθυρα (Travelling Salesman Problem with Time Windows, TSPTW εν συντομία). Ο τελικός σκοπός είναι η επίλυση ρεαλιστικών προβλημάτων από τον πραγματικό κόσμο που έχουν μοντελοποιηθεί σαν προβλήματα βελτιστοποίησης (TSP ή TSPTW) χρησιμοποι-ώντας τις μη συμβατικές μεθευρετικές μεθόδους που αναπτύξαμε. Το πρόβλημα του πλανόδιου πωλητή χρησιμοποιείται ως σημείο αναφοράς σε πολλές μεθόδους βελτιστοποίησης και έχει πλήθος εφαρμογών σε πολλές και διαφορετικές περιοχές, όπως στην τεχνητή νοημοσύνη, την βιοπληροφορικη, την βέλτιστη αναζήτηση διαδρομών και αλλού. Σε αυτή τη διατριβή διερευνούμε ιδιαίτερα την εκδοχή του TSP προβλήματος, που αποτελείται από κάποιους επιπρόσθετους περιορισμούς, όπως τα χρονικά παράθυρα (time windows). Η εκδοχή αυτή είναι γνωστή ως TSPTW (Travelling Salesman Problem with Time Windows). Με βάση το πρόβλημα του πλανόδιου πωλητή (TSP) αλλά και το πρόβλημα του πλανόδιου πωλητή με χρονικά παράθυρα (TSPTW) επιλύσαμε το πρόβλημα περισυλλογής απορριμάτων από τον πραγματικό κόσμο, σε δύο διαφορετικές εκδοχές του. Το απλό πρόβλημα της περισυλλογής των απορριμάτων όπως και το πρόβλημα περισυλλογής των απορριμάτων με χρονικά παράθυρα. Συνεχίζοντας, πραγματοποιήσαμε αναλυτική και διεξοδική συγκριτική μελέτη απόδοσης ανά-μεσα στην νέα κβαντικά εμπνευσμένη μέθοδο που προτείναμε και σε άλλες συμβατικές μεθόδους. Η παρούσα διατριβή ολοκληρώνεται με την παρουσίαση μερικών βασικών σημείων και βιβλιογραφίας σχετική με την κβαντική βελτιστοποίηση και την κβαντική ανόπτηση (quantum annealing).
Στην παρούσα διατριβή μελετήθηκε η δυνατότητα υλοποίησης συστημάτων κβαντικού υπολογισμού που βασίζονται σε εναλλακτικούς τύπους απεικόνισης κβαντικής πληροφορίας. Μελετήθηκαν δύο κύριες τεχνικές. Η πρώτη βασίστηκε σε αρχιτεκτονική πλέγματος άμεσης γειτνίασης, στην οποία προτάθηκε μηχανισμός εκτέλεσης κβαντικού υπολογισμού με τη χρήση ενός μόνο παλμού σε κάθε υπολογιστικό βήμα. Η εναλλακτική απεικόνιση βασίστηκε στη διαδικασία της τηλεμεταφοράς για την επίτευξη της επιθυμητής διάταξης των κβαντικών μπιτ. Το γεγονός ότι μόνο ένας παλμός εφαρμόζεται σε κάθε βήμα, μπορεί να μειώσει το λάθος που οφείλεται σε αλληλεπιδράσεις κβαντικών μπιτ λόγω διάχυσης του σήματος. Συνεπώς, αν μία υλοποίηση υποστηρίζει αποτελεσματικές πράξεις κβαντικής τηλεμεταφοράς, η μεθοδολογία μπορεί να οδηγήσει σε αρκετά σημαντική μείωση του συνολικού θορύβου. Στη δεύτερη τεχνική, χρησιμοποιήθηκαν τα ανώτερα ενεργειακά επίπεδα ενός κβαντικού μπιτ τύπου τρανσμόν (transmon) για την αποθήκευση κβαντικής πληροφορίας. Μέσω θεωρητικής απόδειξης και πειραμάτων που εκτελέστηκαν στους κβαντικούς επεξεργαστές της IBM Quantum Platform αποδείχθηκε ότι μπορεί να επιτευχθεί διεμπλοκή σε λογικό επίπεδο χρησιμοποιώντας τους βαθμούς ελευθερίας ενός μόνο συστήματος. Αυτό μπορεί να έχει ως αποτέλεσμα τη μείωση των αναγκαίων παλμών σύζευξης, που είναι η κύρια πηγή θορύβου στους σύγχρονους κβαντικούς επεξεργαστές.
Η Κβαντική Πληροφορία είναι μια ιδιότητα των κβαντικών συστημάτων που σχετίζεται με την κβαντομηχανική επαλληλία και την συσχέτιση των συστημάτων σε Ενδιαπλοκή. Λόγω της αλληλεπίδρασης με το κλασικό περιβάλλον η Ενδιαπλοκή χάνεται ταχύτατα με συνέπεια να περιορίζεται δραματικά η πρακτική της χρησιμότητα. Πραγματοποιήθηκε διερεύνηση διαφόρων διατάξεων κβαντικών συστημάτων είτε σε αλληλεπίδραση με άλλα συστήματα είτε μεμονωμένων, αλλά με την συνθήκη το αντίστοιχο κλασικό μη γραμμικό σύστημα να είναι χαοτικό ή ολοκληρώσιμο. Ερευνητικά αποτελέσματα: 1. Ο ρυθμός μεταβολής της Ενδιαπλοκής με την μεταβολή μιας παραμέτρου σύζευξης φράσσεται από την καμπυλότητα των ενεργειακών επιπέδων. Το αποτέλεσμα έχει γενική ισχύ, διότι βασίζεται σε γενικές ιδιότητες των τυχαίων πινάκων που κωδικοποιούν την χαοτική ή την κανονική συμπεριφορά των συστημάτων,2. Ο ρόλος της λεπτομερούς δομής του κλασικού χώρου των φάσεων. Ερευνήθηκε η εξάρτηση της Ενδιαπλοκής από την τιμή παραμέτρου σύζευξης σε σχέση με το διάγραμμα διακλαδώσεων του Βηματικού Στρόβου, καθώς και σε σχέση με την ύπαρξη Κβαντικών Ουλών, 3. Η μη γραμμικότητα συστημάτων σε συνδυασμό με την παρουσία εξωτερικών πεδίων μπορεί να οδηγήσει σε βέλτιστες τιμές ορισμένων παραμέτρων που ευνοούν την δημιουργία Ενδιαπλοκής θερμικά. Μελετήθηκε κατάλληλο μοντέλο, 4. Κβαντικός δίαυλος βρίσκεται σε αλληλεπίδραση με το τοπικό περιβάλλον. Οι ιδιότητες του τοπικού περιβάλλοντος (χάος ή κανονικότητα) μπορούν να επηρεάσουν τις δυνατότητες του διαύλου, 5. Ένα ανοικτό κβαντικό σύστημα αλληλεπιδρά με τοπικό κβαντικό περιβάλλον λίγων βαθμών ελευθερίας, καθώς και με ένα ολικό Μαρκοβιανό περιβάλλον και τελικά προκαλείται απώλεια κβαντικής συνάφειας. Διερευνήθηκε, αριθμητικά, ο τρόπος με τον οποίο, οι κλασικές ιδιότητες του τοπικού περιβάλλοντος επηρεάζουν τον ρυθμό απώλειας συνάφειας του συστήματος.
Στις επικοινωνίες ανάμεσα σε ανοιχτά συστήματα υπάρχουν τέσσερις κύριες κατηγορίες απειλών: Μη εξουσιοδοτημένη απόκτηση της πληροφορίας, Μη εξουσιοδοτημένη τροποποίηση της πληροφορίας, Πλαστοπροσωπία χρήστη, Αποκήρυξη της επικοινωνίας. Ο βασικός μηχανισμός για την παροχή ασφάλειας με τα χαρακτηριστικά που περιγράφηκαν πιο πάνω είναι η κρυπτογραφία. Οι συμμετρικοί αλγόριθμοι κρυπτογραφίας είναι πολύ ασφαλείς, γρήγοροι και έχουν διαδεδομένη χρήση. Ωστόσο, υπάρχουν διάφορες ελλείψεις που σχετίζονται με σχήματα συμμετρικού κλειδιού, όπως το πρόβλημα της διανομής κλειδιού, το μεγάλο πλήθος των κλειδιών που απαιτούνται και επίσης δεν παρέχουν καμία προστασία ενάντια σε επιθέσεις της επικοινωνίας. Τα παραπάνω προβλήματα λύνονται με τη χρήση ασύμμετρων αλγορίθμων ή αλλιώς δημοσίου κλειδιού σε καλά σχεδιασμένα πρωτόκολλα ασφάλειας και ανταλλαγής κλειδιού. Υπάρχουν τρεις κυρίαρχες οικογένειες αλγορίθμων δημοσίου κλειδιού οι οποίες έχουν πρακτικό αντίκρισμα. Μπορούν να ταξινομηθούν με βάση το υπολογιστικό πρόβλημα που τις χαρακτηρίζουν: Συστήματα παραγοντοποίησης ακεραίου, Συστήματα διακριτού λογαρίθμου, Συστήματα ελλειπτικών καμπυλών. Κάθε μία από αυτές τις τρεις οικογένειες μπορούν να παρέχουν τους βασικούς μηχανισμούς δημοσίου κλειδιού, όπως της εγκαθίδρυσης κλειδιού, της μη αποποίησης μέσω ψηφιακών υπογραφών και της κρυπτογράφησης δεδομένων. Ο 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.
Το βιβλίο αυτό βασίζεται στις διαλέξεις κβαντικής θεωρίας που έδωσα σε τριτοετείς φοιτητές του τμήματος Φυσικής του Παν/μίου Ιωαννίνων, κατά τα έτη 2012-2014. Απευθύνεται σε φοιτητές που έχουν βασικές γνώσεις διαφορικών εξισώσεων, κυματικής και κλασικής μηχανικής. Υπάρχει, ήδη, μια αρκετά εκτενής βιβλιογραφία από συγγράμματα κβαντομηχανικής στον ελληνικό και στον διεθνή χώρο. Η καινοτομία της παρούσας προσπάθειας εστιάζεται στα παρακάτω: Το γραπτό κείμενο συνοδεύεται από βιντεοδιαλέξεις που έχουν αναρτηθεί στο διαδίκτυο και οι σχετικοί σύνδεσμοι δίνονται στο τέλος κάθε κεφαλαίου. Οι βιντεοδιαλέξεις αυτές έχουν βιντεοσκοπηθεί από τον συγγραφέα, αποτελούν τις κανονικές διαλέξεις, που δόθηκαν στα πλαίσια των εξαμηνιαίων υποχρεωτικών μαθημάτων Κβαντική Θεωρία Ι και Κβαντική Θεωρία ΙΙ και απευθύνονται σε τριτοετείς φοιτητές του τμήματος Φυσικής του Πανεπιστημίου Ιωαννίνων. Στις διαλέξεις αυτές παρουσιάζεται μία λεπτομερέστερη ανάλυση των θεμάτων, η οποία στην πράξη έχει αποδειχτεί αρκετά χρήσιμη για τους φοιτητές που παρακολούθησαν τα μαθήματα. Κατά τη διάρκεια των βιντεοδιαλέξεων προτείνονται απλές ασκήσεις στους φοιτητές, πολλές από τις οποίες έχουν περιληφθεί και στο γραπτό κείμενο. Το γραπτό κείμενο συνοδεύεται από τις διαφάνειες των διαλέξεων σε μορφή pdf, οι οποίες από μόνες τους αποτελούν μια συνοπτική παρουσίαση των περιεχομένων, χρήσιμη για μια πρώτη ανάγνωση, αλλά και για μία επανάληψη της ύλης. Κάθε κεφάλαιο συνοδεύεται από λυμένες ασκήσεις, άλυτες ασκήσεις, καθώς και (για τα περισσότερα κεφάλαια) από ασκήσεις πολλαπλής επιλογής, που συνοδεύονται από επεξήγηση της ορθής απάντησης. Έτσι παρέχεται στο φοιτητή μια εκτενής ποικιλία εφαρμογών της διδαχθείσης ύλης. Η ανάλυση των θεωρητικών θεμάτων γίνεται σε, όσο το δυνατόν, πιο απλό επίπεδο και συνοπτικά, με έμφαση στην ουσία και αποφεύγοντας εκτενείς συζητήσεις, που αν και διαφωτιστικές, ορισμένες φορές μπορεί να γίνουν κουραστικές και να αποπροσανατολίσουν από την ουσία. Τα θέματα που πραγματευόμαστε καλύπτουν, με αρκετή πληρότητα, την ύλη ενός προπτυχιακού ετήσιου μαθήματος κβαντομηχανικής ή αντίστοιχα δύο εξαμηνιαίων μαθημάτων. Ο συμβολισμός Dirac εισάγεται νωρίς και χρησιμοποιείται σε σημαντικό μέρος του βιβλίου, έτσι ώστε οι φοιτητές να αντιληφθούν την αναπαράσταση της θέσης ως μια ειδική περίπτωση του γενικότερου φορμαλισμού. Επίσης, καλύπτονται συνοπτικά και θέματα, που εμφανίζονται, κυρίως σε πιο προχωρημένα ή και μεταπτυχιακά μαθήματα, όπως μετασχηματισμοί κβαντικών καταστάσεων και τελεστών και πρόσθεση στροφορμών.
Η ραγδαία πρόοδος των κβαντικών υπολογιστικών απειλεί τη μακροχρόνια ασφάλεια της συμβατικής κρυπτογραφίας και πιο συγκεκριμένα αλγόριθμους όπως ο 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 κ.α) ή συμβατικούς υπολογιστές.