Znanstveniki NTT pravijo, da imajo nov način za preverjanje kvantne prednosti

Sunnyvale, Kalifornija – 26. oktober 2022 – NTT Research je objavil, da je znanstvenik iz Laboratorij za kriptografijo in informacijsko varnost (CIS). in kolega iz Laboratoriji za družbeno informatiko NTT (SIL) so napisali prelomni dokument o kvantni prednosti. Članek je bil izbran za predstavitev na letnem simpoziju IEEE o temeljih računalništva (FOCS), ki bo potekal od 31. oktobra do novembra. 3 v Denverju.

Soavtorji prispevka z naslovom »Preverljiva kvantna prednost brez strukture,« sta dr. Takashi Yamakawa, ugledni raziskovalec pri NTT SIL in dr. Mark Zhandry, višji znanstvenik v Raziskava NTT CIS laboratorij. Delo je bilo delno opravljeno na univerzi Princeton, kjer je bil dr. Yamakawa gostujoči raziskovalec, dr. Zhandry pa je tudi docent za računalništvo. 

Tema kvantne prednosti (ali kvantne pospešitve) se nanaša na vrste problemov, ki jih lahko kvantni računalniki rešijo hitreje od klasičnih ali nekvantnih računalnikov in koliko hitrejši so. Zadevni problemi so običajno opisani kot nedeterministični razred polinomskega časa (NP). Kolikšna prednost se lahko zelo razlikuje. Kvantni računalnik je morda sposoben rešiti določeno težavo v minuti ali sekundi, kar klasičnemu računalniku vzame en teden ali morda neznansko eksponentno količino časa. V tem prispevku avtorji obravnavajo izziv preverjanja te superiornosti in to učinkovito. Do danes so prikazi kvantne prednosti vključevali pomembno "strukturo" ali komunikacijo naprej in nazaj med dvema ali več stranmi. Preboj prispevka Yamakawe in Zhandryja je prikaz težkega problema NP, kjer je preverjanje možno brez strukture.

"To je prvič, da smo videli eksponentno kvantno pospešitev za težavo iskanja NP, ki zahteva samo naključni orakelj," je dejal profesor računalništva Univerze v Teksasu v Austinu dr. Scott Aaronson, ki je komentiral zgodnjo različico prispevka med delavnico 13. junija 2022 na Simonsovem inštitutu za teorijo računalništva. Ker sta zahtevala samo naključni orakelj, tj. teoretično črno skrinjico, ki generira naključne odgovore na vsako poizvedbo, sta Yamakawa in Zhandry svoj problem zgradila na nestrukturiranih računskih predpostavkah. Kot taka je njihova težava bolj povezana z enosmernimi funkcijami namesto s strukturiranimi, kot so tiste, ki jih najdemo v kriptografiji z javnimi ključi. Ta enosmerna poravnava olajša učinkovito preverjanje.

»Vznemirljivo je videti, da kriptografi, povezani z NTT, sodelujejo pri raziskavah, ki si ponovno zaslužijo oznako 'preboj', zlasti v dokumentu, ki obogati naše razumevanje kvantnega računalništva, kar je še eno področje, na katerega se pri NTT Research osredotočamo,« je dejal Kazuhiro Gomi. , predsednik in izvršni direktor NTT Research. "Čestitke in najboljše želje vsem udeležencem te prestižne konference IEEE." 

Problem iskanja NP, ki sta ga zasnovala Yamakawa in Zhandry, je bil problem dva v enem, ki vključuje iskanje 1) niza n-simbolov, ki je kodna beseda dane kode za popravljanje napak, in 2) niza n-simbolov, kjer vsak simbol je preslikan v nič pod naključnim orakljem. Vsaka težava posebej je enostavna. Toda najti en sam niz simbolov, ki je hkrati kodna beseda in se preslika na nič, je veliko težje, vsaj klasično. "Če ste kvantni, lahko to rešite v polinomskem času," je dejal dr. Zhandry, "če pa ste klasičen, vsaj če ste v tem modelu črne skrinjice, potrebujete eksponentni čas." Po drugi strani pa jo je glede na potencialno rešitev enostavno preveriti tako, da preverimo, ali ločeno rešuje vsakega od obeh problemov. Upoštevajte, da je to delo osnovno ali temeljno, kot se spodobi za članek za FOCS. Kot je bilo poudarjeno v govoru dr. Aaronsona na Simonsovem inštitutu (o katerem razpravljamo v tej raziskavi NTT članek bloga), argument Yamakawa-Zhandry spada v razred pospeškov, ki jih je mogoče zlahka matematično preveriti, vendar jih dejanski kvantni računalnik ne bo kmalu pokazal v praksi. Poleg prelomne sheme preverjanja pa dokument kaže tudi na nekaj novega v zvezi z obsegom kvantne pospešitve.

»Pred našim delom smo imeli primere kvantne prednosti za probleme NP, kot je faktoring ali, v nastavitvi črne skrinjice, iskanje obdobja. Izkazalo pa se je, da je bil kvantni algoritem, na katerem temeljijo vsi ti primeri, v bistvu iskanje obdobja – čeprav prikazovanje uporabe iskanja obdobja na teh primerih pogosto ni bilo trivialno,« je dejal dr. Zhandry. »Naš dokument kaže, da obstaja vsaj še en primer. To bi lahko optimistično razlagali, kot da obstaja upanje, da je kvantna prednost bolj razširjena, kot smo morda prej mislili.«

FOCS je vodilna konferenca na področju teoretičnega računalništva, ki jo sponzorira Tehnični odbor za matematične temelje računalništva (TCMF) IEEE Computer Society. Razpis za zbiranje prispevkov za FOCS 2022, 63. tovrstno letno srečanje, je kvantno računalništvo uvrstil med 17 splošnih področij zanimanja. Članek Yamakawa-Zhandry bo predvidoma predstavljen 31. oktobra 2022 ob 10 po srednjeevropskem času. Če želite izvedeti več o tem dogodku in se nanj prijaviti, obiščite FOCS 2022 spletne strani.