NTT-forskere siger, at de har en ny måde at verificere Quantum Advantage på

Sunnyvale, Californien – 26. oktober 2022 – NTT Research meddelte, at en videnskabsmand fra dens Lab for kryptografi og informationssikkerhed (CIS). og en kollega fra NTT Social Informatics Laboratories (SIL) har skrevet et banebrydende papir om kvantefordele. Papiret blev udvalgt til at blive præsenteret på det årlige IEEE Symposium on Foundations of Computer Science (FOCS), som finder sted 31. oktober-nov. 3 i Denver.

Medforfatterne til papiret, med titlen "Verificerbar Quantum Advantage uden struktur,” er Dr. Takashi Yamakawa, fremtrædende forsker ved NTT SIL og Dr. Mark Zhandry, seniorforsker i NTT Research CIS Lab. Arbejdet blev delvist udført på Princeton University, hvor Dr. Yamakawa var gæsteforsker og Dr. Zhandry også fungerer som assisterende professor i datalogi. 

Emnet kvantefordel (eller kvantehastighed) vedrører den slags problemer, som kvantecomputere kan løse hurtigere end klassiske eller ikke-kvantecomputere, og hvor meget hurtigere de er. De pågældende problemer beskrives almindeligvis som non-deterministic polynomial-time (NP) klasse. Hvor stor en fordel kan variere i høj grad. En kvantecomputer kan muligvis løse et bestemt problem på et minut eller et sekund, der tager en klassisk computer om ugen, eller muligvis en ufattelig eksponentiel tid. I dette papir behandler forfatterne udfordringen med at verificere denne overlegenhed og gøre det effektivt. Til dato har demonstrationer af kvantefordele involveret betydelig "struktur" eller frem-og-tilbage-kommunikation mellem to eller flere parter. Gennembruddet af Yamakawa og Zhandry papiret er at demonstrere et NP hårdt problem, hvor verifikation er mulig uden struktur.

"Dette er første gang, at vi har set en eksponentiel kvantehastighed for et NP-søgningsproblem, som kun kræver et tilfældigt orakel," sagde University of Texas i Austin professor i datalogi Dr. Scott Aaronson, som kommenterede en tidlig version af papiret under en workshop den 13. juni 2022 på Simons Institute for the Theory of Computing. Ved kun at kræve et tilfældigt orakel, dvs. en teoretisk sort boks, der genererer tilfældige svar på hver forespørgsel, byggede Yamakawa og Zhandry deres problem på ustrukturerede beregningsantagelser. Som sådan falder deres problem tættere sammen med envejsfunktioner i stedet for strukturerede, såsom dem der findes i offentlig nøglekryptografi. Denne envejsjustering letter effektiv verifikation.

"Det er spændende at se NTT-tilknyttede kryptografer samarbejde om forskning, der igen fortjener betegnelsen 'gennembrud', især i et papir, der beriger vores forståelse af kvanteberegning, et andet fokusområde for os hos NTT Research," sagde Kazuhiro Gomi , NTT Research President og CEO. "Tillykke og de bedste ønsker til alle deltagere i denne prestigefyldte IEEE-konference." 

NP-søgeproblemet, som Yamakawa og Zhandry udtænkte, var et to-i-en-problem, der indebærer at finde 1) en n-symbolstreng, der er et kodeord for en given fejlkorrektionskode, og 2) en n-symbolstreng, hvor hver symbolet er afbildet til nul under det tilfældige orakel. Hvert problem separat er nemt. Men at finde en enkelt streng af symboler, der både er et kodeord og kortlægger til nul, er meget sværere, i det mindste klassisk. "Hvis du er kvante, kan du løse dette i polynomisk tid," sagde Dr. Zhandry, "men hvis du er klassisk, i det mindste hvis du er i denne sorte boks-model, har du brug for eksponentiel tid." På den anden side, givet en potentiel løsning, er det nemt at verificere den ved at kontrollere, at den løser hvert af de to problemer separat. Bemærk, at som det sømmer sig et papir for FOCS, er dette arbejde grundlæggende eller grundlæggende. Som påpeget i Dr. Aaronsons tale på Simons Institute (diskuteret i denne NTT Research blog artiklen), falder Yamakawa-Zhandry-argumentet ind i en klasse af speedups, der let kan kontrolleres matematisk, men ikke demonstreres praktisk af en faktisk kvantecomputer på et tidspunkt snart. Ud over dets banebrydende verifikationsskema peger papiret dog også på noget nyt vedrørende omfanget af kvantehastighedsstigning.

"Før vores arbejde havde vi eksempler på kvantefordele for NP-problemer, såsom factoring eller, i black box-indstillingen, periodefunding. Men det viser sig, at kvantealgoritmen, der ligger til grund for alle disse eksempler, dybest set var periodefunding - selvom det ofte var ikke-trivielt at vise, hvordan man anvender periode-finding på disse eksempler," sagde Dr. Zhandry. "Vores papir viser, at der er mindst et andet tilfælde. Du kan optimistisk tolke det som at sige, at der er håb om, at kvantefordele er mere udbredt, end vi måske tidligere troede."

Sponsoreret af IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), er FOCS en førende konference inden for teoretisk datalogi. Indkaldelsen til papirer til FOCS 2022, den 63. sådanne årlige samling, anførte kvantedatabehandling som et af 17 generelle interesseområder. Yamakawa-Zhandry-papiret er planlagt til at blive præsenteret den 31. oktober 2022 kl. 10:15 MT. For at lære mere om og tilmelde dig denne begivenhed, besøg FOCS 2022 internet side.