Sunnyvale, Kalifornia – 26. október 2022. – Az NTT Research bejelentette, hogy egy tudós Kriptográfiai és Információbiztonsági (CIS) Lab és egy kolléga a NTT Társadalominformatikai Laboratóriumok (SIL) úttörő tanulmányt írtak a kvantumelőnyökről. A tanulmányt az éves IEEE Symposium on Foundations of Computer Science (FOCS) rendezvényen való bemutatásra választották, amelyre október 31. és november között kerül sor. 3 Denverben.
A lap társszerzői „Ellenőrizhető kvantumelőny struktúra nélkül”, Dr. Takashi Yamakawa, az NTT SIL jeles kutatója és Dr. Mark Zhandry, a NTT kutatás CIS Lab. A munkát részben a Princeton Egyetemen végezték, ahol Dr. Yamakawa vendégkutató volt, Dr. Zhandry pedig a számítástechnika adjunktusaként is szolgál.
A kvantumelőny (vagy kvantumgyorsítás) témája azokhoz a problémákhoz kapcsolódik, amelyeket a kvantumszámítógépek gyorsabban tudnak megoldani, mint a klasszikus vagy nem kvantumszámítógépek, és mennyivel gyorsabbak. A kérdéses problémákat általában nem-determinisztikus polinom-idő (NP) osztályként írják le. Az, hogy mekkora előny, nagymértékben változhat. Egy kvantumszámítógép egy perc vagy másodperc alatt képes megoldani egy adott problémát, ami egy klasszikus számítógépnek egy hétbe, vagy esetleg felmérhetetlenül exponenciálisan sok időt vesz igénybe. Ebben a cikkben a szerzők azzal a kihívással foglalkoznak, hogy ellenőrizzék ezt a felsőbbrendűséget, és ezt hatékonyan tegyék. A mai napig a kvantumelőny demonstrációi jelentős „struktúrát” vagy oda-vissza kommunikációt jelentettek két vagy több fél között. A Yamakawa és a Zhandry papír áttörése egy olyan NP nehéz probléma bemutatása, ahol az ellenőrzés struktúra nélkül is lehetséges.
"Ez az első alkalom, hogy egy NP-keresési probléma exponenciális kvantumgyorsulását látjuk, amelyhez csak véletlenszerű jóslatra van szükség" - mondta Dr. Scott Aaronson, az austini Texasi Egyetem számítástechnikai professzora, aki kommentálta a korai verziót. a cikk egy műhelymunka során 13. június 2022-án a Simons Institute for the Theory of Computing-ban. Yamakawa és Zhandry azáltal, hogy csak egy véletlenszerű orákulumra, azaz egy elméleti fekete dobozra volt szükség, amely véletlenszerű válaszokat generál minden lekérdezésre, strukturálatlan számítási feltevésekre építette fel problémáját. Mint ilyen, problémájuk jobban illeszkedik az egyirányú funkciókhoz, nem pedig a strukturált függvényekhez, mint amilyenek a nyilvános kulcsú kriptográfiában találhatók. Ez az egyirányú igazítás megkönnyíti a hatékony ellenőrzést.
„Izgalmas látni, hogy az NTT-vel kapcsolatban álló kriptográfusok olyan kutatásban működnek együtt, amely ismét megérdemli az „áttörés” címkét, különösen egy olyan írásban, amely gazdagítja a kvantumszámítástechnikával kapcsolatos ismereteinket, amely egy másik fókuszterület az NTT Researchnél” – mondta Kazuhiro Gomi. , az NTT Research elnök-vezérigazgatója. "Gratulálunk és a legjobbakat kívánom minden résztvevőnek ezen a tekintélyes IEEE konferencián."
A Yamakawa és Zhandry által kidolgozott NP-keresési probléma egy kettő az egyben probléma volt, amely magában foglalja 1) egy n-szimbólum-karakterlánc megtalálását, amely egy adott hibajavító kód kódszava, és 2) egy n-szimbólum-karakterláncot, ahol mindegyik szimbólum nullára van leképezve a véletlenszerű orákulum alatt. Minden probléma külön-külön könnyű. De sokkal nehezebb megtalálni egyetlen olyan szimbólumsort, amely egyszerre kódszó és nullára leképez, legalábbis klasszikusan. "Ha kvantum, meg tudod oldani ezt polinomiális időben" - mondta Dr. Zhandry - "de ha klasszikus vagy, legalább ebben a fekete dobozos modellben, akkor exponenciális időre van szükséged." Másrészt, ha van egy lehetséges megoldás, egyszerűen ellenőrizhető, hogy ellenőrizni kell, hogy az külön megoldja-e mind a két problémát. Vegye figyelembe, hogy a FOCS papírjaihoz hasonlóan ez a munka alapvető vagy alapvető. Amint arra Dr. Aaronson a Simons Institute-ban tartott előadásában rámutatott (amelyet ebben az NTT-kutatásban tárgyalunk blogcikk), a Yamakawa-Zhandry-érv a gyorsítások egy osztályába tartozik, matematikailag könnyen ellenőrizhető, de gyakorlatilag egy kvantumszámítógéppel egyhamar nem demonstrálható. Az úttörő verifikációs sémán túl azonban a tanulmány valami újdonságra is rámutat a kvantumgyorsítás mértékét illetően.
„Munkánkat megelőzően voltak példáink az NP-problémák kvantumelőnyére, például a faktorálásra vagy a fekete doboz beállításánál az időszak megállapítására. De kiderült, hogy az összes példa alapjául szolgáló kvantumalgoritmus alapvetően perióduskeresés volt – bár a perióduskeresés alkalmazásának bemutatása ezekre a példákra gyakran nem volt triviális” – mondta Dr. Zhandry. „A lapunk azt mutatja, hogy van legalább egy második eset. Ezt optimistán úgy is értelmezheti, hogy van remény arra, hogy a kvantumelőny szélesebb körben elterjedt, mint azt korábban gondoltuk.”
Az IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) által szponzorált FOCS az elméleti számítástechnika egyik vezető konferenciája. A 2022. ilyen éves összejövetelre, a FOCS 63-re szóló pályázati felhívás a kvantumszámítást a 17 általános érdeklődési terület egyikeként sorolta fel. A Yamakawa-Zhandry papírt a tervek szerint 31. október 2022-én, délelőtt 10:15-kor mutatják be. Ha többet szeretne megtudni erről az eseményről, és regisztrálni szeretne, látogasson el a FOCS 2022 weboldal.
