Oamenii de știință NTT spun că au o nouă modalitate de a verifica avantajul cuantic

Sunnyvale, California – 26 octombrie 2022 – NTT Research a anunțat că un om de știință de la Laboratorul de Criptografie și Securitate Informațională (CIS). si un coleg de la Laboratoarele de informatică socială NTT (SIL) au scris o lucrare inovatoare despre avantajul cuantic. Lucrarea a fost selectată pentru a fi prezentată la Simpozionul anual IEEE privind fundamentele științei computerelor (FOCS), care are loc în perioada 31 octombrie – noiembrie. 3 în Denver.

Co-autorii lucrării, intitulate „Avantaj cuantic verificabil fără structură”, sunt Dr. Takashi Yamakawa, cercetător distins la NTT SIL și Dr. Mark Zhandry, om de știință senior în Cercetare NTT Laboratorul CIS. Lucrarea a fost realizată parțial la Universitatea Princeton, unde dr. Yamakawa a fost cercetător vizitator și dr. Zhandry servește și ca profesor asistent de informatică. 

Subiectul avantajului cuantic (sau accelerarea cuantică) se referă la tipurile de probleme pe care computerele cuantice le pot rezolva mai repede decât computerele clasice sau non-cuantice și cu cât de mai rapide sunt. Problemele în cauză sunt descrise în mod obișnuit ca clasă nedeterministă în timp polinom (NP). Cât de mult avantaj ar putea varia într-o mare măsură. Un computer cuantic poate fi capabil să rezolve o anumită problemă într-un minut sau o secundă, ceea ce durează un computer clasic o săptămână sau, eventual, o perioadă de timp nespus de exponențială. În această lucrare, autorii abordează provocarea de a verifica această superioritate și de a face acest lucru în mod eficient. Până în prezent, demonstrațiile de avantaj cuantic au implicat o „structură” semnificativă sau o comunicare dus-întors între două sau mai multe părți. Descoperirea lucrării Yamakawa și Zhandry este de a demonstra o problemă dificilă NP în care verificarea este posibilă fără structură.

„Este prima dată când vedem o accelerare cuantică exponențială pentru o problemă de căutare NP, care necesită doar un oracol aleatoriu”, a spus profesorul de informatică de la Universitatea Texas din Austin, dr. Scott Aaronson, care a comentat o versiune timpurie. a lucrării în timpul unui workshop din 13 iunie 2022, la Institutul Simons pentru Teoria Calculului. Cerând doar un oracol aleatoriu, adică o cutie neagră teoretică care generează răspunsuri aleatorii la fiecare interogare, Yamakawa și Zhandry și-au construit problema pe ipoteze de calcul nestructurate. Ca atare, problema lor se aliniază mai strâns cu funcțiile unidirecționale în loc de cele structurate, cum ar fi cele găsite în criptografia cu cheie publică. Acea aliniere unidirecțională facilitează verificarea eficientă.

„Este interesant să vedem criptografi afiliați NTT colaborând la cercetări care merită încă o dată eticheta de „renovare”, în special într-o lucrare care ne îmbogățește înțelegerea calculului cuantic, un alt domeniu de interes pentru noi la NTT Research”, a spus Kazuhiro Gomi. , NTT Research Președinte și CEO. „Felicitări și cele mai bune urări tuturor participanților la această prestigioasă conferință IEEE.” 

Problema de căutare NP pe care Yamakawa și Zhandry au conceput-o a fost o problemă două-în-unu care presupune găsirea 1) a unui șir n-simbol care este un cuvânt cod al unui anumit cod de corectare a erorilor și 2) a unui șir n-simbol în care fiecare simbolul este mapat la zero sub oracolul aleatoriu. Fiecare problemă separat este ușoară. Dar să găsești un singur șir de simboluri care este atât un cuvânt de cod, cât și mapări la zero este mult mai greu, cel puțin în mod clasic. „Dacă ești cuantic, poți rezolva asta în timp polinomial”, a spus dr. Zhandry, „dar dacă ești clasic, cel puțin dacă ești în acest model cutie neagră, ai nevoie de timp exponențial.” Pe de altă parte, având în vedere o posibilă soluție, este simplu să o verifici verificând dacă rezolvă separat fiecare dintre cele două probleme. Rețineți că, așa cum se cuvine unei lucrări pentru FOCS, această lucrare este de bază sau fundamentală. După cum s-a subliniat în discursul Dr. Aaronson la Institutul Simons (discutat în această cercetare NTT articol de blog), argumentul Yamakawa-Zhandry se încadrează într-o clasă de accelerații care pot fi verificate cu ușurință matematic, dar nu pot fi demonstrate practic de un computer cuantic real în curând. Dincolo de schema sa de verificare inovatoare, lucrarea indică, de asemenea, ceva nou în ceea ce privește gradul de accelerare cuantică.

„Înainte de munca noastră, am avut exemple de avantaj cuantic pentru problemele NP, cum ar fi factoring sau, în setarea cutiei negre, determinarea perioadei. Dar se dovedește că algoritmul cuantic care stă la baza tuturor acestor exemple a fost în esență găsirea perioadei – deși arătarea modului de aplicare a descoperirii perioadei acestor exemple a fost adesea nebanală”, a spus dr. Zhandry. „Hârtia noastră arată că există cel puțin un al doilea caz. Ați putea interpreta asta în mod optimist ca spunând că există speranță că avantajul cuantic este mai răspândit decât poate ne-am gândit anterior.

Sponsorizat de IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), FOCS este o conferință de top în domeniul informaticii teoretice. Apelul pentru lucrări pentru FOCS 2022, a 63-a astfel de reuniune anuală, a enumerat calculul cuantic ca una dintre cele 17 domenii generale de interes. Lucrarea Yamakawa-Zhandry este programată să fie prezentată pe 31 octombrie 2022, la ora 10:15 MT. Pentru a afla mai multe despre acest eveniment și pentru a vă înregistra, vizitați FOCS 2022 site-ul web.