Το 1994, ένας μαθηματικός ανακάλυψε πώς να κάνει έναν κβαντικό υπολογιστή να κάνει κάτι που κανένας συνηθισμένος κλασικός υπολογιστής δεν θα μπορούσε. Η εργασία αποκάλυψε ότι, κατ 'αρχήν, μια μηχανή που βασίζεται στους κανόνες της κβαντικής μηχανικής θα μπορούσε αποτελεσματικά να σπάσει έναν μεγάλο αριθμό στους πρώτους παράγοντες της - ένα έργο τόσο δύσκολο για έναν κλασικό υπολογιστή που αποτελεί τη βάση για μεγάλο μέρος της σημερινής ασφάλειας στο Διαδίκτυο.
Ακολούθησε ένα κύμα αισιοδοξίας. Ίσως, σκέφτηκαν οι ερευνητές, να μπορέσουμε να εφεύρουμε κβαντικούς αλγόριθμους που μπορούν να λύσουν ένα τεράστιο φάσμα διαφορετικών προβλημάτων.
Όμως η πρόοδος σταμάτησε. «Ήταν λίγο δύσκολη η τροχιά», είπε Ράιαν Ο' Ντόνελ του Πανεπιστημίου Carnegie Mellon. «Οι άνθρωποι έλεγαν: "Αυτό είναι καταπληκτικό, είμαι σίγουρος ότι θα λάβουμε όλα τα είδη άλλων καταπληκτικών αλγορίθμων". Οχι." Οι επιστήμονες ανακάλυψαν δραματικές επιταχύνσεις μόνο για μια ενιαία, στενή κατηγορία προβλημάτων μέσα από ένα τυπικό σύνολο ονομάζεται NP, που σημαίνει ότι είχαν αποτελεσματικά επαληθεύσιμες λύσεις — όπως το factoring.
Αυτό συνέβαινε για σχεδόν τρεις δεκαετίες. Στη συνέχεια, τον Απρίλιο, οι ερευνητές εφευρέθηκε ένα θεμελιωδώς νέο είδος προβλήματος που ένας κβαντικός υπολογιστής θα πρέπει να είναι σε θέση να λύσει εκθετικά ταχύτερα από έναν κλασικό. Περιλαμβάνει τον υπολογισμό των εισροών σε μια περίπλοκη μαθηματική διαδικασία, που βασίζεται αποκλειστικά στις μπερδεμένες εξόδους της. Το αν το πρόβλημα παραμένει μόνο του ή είναι το πρώτο σε ένα νέο σύνορο πολλών άλλων δεν έχει ακόμη καθοριστεί.
«Υπάρχει μια αίσθηση ενθουσιασμού», είπε Βίνοντ Βαϊκουντανάθαν, επιστήμονας υπολογιστών στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης. «Πολλοί άνθρωποι σκέφτονται τι άλλο υπάρχει εκεί έξω».
Οι επιστήμονες υπολογιστών προσπαθούν να καταλάβουν τι κάνουν καλύτερα οι κβαντικοί υπολογιστές μελετώντας μαθηματικά μοντέλα που τους αντιπροσωπεύουν. Συχνά, φαντάζονται ένα μοντέλο ενός κβαντικού ή κλασικού υπολογιστή σε συνδυασμό με μια εξιδανικευμένη υπολογιστική μηχανή που ονομάζεται μαντείο. Τα Oracles είναι σαν απλές μαθηματικές συναρτήσεις ή προγράμματα υπολογιστή, που λαμβάνουν μια είσοδο και φτύνουν μια προκαθορισμένη έξοδο. Μπορεί να έχουν τυχαία συμπεριφορά, να βγάζουν «ναι» εάν η είσοδος εμπίπτει σε ένα συγκεκριμένο τυχαίο εύρος (ας πούμε, 12 έως 67) και «όχι» εάν δεν είναι. Ή μπορεί να είναι περιοδικές, έτσι ώστε μια είσοδος μεταξύ 1 και 10 επιστρέφει "ναι", 11 έως 20 αποδίδει "όχι", 21 έως 30 παράγει ξανά "ναι" και ούτω καθεξής.
Ας υποθέσουμε ότι έχετε έναν από αυτούς τους περιοδικούς χρησμούς και δεν γνωρίζετε την περίοδο. Το μόνο που μπορείτε να κάνετε είναι να το τροφοδοτήσετε με αριθμούς και να δείτε τι βγάζει. Με αυτούς τους περιορισμούς, πόσο γρήγορα θα μπορούσε ένας υπολογιστής να βρει την περίοδο; Το 1993, ο Daniel Simon, τότε στο Πανεπιστήμιο του Μόντρεαλ, διαπίστωσε ότι ένας κβαντικός αλγόριθμος μπορούσε να υπολογίσει την απάντηση σε ένα στενά συνδεδεμένο πρόβλημα εκθετικά ταχύτερα από οποιονδήποτε κλασικό αλγόριθμο.
Το αποτέλεσμα επέτρεψε στον Simon να προσδιορίσει έναν από τους πρώτους υπαινιγμούς για το πού θα μπορούσε να αναμένεται δραματική υπεροχή για τους κβαντικούς υπολογιστές. Αλλά όταν υπέβαλε την εργασία του σε ένα κορυφαίο συνέδριο, απορρίφθηκε. Ωστόσο, η εργασία ενδιέφερε ένα κατώτερο μέλος της επιτροπής προγράμματος του συνεδρίου — Πήτερ Σορ, ο οποίος εκείνη την εποχή βρισκόταν στα εργαστήρια Bell στο Νιου Τζέρσεϊ. Ο Shor συνέχισε διαπιστώνοντας ότι μπορούσε να προσαρμόσει τον αλγόριθμο του Simon για να υπολογίσει την περίοδο ενός χρησμού, αν είχε. Τότε συνειδητοποίησε ότι μπορούσε να προσαρμόσει τον αλγόριθμο για άλλη μια φορά, για να λύσει μια εξίσωση που συμπεριφέρεται παρόμοια με έναν περιοδικό χρησμό: την εξίσωση που περιγράφει την παραγοντοποίηση, η οποία είναι περιοδική.
Το αποτέλεσμα του Σορ ήταν ιστορικό. Ο κβαντικός αλγόριθμος που ανακάλυψε θα μπορούσε να μειώσει γρήγορα τους γιγάντιους αριθμούς στους πρώτους συντελεστές τους, κάτι που κανένας γνωστός κλασικός αλγόριθμος δεν μπορεί να κάνει. Στα χρόνια που ακολούθησαν, οι ερευνητές ανακάλυψαν άλλους αποτελεσματικούς κβαντικούς αλγόριθμους. Μερικοί από αυτούς, όπως ο αλγόριθμος του Shor, παρείχαν ακόμη και εκθετικό πλεονέκτημα, αλλά κανείς δεν μπορούσε να αποδείξει ένα δραματικό κβαντικό πλεονέκτημα σε οποιοδήποτε πρόβλημα NP που δεν ήταν περιοδικό.
Αυτή η έλλειψη προόδου οδήγησε δύο επιστήμονες υπολογιστών, Σκοτ Άαρσον του Πανεπιστημίου του Τέξας, στο Ώστιν, και Άντρης Αμπαΐνης του Πανεπιστημίου της Λετονίας, να κάνει μια παρατήρηση. Οι αποδείξεις του κβαντικού πλεονεκτήματος φαινόταν πάντα να εξαρτώνται από χρησμούς που είχαν κάποιο είδος μη τυχαίας δομής, όπως η περιοδικότητα. Το 2009, αυτοί εικάζεται ότι δεν θα μπορούσαν να υπάρξουν δραματικές επιταχύνσεις σε προβλήματα NP που ήταν τυχαία ή μη δομημένα. Κανείς δεν μπορούσε να βρει εξαίρεση.
Η εικασία τους έθεσε ένα όριο στις δυνάμεις των κβαντικών υπολογιστών. Αλλά είπε μόνο ότι δεν υπήρχαν δραματικές επιταχύνσεις για έναν συγκεκριμένο τύπο μη δομημένου προβλήματος NP - εκείνων με ναι ή όχι απαντήσεις. Εάν ένα πρόβλημα περιελάμβανε τον εντοπισμό πιο συγκεκριμένων, ποσοτικών απαντήσεων, το οποίο είναι γνωστό ως πρόβλημα αναζήτησης, η εικασία δεν ίσχυε.
Έχοντας αυτό κατά νου, ερευνητές Takashi Yamakawa των Εργαστηρίων Κοινωνικής Πληροφορικής ΝΤΤ και Mark Zhandry του NTT Research και του Princeton University αποφάσισαν να πειραματιστούν με ένα συγκεκριμένο πρόβλημα αναζήτησης, που εισήχθη το 2005 από Oded Regev.
Φανταστείτε ένα σύνολο μετεωρολογικών πτερυγίων που όλα δείχνουν προς την ίδια κατεύθυνση. Δώστε σε καθένα από αυτά μια μετρημένη ώθηση και, στη συνέχεια, αφήστε έναν θυελλώδη άνεμο να επηρεάσει την κατεύθυνσή τους. Ο Ρέγεβ ήθελε να καθορίσει, με βάση τις τελικές κατευθύνσεις τους, πού έδειξαν όλοι αρχικά. Προβλήματα όπως αυτό ονομάστηκαν «μάθηση με λάθη», επειδή η ώθηση και ο άνεμος λειτουργούν σαν πηγή τυχαίου λάθους στην αρχική κατεύθυνση. Υπάρχουν ενδείξεις ότι είναι δύσκολο να λυθεί τόσο για κλασικούς όσο και για κβαντικούς αλγόριθμους.
Ο Yamakawa και ο Zhandry τροποποίησαν τη ρύθμιση. Τροποποίησαν τη δύναμη εκείνων που ξεκίνησαν τα σπρώξιμο, καθιστώντας τα πιο προβλέψιμα. Προκάλεσαν επίσης τον προσδιορισμό του ανέμου από έναν τυχαίο χρησμό, έτσι ώστε σε ορισμένες περιπτώσεις να ήταν ακόμη πιο τυχαίος, αλλά σε άλλες εντελώς αδρανής.
Με αυτές τις τροποποιήσεις, οι ερευνητές ανακάλυψαν ότι ένας κβαντικός αλγόριθμος θα μπορούσε να βρει αποτελεσματικά την αρχική κατεύθυνση. Απέδειξαν επίσης ότι οποιοσδήποτε κλασικός αλγόριθμος πρέπει να είναι πιο αργός κατά έναν εκθετικό παράγοντα. Όπως και ο Shor, στη συνέχεια προσάρμοσαν τον αλγόριθμό τους για να λύσουν μια πραγματική εκδοχή του προβλήματος, η οποία αντικαθιστά το μαντείο με μια πραγματική μαθηματική εξίσωση.
Οι επιστήμονες υπολογιστών εξακολουθούν να εργάζονται για να κατανοήσουν και να αναπτύξουν το πρόβλημα. Ο Vaikuntanathan το συγκρίνει με ένα διαφορετικό που προκύπτει κατά τη συμπίεση δεδομένων: Όταν οι πληροφορίες συμπιέζονται προς τα κάτω, δύο bit μπορούν κατά λάθος να συμπιεστούν στην ίδια θέση, αντικαθιστώντας τα. Το πρόβλημα της πρόβλεψης αυτών των συγκρούσεων εκ των προτέρων, ώστε να μπορείτε να τις αποφύγετε, έχει κάποια ομοιότητα. «Αυτή είναι μια κατηγορία προβλημάτων που βασικά μοιάζουν με αυτό», είπε. «Ίσως αυτά τα προβλήματα μπορούν να λυθούν κβαντικά».
Υπήρχαν ελπίδες ότι ένα αδόμητο πρόβλημα όπως το νέο θα μπορούσε να επιλυθεί ακόμη και στις σημερινές νεοσύστατες εκδόσεις κβαντικών υπολογιστών, παρέχοντας έτσι ένα μέσο για τη δοκιμή τους. Η σκέψη ήταν ότι τα μη δομημένα προβλήματα μπορεί να χρειαστούν λιγότερους πόρους για να προγραμματιστούν ή να είναι λιγότερο ευαίσθητα στο θόρυβο, καθώς είναι ήδη τυχαία. Αλλά μέχρι στιγμής, το νέο πρόβλημα εξακολουθεί να φαίνεται πολύ προχωρημένο για να λυθεί από υπάρχοντες κβαντικούς υπολογιστές. «Είναι ένα περίεργο πρόβλημα. Δεν είχα σκεφτεί να το ορίσω», είπε ο Aaronson. "Αλλά εκ των υστέρων, έχει μερικά πολύ ωραία χαρακτηριστικά."
Το αποτέλεσμα παρέχει το πρώτο παράδειγμα δραματικού κβαντικού πλεονεκτήματος σε ένα αδόμητο πρόβλημα NP. Θα μπορούσαν να υπάρχουν πολλά άλλα προβλήματα που ο κβαντικός κόσμος αλλάζει από πρακτικά άλυτα σε επιλύσιμα; Τώρα υπάρχει περισσότερος λόγος να το σκεφτόμαστε.
«Έχει ανατραπεί κάπως οι πεποιθήσεις μας για τα είδη προβλημάτων στα οποία θα μπορούσαν να είναι καλοί οι κβαντικοί υπολογιστές», είπε ο O'Donnell.
