Οι ερευνητές του NTT επιδεικνύουν έναν νέο τρόπο επαλήθευσης του Quantum Advantage

SUNNYVALE, Καλιφόρνια.–(ΣΥΡΜΑ ΕΠΙΧΕΙΡΗΣΕΩΝ)– Η NTT Research, Inc., ένα τμήμα της NTT (TYO:9432), ανακοίνωσε σήμερα ότι ένας ερευνητής από το Εργαστήριο Κρυπτογραφίας και Ασφάλειας Πληροφοριών (CIS) και ένας συνάδελφος από τα Εργαστήρια Κοινωνικής Πληροφορικής NTT (SIL) συνέταξαν μια πρωτοποριακή εργασία στο κβαντικό πλεονέκτημα. Η εργασία επιλέχθηκε να παρουσιαστεί στο ετήσιο IEEE Symposium on Foundations of Computer Science (FOCS), το οποίο λαμβάνει χώρα 31 Οκτ.–Νοεμ. 3 στο Ντένβερ. Οι συν-συγγραφείς της εργασίας, με τίτλο “Επαληθεύσιμο κβαντικό πλεονέκτημα χωρίς δομή”, είναι ο Δρ Takashi Yamakawa, διακεκριμένος ερευνητής στο NTT SIL και ο Δρ Mark Zhandry, ανώτερος ερευνητής στο NTT Research CIS Lab. Η εργασία διεξήχθη εν μέρει στο Πανεπιστήμιο του Πρίνστον, όπου ο Δρ Yamakawa ήταν επισκέπτης ερευνητής και ο Δρ Zhandry υπηρετεί επίσης ως επίκουρος καθηγητής της επιστήμης των υπολογιστών.

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

“Είναι η πρώτη φορά που βλέπουμε μια εκθετική κβαντική επιτάχυνση για ένα πρόβλημα αναζήτησης 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 Research), το επιχείρημα 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 MT. Για να μάθετε περισσότερα και να εγγραφείτε για αυτήν την εκδήλωση, επισκεφτείτε τον ιστότοπο του FOCS 2022.

Σχετικά με την Έρευνα NTT

Η NTT Research άνοιξε τα γραφεία της τον Ιούλιο του 2019 ως μια νέα start-up στη Silicon Valley για τη διεξαγωγή θεμελιωδών ερευνών και την προώθηση τεχνολογιών που προωθούν θετικές αλλαγές για την ανθρωπότητα. Επί του παρόντος, τρία εργαστήρια βρίσκονται στις ερευνητικές εγκαταστάσεις NTT στο Sunnyvale: Εργαστήριο Φυσικής και Πληροφορικής (PHI), Εργαστήριο Κρυπτογραφίας και Ασφάλειας Πληροφοριών (CIS) και Εργαστήριο Ιατρικής και Πληροφορικής Υγείας (MEI). Ο οργανισμός στοχεύει στην αναβάθμιση της πραγματικότητας σε τρεις τομείς: 1) κβαντικές πληροφορίες, νευροεπιστήμη και φωτονική. 2) κρυπτογραφική και ασφάλεια πληροφοριών. και 3) ιατρική και πληροφορική υγείας. Η NTT Research είναι μέρος της NTT, ενός παγκόσμιου προμηθευτή τεχνολογικών και επιχειρηματικών λύσεων με ετήσιο προϋπολογισμό Ε&Α 3,6 δισεκατομμυρίων USD.

Το NTT και το λογότυπο NTT είναι σήματα κατατεθέντα ή εμπορικά σήματα της NIPPON TELEGRAPH AND TELEPHONE CORPORATION ή/και των θυγατρικών της. Όλα τα άλλα αναφερόμενα ονόματα προϊόντων είναι εμπορικά σήματα των αντίστοιχων κατόχων τους. © 2022 NIPPON TELEGRAPH AND TELEPHONE CORPORATION

Leave a Comment