Προς έναν κβαντικό υπολογιστή που σπάει κωδικούς

Η υπόσχεση των κβαντικών υπολογιστών

Η τελευταία φορά που στείλατε ένα email πιθανότατα ήταν κρυπτογραφημένο με μια μέθοδο που βασίζεται στην ιδέα ότι ακόμα και ο ταχύτερος υπολογιστής δεν μπορεί να σπάσει έναν τεράστιο αριθμό σε παράγοντες. Οι κβαντικοί υπολογιστές, όμως, υπόσχονται να σπάσουν γρήγορα πολύπλοκα κρυπτογραφικά συστήματα που οι κλασικοί υπολογιστές δεν μπορούν να διαχειριστούν. Αυτή η υπόσχεση βασίζεται στον αλγόριθμο κβαντικής παραγοντοποίησης που πρότεινε το 1994 ο Peter Shor, ο οποίος είναι τώρα καθηγητής στο MIT. Παρά τις προόδους των τελευταίων 30 ετών, οι επιστήμονες δεν έχουν καταφέρει ακόμα να κατασκευάσουν έναν κβαντικό υπολογιστή αρκετά ισχυρό για να εκτελέσει τον αλγόριθμο του Shor.

Βελτιώσεις στον αλγόριθμο του Shor

Καθώς κάποιοι ερευνητές προσπαθούν να κατασκευάσουν μεγαλύτερους κβαντικούς υπολογιστές, άλλοι προσπαθούν να βελτιώσουν τον αλγόριθμο του Shor ώστε να μπορεί να εκτελεστεί σε μικρότερο κβαντικό κύκλωμα. Πριν από περίπου ένα χρόνο, ο επιστήμονας υπολογιστών Oded Regev από το Πανεπιστήμιο της Νέας Υόρκης πρότεινε μια σημαντική θεωρητική βελτίωση. Ο αλγόριθμός του μπορούσε να εκτελεστεί πιο γρήγορα, αλλά απαιτούσε περισσότερο μνήμη.

Η προσέγγιση του MIT

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

Η σημασία της κβαντικής παραγοντοποίησης

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

Η πρόκληση της κρυπτογραφίας

Για την ασφαλή μετάδοση μηνυμάτων στο διαδίκτυο, οι πάροχοι υπηρεσιών βασίζονται συνήθως στο RSA, ένα σύστημα κρυπτογράφησης που εφευρέθηκε από τους ερευνητές του MIT, Ron Rivest, Adi Shamir, και Leonard Adleman τη δεκαετία του 1970. Το σύστημα βασίζεται στην ιδέα ότι η παραγοντοποίηση ενός αριθμού 2,048-bit είναι πολύ δύσκολη για έναν υπολογιστή να την εκτελέσει σε λογικό χρονικό διάστημα.

Η πρόκληση της κβαντικής παραγοντοποίησης

Εκτιμάται ότι ένας κβαντικός υπολογιστής θα χρειαστεί περίπου 20 εκατομμύρια qubits για να εκτελέσει τον αλγόριθμο του Shor. Αυτή τη στιγμή, οι μεγαλύτεροι κβαντικοί υπολογιστές έχουν περίπου 1.100 qubits. Ένας κβαντικός υπολογιστής πραγματοποιεί υπολογισμούς χρησιμοποιώντας κβαντικά κυκλώματα, όπως ένας κλασικός υπολογιστής χρησιμοποιεί κλασικά κυκλώματα. Κάθε κβαντικό κύκλωμα αποτελείται από μια σειρά λειτουργιών γνωστών ως κβαντικές πύλες.

Η καινοτομία του MIT

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

Η μελλοντική κατεύθυνση

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