Μια κβαντική στρατηγική θα μπορούσε να επαληθεύσει τις λύσεις σε μη επιλύσιμα προβλήματα - θεωρητικά

Οι ονειροπόλοι των επιστημόνων υπολογιστών αποκάλυψαν τη δύναμη της κβαντικής μηχανικής.
Φανταστείτε ότι συνάντησε παντογνώστη όντα που ισχυρίζονται ότι έχουν την λύση σε ένα πολύπλοκο πρόβλημα που κανένας υπολογιστής δεν θα μπορούσε ποτέ να λύσει. Θα είχατε πιθανώς να χάσετε να ελέγξετε την απάντηση. Αλλά τώρα, οι επιστήμονες υπολογιστών αναφέρουν ότι η κβαντική μηχανική παρέχει έναν τρόπο για την ταχεία επαλήθευση των λύσεων σε μια απίστευτα ευρεία κατηγορία προβλημάτων, συμπεριλαμβανομένων ορισμένων που είναι αδύνατο να επιλυθούν κατά πρώτο λόγο.
Αν και το αποτέλεσμα δεν έχει προφανείς πρακτικές εφαρμογές, οι θεωρητικές του συνέπειες έχουν επηρεάσει τις ασαφείς ερωτήσεις στη φυσική και τα μαθηματικά, σύμφωνα με επιστήμονες σε άρθρο που δημοσιεύτηκε στις 13 Ιανουαρίου στο arXiv.org. "Έχει τόσες πολλές συνέπειες για όλους αυτούς τους τομείς. Είναι τεράστια διαπραγμάτευση, ανεξάρτητα από το πώς το βλέπετε ", λέει ο θεωρητικός επιστήμονας πληροφορικής Scott Aaronson του Πανεπιστημίου του Τέξας στο Austin, ο οποίος δεν συμμετείχε στη νέα μελέτη.
Στην επιστήμη των υπολογιστών, ορισμένα προβλήματα είναι δύσκολο να επιλυθούν αλλά έχουν λύσεις που είναι εύκολο να ελεγχθούν. Έτσι, οι ερευνητές ταξινομούν τις ερωτήσεις ανάλογα με το πόσο δύσκολο είναι για τους υπολογιστές να επαληθεύουν τις υποτιθέμενες απαντήσεις. Από μόνη της, ένας υπολογιστής μπορεί να προχωρήσει μόνο μέχρι στιγμής στην επαλήθευση των λύσεων. Αλλά οι επιστήμονες έχουν μερικά κόλπα επάνω στα μανίκια τους. Καταρτίζουν σενάρια όπου ένας "prover" - ένας υπολογιστής ή ένας άνθρωπος που ισχυρίζεται ότι έχει λύση σε ένα πρόβλημα - αντιμετωπίζεται με ερωτήσεις από το άτομο που επιχειρεί να ελέγξει τη λύση, τον "επαληθευτή".
Φανταστείτε, για παράδειγμα, ότι έχετε έναν φίλο που ισχυρίζεται ότι έχει συμπεράνει πώς να πει τη διαφορά μεταξύ Pepsi και Coke, αν και δεν μπορείτε να διακρίνετε μεταξύ των δύο. Για να επιβεβαιώσετε αυτόν τον ισχυρισμό, μπορείτε - ο επαληθευτής - να προετοιμάσετε ένα φλιτζάνι Pepsi ή Coke και να ζητήσετε από τον φίλο σας - τον prover - από ποιον είναι αυτός. Εάν ο φίλος σας δίνει σωστά τη σωστή απάντηση σε τέτοιες ερωτήσεις, θα είστε πεπεισμένοι ότι το πρόβλημα της ταυτοποίησης του κόλα είχε επιλυθεί.
Γνωστή ως αλληλεπιδραστική απόδειξη, αυτή η στρατηγική μπορεί να αποκαλύψει πρόσθετες πληροφορίες που θα επιτρέψουν στους επιστήμονες υπολογιστών να επαληθεύσουν λύσεις σε προβλήματα που είναι πολύ δύσκολα για έναν υπολογιστή να πείσει τους επιστήμονες ανεξάρτητα. Οι ακόμα ισχυρότερες αλληλεπιδραστικές αποδείξεις περιλαμβάνουν πολλαπλές δοκιμασίες. Το σενάριο αυτό είναι λίγο σαν μια αστυνομική ανάκριση δύο υπόπτων, απομονωμένων σε χωριστά δωμάτια, που δεν μπορούν να συντονίσουν τις απαντήσεις τους για να ξεγελάσουν έναν ερευνητή. Η τάξη των προβλημάτων που μπορούν να εξακριβωθούν με αυτόν τον τρόπο είναι "μεγάλη, αλλά όχι γελοία μεγάλη", λέει ο συνάδελφος της μελέτης Thomas Vidick, θεωρητικός επιστήμονας πληροφορικής στο Caltech. Για να ελέγξουν τις λύσεις σε μια ακόμη μεγαλύτερη ποικιλία προβλημάτων, οι επιστήμονες μπορούν να φανταστούν την προσθήκη μιας άλλης συστροφής: Οι εξεταστές μοιράζονται μια κβαντική σύνδεση που ονομάζεται εμπλοκή, η οποία προκαλεί δύο φαινομενικά ανεξάρτητα αντικείμενα να συμπεριφέρονται με συσχετισμένους τρόπους (SN: 4/25/18).
Μέχρι τώρα, δεν ήταν γνωστό πόσα προβλήματα ήταν επαληθεύσιμα με την κβαντική εμπλοκή. Το νέο αποτέλεσμα αποκαλύπτει ότι είναι "ένα απίστευτα τεράστιο αριθμό προβλημάτων", λέει ο Aaronson.
Αυτή η τεράστια ομάδα ονομάζεται αναδρομικά απαριθμητή, ή RE, προβλήματα. "Περιέχει όλα τα προβλήματα που μπορούν να επιλυθούν από τους υπολογιστές και έπειτα από κάποιους", λέει ο συνάδελφος Henry Yuen, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Τορόντο. "Αυτό είναι ένα τρελό πράγμα." Είναι το "και έπειτα κάποιο" που είναι πραγματικά μυαλό. Κανένας υπολογιστής δεν θα ήταν σε θέση να λύσει αυτά τα προβλήματα απόλυτα, αλλά αν δύο συνωστισμένα παντογνώσταστα όντα είχαν μια λύση, θα μπορούσαν να σας πείσουν ότι ήταν σωστό. Φυσικά, η θέσπιση της τεχνικής επαλήθευσης στον πραγματικό κόσμο καθίσταται απίθανη λόγω της έλλειψης παντογνώστων όντων για να προσφέρουν τις απαντήσεις.
Το αποτέλεσμα συνοψίζεται στην συνοπτική ισότητα, MIP * = RE, όπου το MIP * σημαίνει Multi-prover Interactive Proof με κβαντική εμπλοκή. Κάθε πρόβλημα στο RE είναι επίσης στο MIP * και αντίστροφα.
Αν και δεν έχει ακόμη αξιολογηθεί, η μελέτη λαμβάνεται πολύ σοβαρά, λέει ο επιστήμονας υπολογιστών Lance Fortnow του Ινστιτούτου Τεχνολογίας του Ιλινόις στο Σικάγο. "Θα ήθελα να στοιχηματίσετε ότι είναι ίσως σωστό .... Δεν υπάρχει λόγος να πιστεύουμε ότι είναι λάθος. "
Και το αποτέλεσμα είναι μια τριπλή απειλή: Επίλυσε τρία προβλήματα ταυτόχρονα. Εκτός από την αποκάλυψη ότι το MIP * ισούται με RE, απαντά ταυτόχρονα σε δύο ανοικτές ερωτήσεις, μία στη φυσική και μία στη μαθηματική. Το πρώτο είναι ένα παζλ κβαντικής φυσικής που ονομάζεται πρόβλημα Tsirelson, το οποίο θέτει το ερώτημα εάν οι τύποι των κβαντικών συσχετίσεων που θα μπορούσαν να παραχθούν χρησιμοποιώντας μια άπειρη ποσότητα εμπλοκής θα μπορούσαν να προσεγγιστούν με ένα πολύ μεγάλο αλλά πεπερασμένο ποσό εμπλοκής. Η απάντηση, η μελέτη αποκαλύπτει, είναι όχι: Μερικές φορές δεν μπορείτε να έρθετε κοντά στην αναπαραγωγή άπειρη εμπλοκή με πεπερασμένη εμπλοκή.
Στα μαθηματικά, η μελέτη ρυθμίζει την εικαστική εικασία της Connes, μια μακρόχρονη ιδέα που είναι μαθηματικά ισοδύναμη με το πρόβλημα του Tsirelson. Ασχολείται επίσης με το ερώτημα εάν μια πεπερασμένη προσέγγιση μπορεί αναγκαστικά να αναπαραγάγει κάτι αληθινά άπειρο. Και πάλι, η απάντηση είναι όχι.
"Είναι ένα απίστευτο επίτευγμα. είναι πραγματικά συναρπαστικό ", λέει ο μαθηματικός William Slofstra του Πανεπιστημίου του Waterloo στον Καναδά. "Είναι μια εκπλήρωση κάτι που θέλαμε εδώ και πολύ καιρό."