Grad Student Επιλύει Πρόβλημα Κβαντικής Επαλήθευσης

Από τη θεωρητική ίδρυσή του τη δεκαετία του 1980, ο κβαντικός υπολογιστής έχει προβληθεί ως το επόμενο μεγάλο άλμα στην τεχνολογία της πληροφορίας. Εκμεταλλευόμενοι τις περίεργες ιδιότητες των κβαντικών σωματιδίων, οι κβαντικοί υπολογιστές θα μπορούσαν θεωρητικά να εκτελούν λειτουργίες που θα ήταν αδύνατες ή θα διαρκούσαν εξαιρετικά μεγάλο χρονικό διάστημα σε έναν κλασικό ψηφιακό υπολογιστή.

Ωστόσο, παρά τις πρόσφατες εξελίξεις στην τεχνολογία των κβαντικών υπολογιστών, εξακολουθεί να υπάρχει ένα επίμονο, πιεστικό ερώτημα σχετικά με την τεχνολογία:συγκεκριμένα, εάν ζητήσετε από έναν κβαντικό υπολογιστή να εκτελέσει έναν υπολογισμό για εσάς, πώς ξέρετε ότι έχει κάνει πραγματικά αυτό που υποδείξατε; ή έκανες κάτι "κβαντικό" καθόλου;

Το ερώτημα μπορεί να ακούγεται ακαδημαϊκό, αλλά επισημαίνει ένα δυνητικά προβληματικό χαρακτηριστικό των συστημάτων κβαντικών υπολογιστών. Εάν δεν εμπιστεύεστε έναν κανονικό υπολογιστή, θα μπορούσατε θεωρητικά να τον ανοίξετε και να ελέγξετε μόνοι σας κάθε βήμα του υπολογισμού για να επαληθεύσετε ότι ο υπολογιστής έκανε όντως αυτό που του είπαν να κάνει. Όχι τόσο με τους κβαντικούς υπολογιστές. Η εσωτερική κατάσταση ενός κβαντικού υπολογιστή αποτελείται από μια υπέρθεση κλασικών καταστάσεων. Έτσι, αν προσπαθούσατε να παρατηρήσετε το εσωτερικό ενός κβαντικού υπολογιστή, η υπέρθεση θα κατέρρεε σε μια συγκεκριμένη κατάσταση. Με άλλα λόγια, αν κρυφοκοιτάγατε κάτω από την κουκούλα, θα λέγαμε, ενός κβαντικού υπολογιστή 300 qubit, το μόνο που θα βλέπατε είναι 300 κλασικά bit—1 και 0. Οι κβαντικοί υπολογιστές από τη φύση τους έχουν αυτό το χαρακτηριστικό «μαύρο κουτί», οπότε πώς υποτίθεται ότι μπορεί κανείς να επαληθεύσει ότι ένας κβαντικός υπολογιστής εκτελεί πραγματικά τη λειτουργία που νομίζει ότι είναι;

Τώρα, ένας αποφοιτητής από το UC Berkley μπορεί να βρίσκεται στο κατώφλι της επίλυσης αυτού του μακροχρόνιου προβλήματος στον κβαντικό υπολογιστή. Σε μια πρόσφατη εργασία, η Urmila Mahadev, μεταπτυχιακή φοιτήτρια στο τμήμα φυσικής στο Πανεπιστήμιο της Καλιφόρνια Μπέρκλι, περιγράφει ένα διαδραστικό πρωτόκολλο που επιτρέπει σε έναν εντελώς κλασικό παρατηρητή να επαληθεύσει χωρίς αμφιβολία ότι ένας κβαντικός υπολογιστής κάνει αυτό που υποτίθεται ότι κάνει . Το πρωτόκολλο περιλαμβάνει την κατασκευή μιας «μυστικής κατάστασης» στον κβαντικό υπολογιστή - μια κατάσταση της οποίας η περιγραφή είναι γνωστή στον κλασικό επαληθευτή αλλά όχι στον ίδιο τον κβαντικό υπολογιστή. Στη συνέχεια, ο κβαντικός υπολογιστής μπλέκει τη μυστική κατάσταση με την κατάσταση που υποτίθεται ότι μετράει. Μόλις ο υπολογιστής μετρήσει την επιδιωκόμενη κατάσταση, τόσο η μετρούμενη κατάσταση όσο και η μυστική κατάσταση καταρρέουν σε μια συγκεκριμένη κλασική κατάσταση. Εφόσον ο υπολογιστής δεν γνωρίζει τη σύνθεση του μυστικού κράτους, αλλά ο κλασικός επαληθευτής γνωρίζει, ελέγχοντας τα αποτελέσματα της λειτουργίας ο επαληθευτής μπορεί να προσδιορίσει εάν ο κβαντικός υπολογιστής πραγματοποίησε πράγματι τη λειτουργία που του ζητήθηκε. Η εργασία μπορεί να διαβαστεί πλήρως στην προτυπωμένη έκδοση arXiv.

Μαύρα κουτιά και μυστικές πολιτείες

Οι κβαντικοί υπολογιστές από τη φύση τους είναι μυστικοπαθείς. Οι κλασικοί υπολογιστές αποθηκεύουν πληροφορίες σε δυαδικά bit που παίρνουν τιμή είτε 1 είτε 0. Οι κβαντικοί υπολογιστές, από την άλλη πλευρά, αποθηκεύουν πληροφορίες σε qubits, τα οποία μπορούν να λάβουν τιμή 1, 0 ή υπέρθεση των δύο. Αφού κατασκευάσει δύο qubit υπέρθεσης, ο κβαντικός υπολογιστής θα μπλέξει αυτά τα δύο qubit έτσι ώστε οι μετρήσεις αυτών των καταστάσεων να συσχετίζονται πάντα μεταξύ τους. Η μέτρηση ενός qubit θα συμπτύξει στιγμιαία την υπέρθεση στο μπλεγμένο qubit σε μια καθορισμένη κατάσταση που μπορεί να επιτρέψει γρήγορους και ισχυρούς υπολογισμούς. Αυτός ο σχεδιασμός όμως οδηγεί σε ένα γνωσιακό πρόβλημα. Οποιαδήποτε απόπειρα παρατήρησης ενός κβαντικού υπολογιστή ενώ λειτουργεί θα καταρρέει τις μπερδεμένες υπερθέσεις qubit και έτσι θα φαίνεται στον παρατηρητή σαν να συμπεριφέρεται απλώς σαν ένας κλασικός υπολογιστής.

Το ερώτημα εάν είναι δυνατό να κατασκευαστεί ένα κλασικό σχήμα επαλήθευσης για έναν κβαντικό υπολογιστή προτάθηκε για πρώτη φορά από τον φυσικό Daniel Gottesman το 2004. Μέσα σε 4 χρόνια, οι επιστήμονες έδωσαν μια μερική απάντηση δείχνοντας ότι ένας κβαντικός υπολογιστής μπορούσε να αποδείξει τα αποτελέσματά του σε έναν επαληθευτή που είχε πρόσβαση σε έναν δικό της μικρό κβαντικό υπολογιστή. Ωστόσο, αυτή η απάντηση φαίνεται απλώς να σπρώχνει την ερώτηση ένα βήμα παραπέρα, γιατί τότε ο επαληθευτής χρειάζεται έναν τρόπο να επαληθεύσει ότι ο κβαντικός υπολογιστής του λειτουργεί όπως έπρεπε, κάτι που θα περιλαμβάνει έναν άλλο κβαντικό υπολογιστή και ούτω καθεξής.

Μπείτε στο έργο της Ουρμίλα Μαχάντεφ. Η τρέχουσα μελέτη βασίζεται στη δουλειά της που διεξήχθη το 2016, στην οποία περιγράφει μια κρυπτογραφική μέθοδο για τη δημιουργία μιας «μυστικής κατάστασης» σε έναν κβαντικό υπολογιστή. Η διαδικασία περιλαμβάνει τη δημιουργία μιας συνάρτησης "trap-door", μια λειτουργία που είναι εύκολο να εκτελεστεί αλλά δύσκολο να αντιστραφεί, εκτός εάν έχετε ένα μυστικό κρυπτογραφικό κλειδί. Αυτή η συνάρτηση πρέπει να είναι 2-προς-1. έχοντας δύο εισόδους που αντιστοιχούν σε κάθε έξοδο. Σκεφτείτε την τετράγωνη συνάρτηση που έχει δύο εισόδους σε κάθε έξοδο (και -3 και 3 αντιστοιχούν στο 9 ως έξοδο) Στη συνέχεια ζητάτε από τον υπολογιστή να δημιουργήσει μια υπέρθεση όλων των πιθανών καταστάσεων εισόδου σε αυτήν τη συνάρτηση, εκτελέστε τη συνάρτηση σε αυτήν την υπέρθεση, η οποία δημιουργεί μια νέα υπέρθεση που αποτελείται από τις πιθανές εξόδους της συνάρτησης.

Στη συνέχεια, ο υπολογιστής μετρά την υπέρθεση εξόδου συμπτύσσοντάς την σε μια καθορισμένη κατάσταση και, εφόσον τα δύο είναι μπερδεμένα, η κατάσταση εισόδου θα συμπτυχθεί σε μια υπέρθεση των αντίστοιχων εισόδων. Έτσι, εάν χρησιμοποιείτε τη συνάρτηση τετραγώνου και μια μέτρηση σας δίνει έξοδο 9, η κατάσταση εισόδου συμπτύσσεται σε μια υπέρθεση 3 και -3. Το πιο σημαντικό, επειδή έχουν το μυστικό κλειδί, ο εξωτερικός επαληθευτής γνωρίζει τη σύνθεση της κατάστασης εισαγωγής, αλλά ο υπολογιστής δεν γνωρίζει και ο υπολογιστής δεν μπορεί να ελέγξει την κατάσταση εισόδου, επειδή κάτι τέτοιο θα κατέρρεε την υπέρθεση και θα καταστρέψει τις αρχικές πληροφορίες. Έτσι, η κατάσταση εισόδου είναι ένα "μυστικό" για τον ίδιο τον υπολογιστή.

Πώς να δημιουργήσετε έναν κβαντικό επαληθευτή

Οπλισμένοι με τη γνώση του τρόπου δημιουργίας μιας μυστικής κατάστασης, μπορεί κανείς να κατασκευάσει έναν κλασικό κβαντικό επαληθευτή ως εξής:Πρώτον, κατασκευάζεις μια μυστική κατάσταση με τη μέθοδο που περιγράφηκε προηγουμένως. Το έργο του Mahadev χρησιμοποιεί έναν τύπο κρυπτογραφίας που ονομάζεται Learning With Errors (LWE) για να κατασκευάσει μια κατάλληλη συνάρτηση trapdoor. Μετά τη δημιουργία μιας μυστικής κατάστασης, ο υπολογιστής μπλέκει αυτή την κατάσταση με την κατάσταση που υποτίθεται ότι μετράει. Μόνο τότε ενημερώνεται ο υπολογιστής τι είδους μέτρηση πρέπει να εκτελέσει. Όταν ο υπολογιστής μετρήσει την προβλεπόμενη κατάσταση, η εμπλεκόμενη μυστική κατάσταση θα καταρρεύσει αντίστοιχα. Εφόσον ο υπολογιστής δεν γνώριζε τη σύνθεση της μυστικής κατάστασης, δεν θα γνωρίζει τη σύνθεση της νέας μυστικής κατάστασης, αλλά ο επαληθευτής θα γνωρίζει επειδή κατέχει τόσο το αρχικό κλειδί όσο και τη γνώση της μέτρησης που εκτελέστηκε. Εάν τα αποτελέσματα μοιάζουν με σωστή απόδειξη, ο επαληθευτής μπορεί να είναι σίγουρος ότι ο υπολογιστής έκανε όντως αυτό που του είπαν.

Ουσιαστικά, το πρωτόκολλο του Mahadev αναγκάζει τον υπολογιστή να συμπεριφέρεται με συγκεκριμένο τρόπο για να έχει το επιθυμητό αποτέλεσμα. Εάν ο υπολογιστής δεν χρησιμοποιούσε πραγματικά κβαντικά φαινόμενα, τότε ο μόνος τρόπος που θα μπορούσε να δώσει το σωστό αποτέλεσμα είναι να ελέγξει τη σύνθεση του μυστικού κράτους. Ωστόσο, κάτι τέτοιο θα κατέρρεε το μυστικό κράτος που αναπόφευκτα εμποδίζει τον υπολογιστή να δώσει το σωστό αποτέλεσμα καθώς οι αρχικές πληροφορίες θα καταστρέφονταν. Επομένως, εάν ο υπολογιστής δίνει το σωστό αποτέλεσμα, τότε πρέπει είναι ότι χρησιμοποιεί κβαντικά φαινόμενα για να το κάνει, διαφορετικά, θα μπορούσαμε να εντοπίσουμε ίχνη παρεμβολής.

Το πρωτόκολλο επαλήθευσης του Mahadev εξαρτάται από την υπόθεση ότι η κρυπτογραφία LWE, η οποία χρησιμοποιείται για τη δημιουργία της συνάρτησης trap-door που χρησιμοποιείται για την κατασκευή του μυστικού κράτους, δεν μπορεί να σπάσει από κβαντικούς υπολογιστές. Αυτό είναι ακόμα ένα ανοιχτό θεωρητικό ερώτημα, αλλά μέχρι στιγμής δεν έχουν βρεθεί στοιχεία που να δείχνουν ότι είναι σπάσιμο.

Το πρωτόκολλο του Mahadev απέχει ακόμα πολύ από το να εφαρμοστεί σε πραγματικούς κβαντικούς υπολογιστές, καθώς απαιτεί μεγάλη επεξεργαστική ισχύ. Ωστόσο, ο τομέας των κβαντικών υπολογιστών έχει σημειώσει πολλές προόδους τα τελευταία 10 χρόνια, με ορισμένες επιτυχημένες πρακτικές εφαρμογές. Δεδομένου του γρήγορου ρυθμού προόδου, η Μαχάντεφ θα μπορούσε να δει το έργο της να εφαρμόζεται σε πραγματικούς κβαντικούς υπολογιστές μέσα στα επόμενα 10 χρόνια.