Γλώσσες Κβαντικού Προγραμματισμού Θεωρία Και Υλοποίηση

Abstract

Σκοπός αυτής της διπλωματικής εργασίας είναι η μελέτη των γλωσσών προγραμματισμού που βασίζονται στις αρχές του κβαντικού μοντέλου υπολογισμών. Μελετήσαμε δύο γλώσσες που έχουν προταθεί στην πρόσφατη βιβλιογραφία: την QPL (Selinger, 2004) και την QML (Grattage and Altenkirch, 2005). Παραλλαγή της δεύτερης αποτελεί η NTUA-QML, μία νέα γλώσσα κβαντικού προγραμματισμού την οποία σχεδιάσαμε στο πλαίσιο αυτής της εργασίας. Κατασκευάσαμε μια υλοποίηση της QPL με εξομοίωση σε συμβατικούς υπολογιστές, γραμμένη στη γλώσσα Haskell, καθώς και μια υλοποίηση της NTUA-QML με μετασχηματισμό στην QPL. Για τον έλεγχο και την επίδειξη των υλοποιήσεων, μεταφράσαμε ορισμένα παραδείγματα γνωστών κβαντικών αλγορίθμων σε NTUA-QML. Η δυνατότητα αξιοποίησης των χαρακτηριστικών της θεωρίας της κβαντομηχανικής για τη διενέργεια υπολογισμών κίνησε για πρώτη φορά το ενδιαφέρον των ερευνητών περίπου πριν από δύο δεκαετίες. Η ανακάλυψη όμως του αλγορίθμου παραγοντοποίησης ακεραίων του Shor, ενός αλγορίθμου πολυωνυμικής πολυπλοκότητας για ένα πρόβλημα το οποίο πιστεύεται πως δεν ανήκει στο P, έφερε τους κβαντικούς υπολογισμούς στο επίκεντρο εξαιτίας και των τεράστιων επιπτώσεων που θα είχε η ύπαρξη μιας πρακτικής υλοποίησης ενός τέτοιου αλγορίθμου στον τομέα της κρυπτανάλυσης. Από τότε η έρευνα έχει επικεντρωθεί στην προσπάθεια κατασκευής πρακτικών κβαντικών υπολογιστών. Οι ιδιαιτερότητες του κβαντικού μοντέλου υπολογισμών, και η αντίθεσή του με την διαίσθηση του κλασικού προγραμματιστή είναι ένας από τους λόγους που δεν έχουν αναπτυχθεί ακόμα πολλοί ενδιαφέροντες κβαντικοί αλγόριθμοι. Η ύπαρξη γλωσσών υψηλού επιπέδου που θα επέτρεπαν στο χρήστη τους να σκέφτεται σε ένα πιο αφηρημένο επίπεδο χωρίς να απασχολείται με λεπτομέρειες υλοποίησης, όπως τα κβαντικά κυκλώματα ίσως να βοηθούσε αυτήν την κατάσταση. Μία καλή γλώσσα κβαντικού προγραμματισμού θα πρέπει να ενσωματώνει τους περιορισμούς και τις δυνάμεις των κβαντικών υπολογισμών διευκολύνοντας το χρήστη να εκφράσει προχωρημένους αλγορίθμους με φυσικό τρόπο.