Κβαντικός Υπολογισμός: Αλγόριθμοι, Υλοποιήσεις, και Εφαρμογές στην Κρυπτογραφία και στην Θεωρία Γράφων

Abstract

Σε αυτή τη διπλωματική εργασία, εξετάζουμε τον Κβαντικό Υπολογισμό μέσω ποικίλων υλοποιήσεων και εφαρμογών. Οι κβαντικοί αλγόριθμοι παρέχουν σημαντικά πλεονεκτήματα σε σχέση με τους κλασσικούς αλγόριθμους καθώς μπορούν να βοηθήσουν στην επίλυση προβλημάτων που είναι ακόμη και εγγενώς δύσκολο να λυθούν με τον κλασσικό υπολογισμό. Συγκεκριμένα, πρώτον, εμβαθύνουμε στην βασική κβαντική σημειογραφία και ύστερα εξετάζουμε τα μαθηματικά εργαλεία που θα χρειαστούμε. Έπειτα, δείχνουμε ορισμένα αμιγώς κβαντικά πρωτόκολλα όπως η Υπερπυκνή Κωδικοποίηση και η Κβαντική Τηλεμεταφορά. Στη συνέχεια, για τους αλγόριθμους Deutsch και Deutsch-Jozsa, τον αλγόριθμο Bernstein-Vazirani, τον αλγόριθμο του Simon, τον αλγόριθμο Shor και τον αλγόριθμο του Grover, αναλύουμε βήμα προς βήμα το πρόβλημα, την επίλυση τόσο στην περίπτωση των κλασσικών υπολογιστών όσο και στην περίπτωση των κβαντικών υπολογιστών, υλοποιούμε και διεξάγουμε αριθμητικά πειράματα και αξιολογήσεις χρησιμοποιώντας την βιβλιοθήκη Qiskit της Python και τρέχουμε τα πειράματά μας σε προσομοιωτές αλλά και σε πραγματικούς Κβαντικούς Υπολογιστές (IBM Quantum, D-Wave, κ.λπ.) και τέλος, εξετάζουμε ορισμένες εφαρμογές στον πραγματικό κόσμο. Πιο αναλυτικά, ξεκινάμε με τον αλγόριθμο Deutsch & Deutsch-Jozsa ο οποίος προσδιορίζει εάν μια συνάρτηση είναι σταθερή ή ισορροπημένη. Στη συνέχεια, εξετάζουμε τον αλγόριθμο του Bernstein-Vazirani, που είναι μια ειδική περίπτωση του προηγούμενου αλγορίθμου, ο οποίος βρίσκει μια συμβολοσειρά που ικανοποιεί ορισμένες ιδιότητες. Ύστερα, μελετάμε τον αλγόριθμο του Simon ο οποίος βρίσκει επίσης μια συμβολοσειρά κάτω από ορισμένες παραδοχές και μάλιστα, αυτός ο αλγόριθμος αποτέλεσε την έμπνευση πίσω από τον αλγόριθμο του Shor, για τον οποίο αναλύουμε τον τρόπο με τον οποίο επιλύεται το πρόβλημα παραγοντοποίησης ακέραιων αριθμών. Τέλος, ασχολούμαστε με τον αλγόριθμο του Grover, ο οποίος παρέχει έναν αλγόριθμο κβαντικής αναζήτησης και τον χρησιμοποιούμε για την επίλυση κλασσικών προβλημάτων αναζήτησης. Συγκεκριμένα, εξετάζουμε το πρόβλημα Max-Cut και αξιοποιούμε τον αλγόριθμο του Grover αλλά και κάποιες ακόμη τεχνικές για την επίλυση αυτού του προβλήματος. Τέλος, μετά από κάθε ανάλυση από τους παραπάνω αλγορίθμους, ολοκληρώνουμε την μελέτη μας συζητώντας σύγχρονες εφαρμογές, άλλοτε απλές, όπως η εύρεση μιας συμβολοσειράς και άλλοτε πιο σύνθετες, όπως η επίθεση στο κρυπτογραφικό πρωτόκολλο RSA.