Το σύμπαν των προβλημάτων που μπορεί να ελέγξει ένας υπολογιστής έχει αυξηθεί. Το μυστικό συστατικό των ερευνητών; Κβαντική εμπλοκή.

Φανταστείτε ότι κάποιος ήρθε μαζί σας και σας είπε ότι είχαν ένα μαντείο και ότι αυτό το μαντείο θα μπορούσε να αποκαλύψει τα βαθιά μυστικά του σύμπαντος. Ενώ μπορεί να σας ενδιαφέρει, θα έχετε έναν σκληρό χρόνο εμπιστοσύνης. Θα θέλατε κάποιο τρόπο να επιβεβαιώσετε ότι αυτό που σας είπε το μαντείο ήταν αλήθεια.

Αυτή είναι η ουσία ενός από τα κεντρικά προβλήματα στην επιστήμη των υπολογιστών. Ορισμένα προβλήματα είναι πολύ δύσκολα για να λυθούν σε εύλογο χρονικό διάστημα. Αλλά οι λύσεις τους είναι εύκολο να ελεγχθούν. Δεδομένου ότι οι επιστήμονες ηλεκτρονικών υπολογιστών θέλουν να μάθουν: Πόσο περίπλοκο μπορεί να είναι ένα πρόβλημα ενώ παράλληλα έχει μια λύση που μπορεί να επαληθευτεί;

Αποδεικνύεται ότι η απάντηση είναι: Σχεδόν αδιανόητα περίπλοκη.

Σε ένα έγγραφο που κυκλοφόρησε τον Απρίλιο, δύο επιστήμονες υπολογιστών αύξησαν δραματικά τον αριθμό των προβλημάτων που εμπίπτουν στην κατηγορία που είναι δύσκολο να επιλυθεί αλλά είναι εύκολο να ελεγχθεί. Περιγράφουν μια μέθοδο που επιτρέπει την εξακρίβωση απαντήσεων σε προβλήματα σχεδόν ακατανόητης πολυπλοκότητας. “Φαίνεται παράλογο”, δήλωσε ο Thomas Vidick, ένας επιστήμονας υπολογιστών στο Ινστιτούτο Τεχνολογίας της Καλιφόρνιας ο οποίος δεν συμμετείχε στο νέο έργο.

Η έρευνα αφορά τους κβαντικούς υπολογιστές – τους υπολογιστές που εκτελούν υπολογισμούς σύμφωνα με τους μη συγκεκριμένους κανόνες της κβαντικής μηχανικής. Οι κβαντικοί υπολογιστές μόλις τώρα υπάρχουν, αλλά έχουν τη δυνατότητα να φέρουν επανάσταση στον υπολογισμό στο μέλλον.

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

Μέχρι το τέλος του Σύμπαντος

Όταν ένα πρόβλημα είναι δύσκολο να λυθεί αλλά είναι εύκολο να επαληθευτεί, η εξεύρεση λύσης απαιτεί πολύ χρόνο, αλλά η επαλήθευση ότι μια δεδομένη λύση είναι σωστή δεν το κάνει.

Για παράδειγμα, φανταστείτε ότι κάποιος σας δίνει ένα γράφημα – μια συλλογή από κουκκίδες (κορυφές) που συνδέονται με γραμμές (άκρες). Το άτομο σας ρωτάει αν είναι δυνατό να χρωματίσετε τις κορυφές του γραφήματος χρησιμοποιώντας μόνο τρία χρώματα, έτσι ώστε να μην έχουν συνδεδεμένες κορυφές το ίδιο χρώμα.

FIGURE: 3 color graph

Σε ένα γράφημα τριών χρωμάτων, κάθε κορυφή είναι ένα από τα τρία χρώματα και καμία συνδεδεμένη κορυφή δεν μοιράζεται το ίδιο χρώμα.

 

Αυτό το πρόβλημα “τριών χρωμάτων” είναι δύσκολο να λυθεί. Σε γενικές γραμμές, ο χρόνος που χρειάζεται για να βρεθεί ένα τριών χρωμάτων ενός γραφήματος (ή να καθοριστεί ότι κανένας δεν υπάρχει) αυξάνεται εκθετικά καθώς αυξάνεται το μέγεθος του γραφήματος. Εάν, ας πούμε, η εξεύρεση λύσης για ένα γράφημα με 20 κορυφές διαρκεί 320 νανοδευτερόλεπτα – μερικά δευτερόλεπτα συνολικά – ένα γράφημα με 60 κορυφές θα πάρει τη τάξη των 360 νανοδευτερόλεπτων ή περίπου 100 φορές την ηλικία του σύμπαντος.

Αλλά ας πούμε κάποιος ισχυρίζεται ότι έχει ένα τριών χρωμάτων ένα γράφημα. Δεν θα χρειαζόταν πολύς χρόνος για να ελέγξετε αν ο ισχυρισμός τους είναι αληθινός. Θα έπρεπε μόνο να περάσετε από τις κορυφές ένα προς ένα, εξετάζοντας τις συνδέσεις τους. Καθώς το γράφημα γίνεται μεγαλύτερο, ο χρόνος που χρειάζεται για να γίνει αυτό αυξάνεται αργά, σε αυτό που ονομάζεται πολυωνυμικός χρόνος. Ως αποτέλεσμα, ένας υπολογιστής δεν χρειάζεται πολύ χρόνο για να ελέγξει ένα τριών χρωμάτων ενός γραφήματος με 60 κορυφές από ότι για να ελέγξει ένα γράφημα με 20 κορυφές.

“Είναι εύκολο, δεδομένης της σωστής τριών χρωμάτων, να ελέγξουμε ότι λειτουργεί”, δήλωσε ο John Wright, φυσικός στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης, ο οποίος έγραψε το νέο έγγραφο μαζί με τον Anand Natarajan της Caltech.

Στη δεκαετία του 1970, οι επιστήμονες υπολογιστών καθόρισαν μια τάξη προβλημάτων που είναι εύκολο να εξακριβωθούν, ακόμα και αν ορισμένοι είναι δύσκολο να λυθούν. Κάλεσαν την τάξη “NP”, για μη καθοριστικό πολυωνυμικό χρόνο. Έκτοτε, η NP ήταν η πιο εντατικά μελετημένη κατηγορία προβλημάτων στην επιστήμη των υπολογιστών. Ειδικότερα, οι επιστήμονες υπολογιστών θα ήθελαν να μάθουν πώς αλλάζει αυτή η τάξη καθώς δίνετε στον επαληθευτή νέους τρόπους να ελέγξει την αλήθεια μιας λύσης.

Οι σωστές ερωτήσεις

Πριν από το έργο του Natarajan και του Wright, η ισχύς επαλήθευσης είχε αυξηθεί σε δύο μεγάλα άλματα.

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

Αλλά έχετε τη δυνατότητα να ζητήσετε την ερώτηση αυτού του προσώπου, τον οποίο θα ονομάσουμε τον prover. Ας υποθέσουμε ότι ο διαχειριστής σας λέει ότι τα δύο μπλοκ είναι διαφορετικά χρώματα. Ορίζετε ένα μπλοκ ως “Block A” και το άλλο ως “Block B.” Στη συνέχεια, τοποθετείτε τα μπλοκ πίσω από την πλάτη σας και αλλάζετε τυχαία σε ποιο χέρι κρατάτε το μπλοκ. Στη συνέχεια αποκαλύπτετε τα μπλοκ και ζητήστε από τον εντολέα να προσδιορίσει το μπλοκ Α.

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

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

Ο επαληθευτής μπορεί να στείλει τις ερωτήσεις του αποδέκτη,” είπε ο Wright, “και ίσως στο τέλος της συζήτησης ο επαληθευτής μπορεί να γίνει πιο πεπεισμένος.”

Το 1985, ένα τρίο των επιστημόνων των υπολογιστών απέδειξε ότι τέτοιες αλληλεπιδραστικές αποδείξεις μπορούν να χρησιμοποιηθούν για την επαλήθευση λύσεων σε προβλήματα που είναι πιο περίπλοκα από τα προβλήματα της NP. Το έργο τους δημιούργησε μια νέα κατηγορία προβλημάτων που ονομάζεται IP, για “διαλογικό πολυωνυμικό” χρόνο. Η ίδια μέθοδος που χρησιμοποιείται για την επαλήθευση του χρωματισμού δύο μπλοκ μπορεί να χρησιμοποιηθεί για την επαλήθευση λύσεων σε πολύ πιο περίπλοκες ερωτήσεις.

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

Είναι αδύνατο για τους δύο υπόπτους να σχηματίσουν ένα είδος κατανεμημένης και συνεπούς ιστορίας γιατί απλά δεν ξέρουν ποιες απαντήσεις δίνουν οι άλλοι”, δήλωσε ο Wright.

Το 1988, τέσσερις επιστήμονες των υπολογιστών αποδείκνυαν ότι αν ζητήσετε από δύο υπολογιστές να λύσουν ξεχωριστά το ίδιο πρόβλημα – και τις εξετάζετε ξεχωριστά για τις απαντήσεις τους – μπορείτε να επαληθεύσετε μια κλάση προβλημάτων που είναι ακόμη μεγαλύτερη από την IP: κατηγορία που ονομάζεται MIP, διαδραστικές αποδείξεις.

Με μια διαδραστική προσέγγιση πολλαπλών αποδεκτών, για παράδειγμα, είναι δυνατή η επαλήθευση των τριών χρωμάτων για μια ακολουθία γραφημάτων που αυξάνουν σε μέγεθος πολύ ταχύτερα από τα γραφήματα σε NP. Στο NP, τα μεγέθη των γραφημάτων αυξάνονται με γραμμικό ρυθμό – ο αριθμός των κορυφών μπορεί να αυξηθεί από 1 σε 2 σε 3 έως 4 και ούτω καθεξής – έτσι ώστε το μέγεθος ενός γραφήματος να μην είναι ποτέ υπερβολικά δυσανάλογο σε σχέση με το χρονικό διάστημα που απαιτείται για την επαλήθευση των τριών -χρωστικός. Αλλά στο MIP, ο αριθμός των κορυφών σε ένα γράφημα αυξάνεται εκθετικά – από 21 σε 22 έως 23 έως 24 και ούτω καθεξής.

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

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

Η επέκταση των προβλημάτων που ήταν δύσκολο να επιλυθούν αλλά ήταν εύκολο να επαληθευτούν από NP έως IP σε MIP περιελάμβανε κλασσικούς υπολογιστές. Οι κβαντικοί υπολογιστές λειτουργούν πολύ διαφορετικά. Για δεκαετίες δεν ήταν σαφές πώς αλλάζουν την εικόνα – καθιστούν δύσκολη ή ευκολότερη την εξακρίβωση λύσεων;

Το νέο έργο του Natarajan και του Wright παρέχει την απάντηση.

 

Κβαντικοί απατεώνες

Οι κβαντικοί υπολογιστές εκτελούν υπολογισμούς με το χειρισμό κβαντικών δυαδικών ψηφίων ή “qubits”. Αυτές έχουν την περίεργη ιδιότητα ότι μπορούν να μπλεγτούν μεταξύ τους. Όταν δύο qubits – ή ακόμα και μεγάλα συστήματα qubits – εμπλέκονται, σημαίνει ότι οι φυσικές ιδιότητές τους παίζουν ο ένας τον άλλον με κάποιο τρόπο.

Στη νέα τους δουλειά, ο Natarajan και ο Wright θεωρούν ένα σενάριο που περιλαμβάνει δύο ξεχωριστούς κβαντικούς υπολογιστές που μοιράζονται τα μπαλαντέρ.

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

Και πράγματι, όταν το σενάριο δύο κλεισμένων κβαντικών υπολογιστών παρουσιάστηκε για πρώτη φορά το 2003, οι επιστήμονες υπολογιστών υποθέτουν ότι η εμπλοκή θα μειώσει την ισχύ επαλήθευσης. “Η προφανής αντίδραση του καθενός, συμπεριλαμβανομένου και εμού, είναι ότι τώρα δίνετε μεγαλύτερη δύναμη στους εξεταστές”, δήλωσε ο Vidick. “Μπορούν να χρησιμοποιήσουν την εμπλοκή για να συσχετίσουν τις απαντήσεις τους”.

Παρά την αρχική απαισιοδοξία, ο Vidick πέρασε αρκετά χρόνια προσπαθώντας να αποδείξει το αντίθετο. Το 2012, ο ίδιος και ο Tsuyoshi Ito απέδειξαν ότι εξακολουθεί να είναι δυνατή η επαλήθευση όλων των προβλημάτων στο MIP με περιπλεγμένους κβαντικούς υπολογιστές.

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

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

Με την κατηγορία προβλημάτων που θεωρούν οι Natarajan και Wright – που ονομάζονται NEEXP για μη καθοριστικό διπλά εκθετικό χρόνο – τα μεγέθη των γραφημάτων αυξάνονται ακόμη ταχύτερα απ ‘ό, τι συμβαίνει στο MIP. Τα γραφήματα στο NEEXP αναπτύσσονται με ρυθμό “διπλά εκθετικά”. Αντί να αυξάνεται με ένα ποσοστό δυνάμεων των δύο – 21 , 22, 23, 24 και ούτω καθεξής – ο αριθμός των κορυφών στο γράφημα αυξάνεται με ένα ρυθμό δυνάμεων των δύο –  (22)1, (22)2, (22)3, (22)4 και ούτω καθεξής. Ως αποτέλεσμα, τα γραφήματα γίνονται γρήγορα τόσο μεγάλα ώστε ο επαληθευτής δεν μπορεί να αναγνωρίσει ούτε ένα μόνο ζεύγος συνδεδεμένων κορυφών.

 

GRAPHIC

 

“Για να επισημάνουμε μια κορυφή θα έπαιρνε 2n bits, κάτι που είναι εκθετικά περισσότερα κομμάτια από ό, τι ο επαληθευτής έχει στη μνήμη εργασίας του”, δήλωσε ο Natarajan.

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

Η ιδέα να ζητήσουν από τους υπολογιστές να αναρωτηθούν οι δικές τους λύσεις ακούγονται, στους επιστήμονες υπολογιστών, καθώς είναι σκόπιμο να ζητούν υποψίες σε ένα έγκλημα να αναρωτιούνται – σίγουρα μια ανόητη πρόταση. Εκτός από τους Natarajan και Wright αποδείξει ότι δεν είναι. Ο λόγος είναι η εμπλοκή.

“Οι κατακερματισμένες πολιτείες είναι ένας κοινός πόρος”, δήλωσε ο Wright. “Το σύνολο του πρωτοκόλλου μας είναι να υπολογίσουμε πώς να χρησιμοποιήσουμε αυτόν τον κοινόχρηστο πόρο για να δημιουργήσουμε συνδεδεμένα ερωτήματα”.

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

Παράλληλα, ο επαληθευτής δεν θέλει τους δύο κβαντικούς υπολογιστές να είναι τόσο αλληλένδετοι ώστε να αντιστοιχούν οι απαντήσεις τους σε αυτά τα ερωτήματα (που θα ισοδυναμούσαν με δύο υπόπτους σε ένα έγκλημα που συντονίζει το ψευδές τους ψευδώνυμο). Ένα άλλο περίεργο κβαντικό χαρακτηριστικό χειρίζεται αυτή την ανησυχία. Στην κβαντική μηχανική, η αρχή της αβεβαιότητας μας εμποδίζει να γνωρίζουμε ταυτόχρονα τη θέση και την ορμή των σωματιδίων – αν μετρήσετε μια ιδιότητα, καταστρέφετε πληροφορίες σχετικά με την άλλη. Η αρχή της αβεβαιότητας περιορίζει αυστηρά αυτό που μπορείτε να ξέρετε για οποιεσδήποτε δύο “συμπληρωματικές” ιδιότητες ενός κβαντικού συστήματος.

Ο Natarajan και ο Wright επωφελούνται από αυτό στο έργο τους. Για να υπολογίσουν το χρώμα μιας κορυφής, έχουν τους δύο κβαντικούς υπολογιστές να κάνουν συμπληρωματικές μετρήσεις. Κάθε υπολογιστής υπολογίζει το χρώμα της δικής του κορυφής και με αυτόν τον τρόπο καταστρέφει κάθε πληροφορία σχετικά με την κορυφή του άλλου. Με άλλα λόγια, η εμπλοκή επιτρέπει στους υπολογιστές να δημιουργούν συσχετισμένες ερωτήσεις, αλλά η αρχή της αβεβαιότητας τους εμποδίζει να συνεννοούνται όταν τους απαντούν.

“Πρέπει να αναγκάσετε τους εξεταστές να ξεχάσουν, και αυτό είναι το κύριο πράγμα [Natarajan και Wright] κάνουν στην εργασία τους”, είπε ο Vidick. “Αναγκάζουν τον διαχειριστή να διαγράψει πληροφορίες κάνοντας μια μέτρηση.”

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

Και τώρα που έχουν, δεν είναι σαφές πού βρίσκεται το όριο της εξουσίας ελέγχου.

“Θα μπορούσε να προχωρήσει πολύ περισσότερο”, δήλωσε ο Lance Fortnow, επιστήμονας υπολογιστών στο Τεχνολογικό Ινστιτούτο της Γεωργίας. “Αφήνουν ανοιχτό το ενδεχόμενο να μπορέσετε να κάνετε ένα ακόμα βήμα.”

Πατήστε εδώ για να συνεχίσετε

ΑΦΗΣΤΕ ΜΙΑ ΑΠΑΝΤΗΣΗ

Please enter your comment!
Please enter your name here