NTT-forskere sier at de har en ny måte å verifisere Quantum Advantage på

Sunnyvale, California – 26. oktober 2022 – NTT Research kunngjorde at en forsker fra sin Lab for kryptografi og informasjonssikkerhet (CIS). og en kollega fra NTT Sosialinformatikklaboratorier (SIL) har skrevet en banebrytende artikkel om kvantefordel. Artikkelen ble valgt ut til å presenteres på det årlige IEEE Symposium on Foundations of Computer Science (FOCS), som finner sted 31. oktober–nov. 3 i Denver.

Medforfatterne av papiret, med tittelen "Verifiserbar Quantum Advantage uten struktur,” er Dr. Takashi Yamakawa, fremstående forsker ved NTT SIL og Dr. Mark Zhandry, seniorforsker i NTT Research CIS Lab. Arbeidet ble delvis utført ved Princeton University, hvor Dr. Yamakawa var gjesteforsker og Dr. Zhandry også fungerer som assisterende professor i informatikk. 

Emnet kvantefordel (eller kvantehastighet) er relatert til den typen problemer som kvantedatamaskiner kan løse raskere enn klassiske, eller ikke-kvantedatamaskiner, og hvor mye raskere de er. De aktuelle problemene er vanligvis beskrevet som ikke-deterministisk polynomisk-tids-klasse (NP). Hvor mye fordel kan variere i stor grad. En kvantedatamaskin kan være i stand til å løse et bestemt problem på et minutt eller et sekund som tar en klassisk datamaskin i uken, eller muligens en ufattelig eksponentiell tid. I denne artikkelen tar forfatterne opp utfordringen med å verifisere denne overlegenheten, og gjøre det effektivt. Til dags dato har demonstrasjoner av kvantefordeler involvert betydelig "struktur" eller frem-og-tilbake-kommunikasjon mellom to eller flere parter. Gjennombruddet til Yamakawa og Zhandry-papiret er å demonstrere et NP-hardt problem der verifisering er mulig uten struktur.

"Dette er første gang vi har sett en eksponentiell kvantehastighet for et NP-søkeproblem, som bare krever et tilfeldig orakel," sa University of Texas at Austin professor i informatikk Dr. Scott Aaronson, som kommenterte en tidlig versjon av papiret under en workshop 13. juni 2022 ved Simons Institute for the Theory of Computing. Ved å bare kreve et tilfeldig orakel, dvs. en teoretisk svart boks som genererer tilfeldige svar på hver spørring, bygde Yamakawa og Zhandry problemet sitt på ustrukturerte beregningsforutsetninger. Som sådan er problemet deres mer på linje med enveisfunksjoner i stedet for strukturerte, slik som de som finnes i offentlig nøkkelkryptografi. Denne enveisjusteringen letter effektiv verifisering.

"Det er spennende å se NTT-tilknyttede kryptografer samarbeide om forskning som nok en gang fortjener etiketten "gjennombrudd", spesielt i en artikkel som beriker vår forståelse av kvantedatabehandling, et annet fokusområde for oss i NTT Research," sa Kazuhiro Gomi , NTT Research President og CEO. "Gratulerer og beste ønsker til alle deltakere på denne prestisjetunge IEEE-konferansen." 

NP-søkeproblemet som Yamakawa og Zhandry utviklet var et to-i-ett-problem som innebærer å finne 1) en n-symbolstreng som er et kodeord for en gitt feilrettingskode, og 2) en n-symbolstreng hvor hver symbolet er kartlagt til null under det tilfeldige oraklet. Hvert problem separat er enkelt. Men å finne en enkelt streng med symboler som både er et kodeord og kartlegger til null er mye vanskeligere, i det minste klassisk. "Hvis du er kvante, kan du løse dette i polynomisk tid," sa Dr. Zhandry, "men hvis du er klassisk, i det minste hvis du er i denne svarte boks-modellen, trenger du eksponentiell tid." På den annen side, gitt en potensiell løsning, er det enkelt å verifisere den ved å sjekke at den løser hvert av de to problemene separat. Merk at, som det sømmer seg et papir for FOCS, er dette arbeidet grunnleggende eller grunnleggende. Som påpekt i Dr. Aaronsons tale ved Simons Institute (diskutert i denne NTT Research bloggartikkel), faller Yamakawa-Zhandry-argumentet inn i en klasse med speedups som lett kan kontrolleres matematisk, men ikke demonstreres praktisk av en faktisk kvantedatamaskin når som helst snart. Utover det banebrytende verifiseringsskjemaet, peker papiret også på noe nytt angående omfanget av kvantehastighet.

"Før arbeidet vårt hadde vi eksempler på kvantefordeler for NP-problemer, som factoring eller, i black box-innstillingen, periodefunn. Men det viser seg at kvantealgoritmen som ligger til grunn for alle disse eksemplene i bunn og grunn var periodefunn – selv om det ofte var ikke-trivielt å vise hvordan man kan bruke periodefunn på disse eksemplene,” sa Dr. Zhandry. «Vårt papir viser at det er minst en annen sak. Du kan optimistisk tolke det som å si at det er håp om at kvantefordelen er mer utbredt enn vi kanskje tidligere trodde."

Sponset av IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), er FOCS en ledende konferanse innen teoretisk informatikk. Oppfordringen til papirer for FOCS 2022, den 63. slike årlige samlingen, oppførte kvantedatabehandling som et av 17 generelle interesseområder. Yamakawa-Zhandry-avisen skal etter planen presenteres 31. oktober 2022 kl. 10:15 MT. For å lære mer om og registrere deg for dette arrangementet, besøk FOCS 2022 nettside.