Τριάντα χρόνια αργότερα, μια ώθηση ταχύτητας για το Quantum Factoring | Περιοδικό Quanta

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

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

Τα τελευταία 30 χρόνια, οι επιστήμονες υπολογιστών έχουν εξορθολογίσει τον αλγόριθμο του Shor προετοιμάζοντας την ημέρα που η κβαντική τεχνολογία ωριμάσει αρκετά για να τη λειτουργήσει. Αλλά μια νέα παραλλαγή, από τον επιστήμονα πληροφορικής του Πανεπιστημίου της Νέας Υόρκης Oded Regev, είναι πιο γρήγορο με μια θεμελιωδώς νέα έννοια. Είναι το πρώτο που βελτιώνει τη σχέση μεταξύ του μεγέθους του αριθμού που συνυπολογίζεται και του αριθμού των κβαντικών πράξεων που απαιτούνται για την παραγοντοποίησή του.

«Είναι πραγματικά αξιοσημείωτο ότι κάποιος κατάφερε προφανώς να βελτιώσει την πολυπλοκότητα αυτού του αποτελέσματος πολλά, πολλά χρόνια αργότερα», είπε. Άσλεϊ Μοντανάρο, ερευνητής κβαντικών υπολογιστών στο Πανεπιστήμιο του Μπρίστολ. "Αυτό είναι πραγματικά συναρπαστικό."

Martin Ekerå, κρυπτογράφος στη Σουηδική Εθνική Αρχή Ασφάλειας Επικοινωνιών, συμφώνησε ότι η εργασία του Regev είναι ενδιαφέρουσα, αλλά προειδοποίησε ότι η υπέρβαση της τελευταίας τεχνολογίας στην πράξη θα απαιτήσει περαιτέρω βελτιστοποίηση. «Οι αρχικοί αλγόριθμοι του Shor είναι ήδη εκπληκτικά αποτελεσματικοί, επομένως δεν είναι ασήμαντο να κάνουμε σημαντικές βελτιώσεις», έγραψε σε ένα email.

Ο Regev ανέπτυξε τον νέο του αλγόριθμο αυξάνοντας τον αλγόριθμο του Shor με τεχνικές από έναν κλάδο της κρυπτογραφίας που ασχολείται με τη γεωμετρία υψηλών διαστάσεων.

«Θα πίστευα ότι οποιοσδήποτε αλγόριθμος λειτουργούσε με αυτό το βασικό περίγραμμα θα ήταν καταδικασμένος», είπε ο Shor, ένας εφαρμοσμένος μαθηματικός τώρα στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης. "Αλλά έκανα λάθος."

Εύρεση παραγόντων

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

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

Στη συνέχεια, το 1994, ο Shor διάβασε ένα χαρτί από τον επιστήμονα υπολογιστών Daniel Simon που έδειξε πώς να εκμεταλλευτεί την κβαντική υπέρθεση για να λύσει ένα επινοημένο πρόβλημα. Ο Shor ανακάλυψε πώς να επεκτείνει το αποτέλεσμα του Simon σε ένα πιο γενικό και πρακτικό πρόβλημα που ονομάζεται εύρεση περιόδου. Μια μαθηματική συνάρτηση λέγεται ότι είναι περιοδική όταν η έξοδος της κυκλώνει επανειλημμένα τις ίδιες τιμές καθώς αυξάνεται η είσοδος. η διάρκεια ενός μεμονωμένου κύκλου είναι γνωστή ως περίοδος της συνάρτησης.

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

Καθώς ο Shor έψαχνε για εφαρμογές για τον αλγόριθμο εύρεσης κβαντικής περιόδου, ανακάλυψε ξανά ένα παλαιότερα γνωστό αλλά σκοτεινό μαθηματικό θεώρημα: Για κάθε αριθμό, υπάρχει μια περιοδική συνάρτηση της οποίας οι περίοδοι σχετίζονται με τους πρώτους παράγοντες του αριθμού. Έτσι, εάν υπάρχει ένας αριθμός που θέλετε να υπολογίσετε, μπορείτε να υπολογίσετε την αντίστοιχη συνάρτηση και στη συνέχεια να λύσετε το πρόβλημα χρησιμοποιώντας την εύρεση περιόδου — «ακριβώς σε τι είναι τόσο καλοί οι κβαντικοί υπολογιστές», είπε ο Regev.

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

Ο αλγόριθμος του Shor ήταν ένα από τα λίγα βασικά πρώιμα αποτελέσματα που μετέτρεψαν τους κβαντικούς υπολογιστές από ένα σκοτεινό υποπεδίο της θεωρητικής επιστήμης των υπολογιστών σε αυτό που είναι σήμερα. Αλλά η εφαρμογή του αλγορίθμου στην πράξη είναι ένα τρομακτικό έργο, επειδή οι κβαντικοί υπολογιστές είναι ευάλωτοι σε σφάλματα: Εκτός από τα qubits που απαιτούνται για την εκτέλεση των υπολογισμών τους, χρειάζονται πολλά άλλα να κάνουν επιπλέον δουλειά για να μην αποτύχουν. ΕΝΑ πρόσφατο έγγραφο από τον Ekerå και τον ερευνητή της Google Κρεγκ Γκίντνεϊ εκτιμά ότι η χρήση του αλγόριθμου του Shor για τον υπολογισμό ενός αριθμού 2,048 bit προτύπου ασφαλείας (μήκους περίπου 600 ψηφίων) θα απαιτούσε έναν κβαντικό υπολογιστή με 20 εκατομμύρια qubits. Τα σημερινά μηχανήματα τελευταίας τεχνολογίας έχουν το πολύ μερικές εκατοντάδες.

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

Αν ναι, είπε ο Regev, «θα πρέπει να το γνωρίζουμε όσο το δυνατόν νωρίτερα, πριν να είναι πολύ αργά».

Χαμένος στα δέντρα

Ο Regev ξεκίνησε την ακαδημαϊκή του καριέρα στα τέλη της δεκαετίας του 1990, όταν οι κρυπτογράφοι έψαχναν για μια νέα μορφή κρυπτογραφίας δημόσιου κλειδιού που δεν ήταν ευάλωτη στον αλγόριθμο του Shor. Η πιο πολλά υποσχόμενη προσέγγιση, που ονομάζεται κρυπτογραφία βασισμένη σε πλέγμα, βασίζεται στη φαινομενική δυσκολία των υπολογιστικών προβλημάτων που περιλαμβάνουν πίνακες σημείων ή δικτυωμάτων υψηλών διαστάσεων. Ένα τέτοιο πρόβλημα είναι παρόμοιο με το έργο του εντοπισμού του δέντρου που βρίσκεται πιο κοντά σε ένα τυχαίο σημείο σε ένα δάσος.

«Αν είναι ένα δάσος εκατοντάδων διαστάσεων, τότε αυτό είναι πολύ πιο περίπλοκο από ό,τι αν είναι ένα δάσος δύο διαστάσεων», είπε Γκρεγκ Κούπερμπεργκ, μαθηματικός στο Πανεπιστήμιο της Καλιφόρνια, Ντέιβις.

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

"Το Oded είναι απολύτως εξαιρετικό με πλέγματα", είπε ο Kuperberg.

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

"Αν είστε κάποιος που κάνει πλέγματα όπως εγώ, σκέφτεστε, "Εντάξει, υπάρχει κάποιο πλέγμα που συμβαίνει εδώ", είπε ο Ρέγεβ. «Αλλά δεν μου ήταν ξεκάθαρο πώς να το χρησιμοποιήσω». Για χρόνια έπαιζε με άλλες ιδέες για νέους αλγόριθμους κβαντικής παραγοντοποίησης, αλλά ποτέ δεν έφτασε πουθενά. Στη συνέχεια, τον περασμένο χειμώνα επέστρεψε στο πρόβλημα και αποφάσισε να εντοπίσει αυτή τη δελεαστική σύνδεση μεταξύ του factoring και της κρυπτογραφίας με βάση το πλέγμα. Αυτή τη φορά βρήκε επιτυχία.

Επιπλέον Διαστάσεις

Ο Regev ήξερε ότι έπρεπε να ξεκινήσει γενικεύοντας την περιοδική συνάρτηση στην καρδιά του αλγορίθμου του Shor από μια διάσταση σε πολλές διαστάσεις. Στον αλγόριθμο του Shor, αυτή η συνάρτηση περιλαμβάνει τον επανειλημμένο πολλαπλασιασμό ενός τυχαίου αριθμού, μεταγλωττισμένο g, με τον εαυτό του. Αλλά η περίοδος αυτής της συνάρτησης — ο αριθμός των φορών που πρέπει να πολλαπλασιάσετε με g προτού αρχίσει να επαναλαμβάνεται η έξοδος της συνάρτησης — μπορεί να είναι πολύ μεγάλη, και αυτό σημαίνει ότι ένας κβαντικός υπολογιστής πρέπει να πολλαπλασιάσει μεγάλους αριθμούς σε ορισμένα στοιχεία της υπέρθεσης που χρησιμοποιεί για τον υπολογισμό της περιοδικής συνάρτησης. Αυτοί οι μεγάλοι πολλαπλασιασμοί είναι το πιο δαπανηρό υπολογιστικά μέρος του αλγορίθμου του Shor.

Η ανάλογη δισδιάστατη συνάρτηση χρησιμοποιεί αντ' αυτού ένα ζεύγος αριθμών, g₁ και g₂. Περιλαμβάνει πολλαπλασιασμό g₁ με τον εαυτό του πολλές φορές και στη συνέχεια πολλαπλασιάζεται επανειλημμένα με g₂. Η περίοδος αυτής της συνάρτησης είναι επίσης δισδιάστατη — ορίζεται από τον αριθμό των g₁ πολλαπλασιασμούς και g₂ πολλαπλασιασμοί που μαζί κάνουν την έξοδο της συνάρτησης να αρχίσει να επαναλαμβάνεται. Υπάρχουν πολλοί διαφορετικοί συνδυασμοί από g₁ και g₂ πολλαπλασιασμούς που θα κάνουν το κόλπο.

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

"Σκέφτεστε, "Τέλεια, μόλις έκανα τα πάντα σε υψηλές διαστάσεις και είναι ακριβώς ο ίδιος χρόνος εκτέλεσης με αυτόν του Shor", είπε ο Regev. «Κόλλησα με αυτό για λίγο». Τότε συνειδητοποίησε ότι μπορούσε να ξεπεράσει το πρόβλημα αλλάζοντας τη σειρά των πολλαπλασιασμών. Αντί να τοποθετεί επανειλημμένα αριθμούς σε ένα μόνο γινόμενο που θα γινόταν προοδευτικά μεγαλύτερος κατά τη διάρκεια του κβαντικού υπολογισμού, ξεκίνησε με ζεύγη μικρών αριθμών, πολλαπλασίασε τα προκύπτοντα γινόμενα μαζί και προχώρησε προς τα πάνω. Ο συνολικός αριθμός των πολλαπλασιασμών δεν άλλαξε πολύ, αλλά τώρα σχεδόν όλοι περιλαμβάνουν σχετικά μικρούς αριθμούς, κάνοντας τον υπολογισμό πιο γρήγορο.

«Αυτό κάνει όλη τη διαφορά στον κόσμο», είπε Βίνοντ Βαϊκουντανάθαν, κρυπτογράφος στο MIT.

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

Ένα κρύο πρωινό του Μαρτίου πριν από ένα ταξίδι σε ένα σεμινάριο στο Πανεπιστήμιο του Πρίνστον, ο Ρέγεβ βρέθηκε να περιμένει τον συνάδελφο με τον οποίο συναναστρεφόταν. «Έφτασα νωρίς και άργησε να πάρει το αυτοκίνητο», είπε. Ενώ καθόταν περιμένοντας, του ήρθε ξαφνικά το τελευταίο κομμάτι του παζλ. «Αυτή ήταν η στιγμή που τα πράγματα μπήκαν στη θέση τους, αλλά ψήνεται για λίγο».

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

Γράψιμο στην Άμμο

Η βελτίωση ήταν βαθιά. Ο αριθμός των στοιχειωδών λογικών βημάτων στο κβαντικό μέρος του αλγορίθμου του Regev είναι ανάλογος του n^1.5 κατά την παραγοντοποίηση ενός n-αριθμός bit, αντί n² όπως στον αλγόριθμο του Shor. Ο αλγόριθμος επαναλαμβάνει αυτό το κβαντικό μέρος μερικές δεκάδες φορές και συνδυάζει τα αποτελέσματα για να χαρτογραφήσει ένα πλέγμα υψηλών διαστάσεων, από το οποίο μπορεί να συναγάγει την περίοδο και να παράγει τον αριθμό. Έτσι, ο αλγόριθμος στο σύνολό του μπορεί να μην τρέχει πιο γρήγορα, αλλά η επιτάχυνση του κβαντικού μέρους μειώνοντας τον αριθμό των απαιτούμενων βημάτων θα μπορούσε να διευκολύνει την εφαρμογή του.

Φυσικά, ο χρόνος που χρειάζεται για να τρέξει ένας κβαντικός αλγόριθμος είναι μόνο ένα από τα πολλά ζητήματα. Εξίσου σημαντικός είναι ο αριθμός των qubits που απαιτούνται, ο οποίος είναι ανάλογος με τη μνήμη που απαιτείται για την αποθήκευση ενδιάμεσων τιμών κατά τη διάρκεια ενός συνηθισμένου κλασικού υπολογισμού. Ο αριθμός των qubits που απαιτεί ο αλγόριθμος του Shor για να συντελεστεί το an n-ο αριθμός bit είναι ανάλογος με n, ενώ ο αλγόριθμος του Regev στην αρχική του μορφή απαιτεί έναν αριθμό qubits ανάλογο με n^1.5 — μεγάλη διαφορά για αριθμούς 2,048 bit.

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

«Τα qubits μας προσπαθούν συνεχώς να διαλυθούν και προσπαθούμε να τα εμποδίσουμε να καταρρεύσουν», είπε ο Gidney. «Είναι σαν να προσπαθείς να γράψεις στην άμμο και ο άνεμος τη φυσάει μακριά». Αυτό σημαίνει ότι τα επιπλέον qubits που απαιτούνται από τον αλγόριθμο του Regev θα μπορούσαν να είναι ένα σημαντικό μειονέκτημα.

Αλλά το χαρτί του Regev δεν είναι το τέλος της ιστορίας. Πριν από δύο εβδομάδες, ο Vaikuntanathan και ο μεταπτυχιακός φοιτητής του Seyoon Ragavan βρήκαν έναν τρόπο να μειώσουν τη χρήση μνήμης του αλγόριθμου. Η παραλλαγή τους του αλγορίθμου του Regev, όπως ο αρχικός αλγόριθμος του Shor, απαιτεί έναν αριθμό qubits ανάλογο με n αντί n^1.5. Ο Ekerå έγραψε σε ένα email ότι η εργασία «μας φέρνει πολύ πιο κοντά σε μια εφαρμογή που θα ήταν πιο αποτελεσματική στην πράξη».

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

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

Σημείωση του συντάκτη: Ο Oded Regev λαμβάνει χρηματοδότηση από το Ίδρυμα Simons, το οποίο χρηματοδοτεί επίσης αυτό το συντακτικά ανεξάρτητο περιοδικό. Οι αποφάσεις χρηματοδότησης του Simons Foundation δεν επηρεάζουν την κάλυψή μας. Περισσότερες λεπτομέρειες είναι διαθέσιμο εδώ.

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