Gli scienziati di NTT affermano di avere un nuovo modo per verificare il vantaggio quantistico

Sunnyvale, California – 26 ottobre 2022 – NTT Research ha annunciato che uno scienziato del suo Laboratorio di crittografia e sicurezza delle informazioni (CIS). e un collega del Laboratori di Informatica Sociale NTT (SIL) hanno scritto un documento innovativo sul vantaggio quantistico. Il documento è stato selezionato per essere presentato all'annuale IEEE Symposium on Foundations of Computer Science (FOCS), che si terrà dal 31 ottobre al 3 novembre. XNUMX a Denver.

I coautori del paper, intitolato “Vantaggio quantistico verificabile senza struttura”, sono il Dr. Takashi Yamakawa, illustre ricercatore presso NTT SIL e il Dr. Mark Zhandry, scienziato senior nel Ricerca NTT Laboratorio della CSI. Il lavoro è stato svolto in parte all'Università di Princeton, dove il dottor Yamakawa è stato ricercatore in visita e il dottor Zhandry è anche assistente professore di informatica. 

L'argomento del vantaggio quantistico (o accelerazione quantistica) riguarda i tipi di problemi che i computer quantistici possono risolvere più velocemente dei computer classici, o non quantistici, e quanto sono più veloci. I problemi in questione sono comunemente descritti come classi non deterministiche tempo-polinomiale (NP). Quanto vantaggio potrebbe variare in larga misura. Un computer quantistico può essere in grado di risolvere un particolare problema in un minuto o un secondo che impiega un computer classico una settimana, o forse una quantità di tempo insondabilmente esponenziale. In questo articolo, gli autori affrontano la sfida di verificare questa superiorità e di farlo in modo efficiente. Ad oggi, le dimostrazioni del vantaggio quantistico hanno coinvolto una "struttura" significativa o una comunicazione avanti e indietro tra due o più parti. La svolta del documento Yamakawa e Zhandry consiste nel dimostrare un problema difficile NP in cui la verifica è possibile senza struttura.

"Questa è la prima volta che vediamo un aumento della velocità quantistica esponenziale per un problema di ricerca NP, che richiede solo un oracolo casuale", ha affermato Scott Aaronson, professore di informatica dell'Università del Texas ad Austin, che ha commentato una prima versione dell'articolo durante un workshop il 13 giugno 2022, presso il Simons Institute for the Theory of Computing. Richiedendo solo un oracolo casuale, cioè una scatola nera teorica che genera risposte casuali a ciascuna query, Yamakawa e Zhandry hanno costruito il loro problema su ipotesi computazionali non strutturate. In quanto tale, il loro problema si allinea più strettamente con le funzioni unidirezionali anziché quelle strutturate, come quelle che si trovano nella crittografia a chiave pubblica. Questo allineamento unidirezionale facilita una verifica efficiente.

"È emozionante vedere crittografi affiliati a NTT collaborare a ricerche che ancora una volta meritano l'etichetta di 'svolta', specialmente in un documento che arricchisce la nostra comprensione dell'informatica quantistica, un'altra area di interesse per noi di NTT Research", ha affermato Kazuhiro Gomi , Presidente e CEO di NTT Research. "Congratulazioni e auguri a tutti i partecipanti a questa prestigiosa conferenza IEEE." 

Il problema di ricerca NP ideato da Yamakawa e Zhandry era un problema due in uno che implica la ricerca di 1) una stringa di n simboli che è una parola in codice di un dato codice di correzione degli errori e 2) una stringa di n simboli in cui ciascuno il simbolo è mappato a zero sotto l'oracolo casuale. Ogni problema separatamente è facile. Ma trovare una singola stringa di simboli che sia sia una parola in codice che mappata su zero è molto più difficile, almeno classicamente. "Se sei quantistico, puoi risolverlo in tempo polinomiale", ha detto il dottor Zhandry, "ma se sei classico, almeno se sei in questo modello di scatola nera, hai bisogno di tempo esponenziale". D'altra parte, data una possibile soluzione, è semplice verificarla verificando che risolva separatamente ciascuno dei due problemi. Nota che, come si addice a un documento per FOCS, questo lavoro è di base o fondamentale. Come sottolineato nel discorso del Dr. Aaronson al Simons Institute (discusso in questo NTT Research articolo ), l'argomento Yamakawa-Zhandry rientra in una classe di accelerazioni che possono essere prontamente verificate matematicamente, ma non dimostrate praticamente da un vero computer quantistico in tempi brevi. Al di là del suo innovativo schema di verifica, tuttavia, il documento punta anche a qualcosa di nuovo riguardo all'entità dell'accelerazione quantistica.

“Prima del nostro lavoro, avevamo esempi di vantaggi quantistici per problemi NP, come la fattorizzazione o, nell'impostazione della scatola nera, la ricerca del periodo. Ma si scopre che l'algoritmo quantistico alla base di tutti questi esempi era fondamentalmente la ricerca del periodo, anche se mostrare come applicare la ricerca del periodo a questi esempi spesso non era banale", ha affermato il dottor Zhandry. «Il nostro giornale mostra che c'è almeno un secondo caso. Potresti interpretarlo ottimisticamente come se dicesse che c'è speranza che il vantaggio quantistico sia più diffuso di quanto forse pensavamo in precedenza".

Sponsorizzato dall'IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), FOCS è una conferenza leader nel campo dell'informatica teorica. La call for paper per FOCS 2022, il 63° incontro annuale di questo tipo, ha elencato l'informatica quantistica come una delle 17 aree di interesse generale. La presentazione del documento Yamakawa-Zhandry è prevista per il 31 ottobre 2022 alle 10:15 MT. Per saperne di più e registrarsi a questo evento, visitare il FOCUS 2022 di LPI.