Sunnyvale, California – 26. oktoober 2022 – NTT Research teatas, et üks teadlane Krüptograafia ja infoturbe (CIS) labor ja kolleegi NTT sotsiaalinformaatika laborid (SIL) on kvanteelise kohta kirjutanud murrangulise töö. Artikkel valiti esitamiseks iga-aastasel IEEE Symposium on Foundations of Computer Science (FOCS), mis toimub 31. oktoober–november. 3 Denveris.
Artikli pealkirjaga "Kontrollitav kvanteelis ilma struktuurita”, on dr Takashi Yamakawa, NTT SILi tunnustatud teadur ja dr Mark Zhandry, vanemteadur dr. NTT teadustöö SRÜ labor. Töö tehti osaliselt Princetoni ülikoolis, kus dr Yamakawa oli külalisuurija ja dr Zhandry töötab ka arvutiteaduse abiprofessorina.
Kvantieelise (või kvantkiirenduse) teema on seotud probleemidega, mida kvantarvutid suudavad lahendada kiiremini kui klassikalised või mittekvantarvutid ja kui palju kiiremad need on. Kõnealuseid probleeme kirjeldatakse tavaliselt mittedeterministliku polünoomiaja (NP) klassina. Kui palju eeliseid võib suurel määral erineda. Kvantarvuti võib olla suuteline lahendama konkreetse probleemi minuti või sekundiga, mis võtab klassikalisel arvutil nädalas või võib-olla mõõtmatult eksponentsiaalselt palju aega. Selles artiklis käsitlevad autorid selle paremuse kontrollimise väljakutset ja seda tõhusalt. Praeguseks on kvanteelise demonstreerimine hõlmanud märkimisväärset "struktuuri" või edasi-tagasi suhtlust kahe või enama osapoole vahel. Yamakawa ja Zhandry paberi läbimurre seisneb NP raske probleemi demonstreerimises, kus kontrollimine on võimalik ilma struktuurita.
"See on esimene kord, kui näeme NP-otsingu probleemi eksponentsiaalset kvantkiirendust, mis nõuab ainult juhuslikku oraaklit," ütles Texase ülikooli Austini arvutiteaduse professor dr Scott Aaronson, kes kommenteeris varasemat versiooni. artiklist 13. juunil 2022 Simonsi andmetöötlusteooria instituudis toimunud seminaril. Nõudes ainult juhuslikku oraaklit, st teoreetilist musta kasti, mis genereerib igale päringule juhuslikke vastuseid, ehitasid Yamakawa ja Zhandry oma probleemi struktureerimata arvutuslikele eeldustele. Sellisena on nende probleem paremini kooskõlas ühesuunaliste funktsioonidega, mitte struktureeritud funktsioonidega, nagu need, mida leidub avaliku võtme krüptograafias. See ühesuunaline joondamine hõlbustab tõhusat kontrollimist.
"On põnev näha, et NTT-ga seotud krüptograafid teevad koostööd teadustöös, mis väärib taas "läbimurde" silti, eriti artiklis, mis rikastab meie arusaama kvantarvutusest, mis on meie jaoks veel üks NTT Researchi fookusvaldkond," ütles Kazuhiro Gomi. , NTT Researchi president ja tegevjuht. "Õnnitlused ja parimad soovid kõigile sellel mainekal IEEE konverentsil osalejatele."
Yamakawa ja Zhandry välja töötatud NP-otsingu probleem oli kaks-ühes probleem, mis hõlmab 1) n-sümboli stringi leidmist, mis on antud veaparanduskoodi koodsõna, ja 2) n-sümboli stringi, kus iga sümbol kaardistatakse juhusliku oraakli all nulliga. Iga probleem eraldi on lihtne. Kuid vähemalt klassikaliselt on palju raskem leida ühte sümbolite jada, mis oleks nii koodsõna kui ka nulliks. "Kui olete kvant, saate selle lahendada polünoomilise aja jooksul," ütles dr Zhandry, "aga kui olete klassikaline, siis vähemalt kui kasutate seda musta kasti mudelit, vajate eksponentsiaalset aega." Teisest küljest on võimaliku lahenduse korral lihtne seda kontrollida, kontrollides, kas see lahendab mõlemad kaks probleemi eraldi. Pange tähele, et nagu FOCSi paberile kohane, on see töö põhi- või alustöö. Nagu toodi välja dr Aaronsoni kõnes Simonsi Instituudis (seda arutatakse käesolevas NTT uurimistöös ajaveebi artikkel), Yamakawa-Zhandry argument kuulub kiirendamiste klassi, mida saab hõlpsasti matemaatiliselt kontrollida, kuid tegeliku kvantarvutiga seda niipea praktiliselt ei demonstreerita. Lisaks murrangulisele kontrolliskeemile osutab artikkel ka millelegi uuele kvantkiirenduse ulatuse osas.
„Enne oma tööd oli meil näiteid NP-probleemide kvanteelise kohta, nagu faktooring või musta kasti seadistuses perioodi leidmine. Kuid selgub, et kõigi nende näidete aluseks olev kvantalgoritm oli põhimõtteliselt perioodide leidmine – kuigi perioodide leidmise nende näidete puhul rakendamine oli sageli ebaoluline,” ütles dr Zhandry. "Meie paber näitab, et on vähemalt teine juhtum. Võite seda optimistlikult tõlgendada nii, et on lootust, et kvanteelis on laiemalt levinud, kui võib-olla varem arvasime.
FOCS on teoreetilise arvutiteaduse valdkonna juhtiv konverents, mida sponsoreerib IEEE Arvutiühiskonna Arvutustehnika Matemaatiliste Aluste Tehniline Komitee (TCMF). FOCS 2022 paberite esitamise üleskutses, mis on 63. selline iga-aastane kogunemine, loetles kvantarvutused ühe 17 üldisest huvivaldkonnast. Yamakawa-Zhandry paberit on kavas esitleda 31. oktoobril 2022 kell 10 MT. Selle sündmuse kohta lisateabe saamiseks ja registreerumiseks külastage FOCS 2022 kodulehel.
