Οι επιστήμονες του NTT λένε ότι έχουν νέο τρόπο για να επαληθεύσουν το κβαντικό πλεονέκτημα

Sunnyvale, Καλιφόρνια – 26 Οκτωβρίου 2022 – Η NTT Research ανακοίνωσε ότι ένας επιστήμονας από την Εργαστήριο Κρυπτογραφίας και Ασφάλειας Πληροφοριών (CIS). και ένας συνάδελφος από το Εργαστήρια Κοινωνικής Πληροφορικής ΝΤΤ (SIL) έχουν γράψει ένα πρωτοποριακό χαρτί για το κβαντικό πλεονέκτημα. Η εργασία επιλέχθηκε να παρουσιαστεί στο ετήσιο IEEE Symposium on Foundations of Computer Science (FOCS), το οποίο λαμβάνει χώρα από τις 31 Οκτωβρίου έως τις Νοε. 3 στο Ντένβερ.

Οι συν-συγγραφείς της εργασίας με τίτλο «Επαληθεύσιμο κβαντικό πλεονέκτημα χωρίς δομή», είναι ο Δρ Takashi Yamakawa, διακεκριμένος ερευνητής στο NTT SIL και ο Δρ Mark Zhandry, ανώτερος επιστήμονας στο Έρευνα NTT CIS Lab. Η εργασία έγινε εν μέρει στο Πανεπιστήμιο του Πρίνστον, όπου ο Δρ Yamakawa ήταν επισκέπτης ερευνητής και ο Δρ Zhandry υπηρετεί επίσης ως βοηθός καθηγητής επιστήμης υπολογιστών. 

Το θέμα του κβαντικού πλεονεκτήματος (ή της κβαντικής επιτάχυνσης) σχετίζεται με τα είδη προβλημάτων που μπορούν να λύσουν οι κβαντικοί υπολογιστές γρηγορότερα από τους κλασσικούς ή μη κβαντικούς υπολογιστές και το πόσο πιο γρήγοροι είναι. Τα εν λόγω προβλήματα περιγράφονται συνήθως ως κλάση μη ντετερμινιστικού πολυωνυμικού χρόνου (NP). Το πόσο πλεονέκτημα θα μπορούσε να διαφέρει σε τεράστιο βαθμό. Ένας κβαντικός υπολογιστής μπορεί να είναι σε θέση να λύσει ένα συγκεκριμένο πρόβλημα σε ένα λεπτό ή ένα δευτερόλεπτο που χρειάζεται ένας κλασικός υπολογιστής την εβδομάδα, ή πιθανώς σε έναν απίστευτα εκθετικό χρόνο. Σε αυτό το άρθρο, οι συγγραφείς αντιμετωπίζουν την πρόκληση της επαλήθευσης αυτής της ανωτερότητας και να το κάνουν αποτελεσματικά. Μέχρι σήμερα, οι επιδείξεις κβαντικού πλεονεκτήματος περιλαμβάνουν σημαντική «δομή» ή επικοινωνία μεταξύ δύο ή περισσότερων μερών. Η ανακάλυψη του χαρτιού Yamakawa και Zhandry είναι να επιδείξει ένα σκληρό πρόβλημα NP όπου η επαλήθευση είναι δυνατή χωρίς δομή.

«Είναι η πρώτη φορά που έχουμε δει μια εκθετική κβαντική επιτάχυνση για ένα πρόβλημα αναζήτησης NP, το οποίο απαιτεί μόνο έναν τυχαίο χρησμό», δήλωσε ο καθηγητής Επιστήμης Υπολογιστών του Πανεπιστημίου του Τέξας στο Ώστιν, Δρ Σκοτ ​​Άαρονσον, ο οποίος σχολίασε μια πρώιμη έκδοση. της εργασίας κατά τη διάρκεια εργαστηρίου στις 13 Ιουνίου 2022, στο Simons Institute for the Theory of Computing. Απαιτώντας μόνο έναν τυχαίο χρησμό, δηλαδή ένα θεωρητικό μαύρο κουτί που δημιουργεί τυχαίες απαντήσεις σε κάθε ερώτημα, οι Yamakawa και Zhandry έχτισαν το πρόβλημά τους σε μη δομημένες υπολογιστικές υποθέσεις. Ως εκ τούτου, το πρόβλημά τους ευθυγραμμίζεται πιο στενά με μονόδρομες συναρτήσεις αντί για δομημένες, όπως αυτές που βρίσκονται στην κρυπτογραφία δημόσιου κλειδιού. Αυτή η μονόδρομη ευθυγράμμιση διευκολύνει την αποτελεσματική επαλήθευση.

«Είναι συναρπαστικό να βλέπεις κρυπτογράφους που συνδέονται με το NTT να συνεργάζονται σε έρευνα που αξίζει για άλλη μια φορά την ετικέτα της «ανακάλυψης», ειδικά σε μια εργασία που εμπλουτίζει την κατανόησή μας για τους κβαντικούς υπολογιστές, έναν άλλο τομέα εστίασης για εμάς στην NTT Research», δήλωσε ο Kazuhiro Gomi. , Πρόεδρος και Διευθύνων Σύμβουλος της NTT Research. «Συγχαρητήρια και ευχές σε όλους τους συμμετέχοντες σε αυτό το διάσημο συνέδριο IEEE.» 

Το πρόβλημα αναζήτησης NP που επινόησαν οι Yamakawa και Zhandry ήταν ένα πρόβλημα δύο σε ένα που συνεπάγεται την εύρεση 1) μιας συμβολοσειράς n-συμβόλων που είναι μια κωδική λέξη ενός δεδομένου κώδικα διόρθωσης σφάλματος και 2) μια συμβολοσειρά n-συμβόλων όπου κάθε Το σύμβολο αντιστοιχίζεται στο μηδέν κάτω από τον τυχαίο χρησμό. Κάθε πρόβλημα ξεχωριστά είναι εύκολο. Αλλά το να βρείτε μια ενιαία συμβολοσειρά συμβόλων που είναι ταυτόχρονα κωδική λέξη και αντιστοιχούν στο μηδέν είναι πολύ πιο δύσκολο, τουλάχιστον κλασικά. «Αν είστε κβαντικοί, μπορείτε να το λύσετε σε πολυωνυμικό χρόνο», είπε ο Δρ. Zhandry, «αλλά αν είστε κλασικοί, τουλάχιστον αν είστε σε αυτό το μοντέλο μαύρου κουτιού, χρειάζεστε εκθετικό χρόνο». Από την άλλη πλευρά, δεδομένου μιας πιθανής λύσης, είναι απλό να την επαληθεύσετε ελέγχοντας ότι επιλύει ξεχωριστά καθένα από τα δύο προβλήματα. Σημειώστε ότι, όπως αρμόζει σε μια εργασία για το FOCS, αυτή η εργασία είναι βασική ή θεμελιώδης. Όπως επισημάνθηκε στην ομιλία του Δρ. Aaronson στο Ινστιτούτο Simons (που συζητήθηκε σε αυτήν την έρευνα NTT blog άρθρο), το όρισμα Yamakawa-Zhandry εμπίπτει σε μια κατηγορία επιταχύνσεων που μπορούν εύκολα να ελεγχθούν μαθηματικά, αλλά δεν αποδεικνύονται πρακτικά από έναν πραγματικό κβαντικό υπολογιστή σύντομα. Πέρα από το επαναστατικό σχήμα επαλήθευσης, ωστόσο, το έγγραφο επισημαίνει επίσης κάτι νέο σχετικά με την έκταση της κβαντικής επιτάχυνσης.

«Πριν από την εργασία μας, είχαμε παραδείγματα κβαντικού πλεονεκτήματος για προβλήματα NP, όπως παραγοντοποίηση ή, στη ρύθμιση του μαύρου κουτιού, εύρεση περιόδου. Αλλά αποδεικνύεται ότι ο κβαντικός αλγόριθμος που διέπει όλα αυτά τα παραδείγματα ήταν βασικά η εύρεση περιόδου – αν και το να δείξεις πώς να εφαρμόσεις την εύρεση περιόδου σε αυτά τα παραδείγματα ήταν συχνά μη τετριμμένο», είπε ο Δρ Zhandry. «Το χαρτί μας δείχνει ότι υπάρχει τουλάχιστον μια δεύτερη περίπτωση. Θα μπορούσατε να το ερμηνεύσετε αισιόδοξα ως λέγοντας ότι υπάρχει ελπίδα ότι το κβαντικό πλεονέκτημα είναι πιο διαδεδομένο από ό,τι πιστεύαμε προηγουμένως».

Με τη χορηγία της IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), το FOCS είναι ένα κορυφαίο συνέδριο στον τομέα της θεωρητικής επιστήμης των υπολογιστών. Η πρόσκληση υποβολής εργασιών για το FOCS 2022, την 63η τέτοια ετήσια συγκέντρωση, κατέταξε τον κβαντικό υπολογισμό ως έναν από τους 17 γενικούς τομείς ενδιαφέροντος. Η εργασία Yamakawa-Zhandry έχει προγραμματιστεί να παρουσιαστεί στις 31 Οκτωβρίου 2022, στις 10:15 π.μ. Για να μάθετε περισσότερα και να εγγραφείτε σε αυτήν την εκδήλωση, επισκεφθείτε τη διεύθυνση FOCS 2022 ιστοσελίδα.