NTT-wetenschappers zeggen dat ze een nieuwe manier hebben om kwantumvoordeel te verifiëren

Sunnyvale, Californië – 26 oktober 2022 – NTT Research heeft aangekondigd dat een wetenschapper uit zijn Lab voor cryptografie en informatiebeveiliging (CIS) en een collega van de NTT Sociale Informatica Laboratoria (SIL) hebben een baanbrekend artikel geschreven over kwantumvoordeel. De paper werd geselecteerd om te worden gepresenteerd op het jaarlijkse IEEE Symposium on Foundations of Computer Science (FOCS), dat plaatsvindt van 31 oktober tot en met november. 3 in Deventer.

De co-auteurs van het artikel, getiteld “Verifieerbaar kwantumvoordeel zonder structuur”, zijn Dr. Takashi Yamakawa, vooraanstaand onderzoeker bij NTT SIL en Dr. Mark Zhandry, senior wetenschapper in de NTT-onderzoek CIS-lab. Het werk werd gedeeltelijk gedaan aan de Princeton University, waar Dr. Yamakawa een gastonderzoeker was en Dr. Zhandry ook als assistent-professor in de computerwetenschappen fungeert. 

Het onderwerp kwantumvoordeel (of kwantumversnelling) heeft betrekking op het soort problemen dat kwantumcomputers sneller kunnen oplossen dan klassieke of niet-kwantumcomputers en hoeveel sneller ze zijn. De problemen in kwestie worden gewoonlijk beschreven als niet-deterministische polynomiale tijd (NP) klasse. Hoeveel voordeel kan in grote mate variëren. Een kwantumcomputer kan een bepaald probleem misschien oplossen in een minuut of een seconde die een klassieke computer een week kost, of mogelijk een onpeilbare exponentiële hoeveelheid tijd. In dit artikel gaan de auteurs in op de uitdaging om deze superioriteit te verifiëren, en wel op een efficiënte manier. Tot op heden hebben demonstraties van kwantumvoordeel een significante "structuur" of heen-en-weer communicatie tussen twee of meer partijen met zich meegebracht. De doorbraak van het Yamakawa- en Zhandry-document is het aantonen van een moeilijk NP-probleem waarbij verificatie mogelijk is zonder structuur.

"Dit is de eerste keer dat we een exponentiële kwantumversnelling hebben gezien voor een NP-zoekprobleem, waarvoor alleen een willekeurig orakel nodig is", zegt professor computerwetenschappen van de Universiteit van Texas in Austin, Dr. Scott Aaronson, die commentaar gaf op een vroege versie van de paper tijdens een workshop op 13 juni 2022 in het Simons Institute for the Theory of Computing. Door alleen een willekeurig orakel te vereisen, dwz een theoretische zwarte doos die willekeurige antwoorden op elke vraag genereert, bouwden Yamakawa en Zhandry hun probleem op ongestructureerde rekenkundige aannames. Als zodanig sluit hun probleem beter aan bij eenrichtingsfuncties in plaats van bij gestructureerde, zoals die worden aangetroffen in cryptografie met openbare sleutels. Die eenrichtingsafstemming maakt een efficiënte verificatie mogelijk.

"Het is opwindend om NTT-gelieerde cryptografen te zien samenwerken aan onderzoek dat opnieuw het label 'doorbraak' verdient, vooral in een paper dat ons begrip van kwantumcomputing verrijkt, een ander aandachtsgebied voor ons bij NTT Research," zei Kazuhiro Gomi , NTT Research President en CEO. "Gefeliciteerd en de beste wensen aan alle deelnemers aan deze prestigieuze IEEE-conferentie." 

Het NP-zoekprobleem dat Yamakawa en Zhandry bedachten, was een twee-in-een-probleem dat inhoudt dat men 1) een n-symboolreeks moet vinden die een codewoord is van een gegeven foutcorrectiecode, en 2) een n-symboolreeks waarbij elk symbool wordt toegewezen aan nul onder het willekeurige orakel. Elk probleem afzonderlijk is eenvoudig. Maar het vinden van een enkele reeks symbolen die zowel een codewoord is als een kaart naar nul, is veel moeilijker, althans klassiek. "Als je kwantum bent, kun je dit in polynomiale tijd oplossen," zei Dr. Zhandry, "maar als je klassiek bent, heb je tenminste exponentiële tijd nodig als je in dit black-box-model zit." Aan de andere kant, gegeven een mogelijke oplossing, is het eenvoudig om het te verifiëren door te controleren of het elk van de twee problemen afzonderlijk oplost. Merk op dat, zoals het een paper voor FOCS betaamt, dit werk fundamenteel of fundamenteel is. Zoals opgemerkt in de lezing van Dr. Aaronson aan het Simons Institute (besproken in dit NTT-onderzoek) blog artikel), valt het Yamakawa-Zhandry-argument in een klasse van versnellingen die gemakkelijk wiskundig kunnen worden gecontroleerd, maar op korte termijn niet praktisch kunnen worden aangetoond door een echte kwantumcomputer. Naast het baanbrekende verificatieschema wijst het artikel echter ook op iets nieuws met betrekking tot de mate van kwantumversnelling.

"Voorafgaand aan ons werk hadden we voorbeelden van kwantumvoordeel voor NP-problemen, zoals factoring of, in de black box-setting, periodebepaling. Maar het blijkt dat het kwantumalgoritme dat aan al deze voorbeelden ten grondslag ligt in feite periodebepaling was, hoewel het vaak niet triviaal was om te laten zien hoe periodebepaling op deze voorbeelden kon worden toegepast, "zei Dr. Zhandry. 'Onze krant laat zien dat er op zijn minst een tweede geval is. Je zou dat optimistisch kunnen interpreteren als zeggen dat er hoop is dat kwantumvoordeel meer wijdverbreid is dan we misschien eerder dachten."

FOCS, gesponsord door de IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), is een toonaangevende conferentie op het gebied van theoretische informatica. De call for papers voor FOCS 2022, de 63e van zo'n jaarlijkse bijeenkomst, noemde kwantumcomputing als een van de 17 algemene interessegebieden. De presentatie van de Yamakawa-Zhandry-paper is gepland op 31 oktober 2022 om 10:15 uur MT. Ga voor meer informatie over en aanmelding voor dit evenement naar de FOCS 2022 website.