NTT:n tutkijat sanovat, että heillä on uusi tapa varmistaa kvanttietu

Sunnyvale, Kalifornia – 26. lokakuuta 2022 – NTT Research ilmoitti, että sen tutkija Cryptography and Information Security (CIS) Lab ja kollega NTT Social Informatics Laboratories (SIL) ovat kirjoittaneet uraauurtavan paperin kvanttieduista. Paperi valittiin esitettäväksi vuotuisessa IEEE Symposium on Foundations of Computer Science (FOCS) -tapahtumassa, joka järjestetään 31. lokakuuta–marraskuuta. 3 Denverissä.

Lehden, jonka otsikko on "Todennettavissa oleva kvanttietu ilman rakennetta”, ovat tohtori Takashi Yamakawa, arvostettu tutkija NTT SIL:stä ja tohtori Mark Zhandry, vanhempi tutkija NTT-tutkimus CIS Lab. Työ tehtiin osittain Princetonin yliopistossa, jossa tohtori Yamakawa oli vieraileva tutkija ja tohtori Zhandry toimii myös tietojenkäsittelytieteen apulaisprofessorina. 

Kvanttiedun (tai kvanttinopeuden) aihe liittyy siihen, millaisia ​​ongelmia kvanttitietokoneet voivat ratkaista nopeammin kuin klassiset tai ei-kvanttitietokoneet ja kuinka paljon nopeampia ne ovat. Kyseisiä ongelmia kuvataan yleisesti ei-deterministiseksi polynomiaikaluokaksi (NP). Kuinka paljon hyötyä voi vaihdella suuresti. Kvanttitietokone voi pystyä ratkaisemaan tietyn ongelman minuutissa tai sekunnissa, joka kestää klassisen tietokoneen viikossa tai mahdollisesti käsittämättömän eksponentiaalisen ajan. Tässä artikkelissa kirjoittajat tarkastelevat tämän paremmuuden varmistamisen haastetta ja tekevät sen tehokkaasti. Tähän mennessä kvanttiedun osoituksiin on liittynyt merkittävää "rakennetta" tai edestakaisin kommunikointia kahden tai useamman osapuolen välillä. Yamakawan ja Zhandryn paperin läpimurto on osoittaa NP vaikea ongelma, jossa todentaminen on mahdollista ilman rakennetta.

"Tämä on ensimmäinen kerta, kun näemme eksponentiaalisen kvanttinopeuden NP-hakuongelmassa, joka vaatii vain satunnaisen oraakkelin", sanoi Texasin yliopiston Austinissa tietojenkäsittelytieteen professori tohtori Scott Aaronson, joka kommentoi varhaista versiota. paperin työpajassa 13 Simons Institute for the Theory of Computingissa. Vaatimalla vain satunnaista oraakkelia, eli teoreettista mustaa laatikkoa, joka tuottaa satunnaisia ​​vastauksia jokaiseen kyselyyn, Yamakawa ja Zhandry rakensivat ongelmansa jäsentämättömille laskennallisille olettamuksille. Sellaisenaan heidän ongelmansa liittyy lähemmin yksisuuntaisiin toimintoihin strukturoitujen toimintojen sijaan, kuten julkisen avaimen salakirjoituksessa. Tämä yksisuuntainen kohdistus helpottaa tehokasta todentamista.

"On jännittävää nähdä NTT:hen sidoksissa olevien kryptografien tekevän yhteistyötä tutkimuksessa, joka ansaitsee jälleen "läpimurron" leiman, erityisesti artikkelissa, joka rikastaa ymmärrystämme kvanttilaskennasta, joka on toinen NTT Researchin painopistealue, Kazuhiro Gomi sanoi. , NTT Tutkimusjohtaja. "Onnittelut ja parhaat onnittelut kaikille tämän arvostetun IEEE-konferenssin osallistujille." 

Yamakawan ja Zhandryn kehittämä NP-hakuongelma oli kaksi yhdessä -ongelma, joka edellyttää 1) n-symbolijonon löytämistä, joka on tietyn virheenkorjauskoodin koodisana, ja 2) n-symbolijonon, jossa jokainen symboli on kartoitettu nollaan satunnaisen oraakkelin alla. Jokainen ongelma erikseen on helppoa. Mutta yhden merkkijonon löytäminen, joka on sekä koodisana että nollaan, on paljon vaikeampaa, ainakin klassisesti. "Jos olet kvantti, voit ratkaista tämän polynomiajassa", tohtori Zhandry sanoi, "mutta jos olet klassinen, ainakin jos olet tässä black box -mallissa, tarvitset eksponentiaalista aikaa." Toisaalta, kun otetaan huomioon mahdollinen ratkaisu, se on helppo tarkistaa tarkistamalla, että se ratkaisee erikseen molemmat ongelmat. Huomaa, että kuten FOCS-paperille kuuluu, tämä työ on perus- tai perustavaa laatua olevaa työtä. Kuten tohtori Aaronsonin puheessa Simons Institutessa (käsitelty tässä NTT:n tutkimuksessa) blogiartikkeli), Yamakawa-Zhandry-argumentti kuuluu nopeuksien luokkaan, joka voidaan helposti tarkistaa matemaattisesti, mutta sitä ei voida osoittaa käytännössä todellisella kvanttitietokoneella lähiaikoina. Sen uraauurtavan verifiointijärjestelmän lisäksi paperi viittaa kuitenkin myös johonkin uuteen kvanttinopeuden laajuuteen.

"Ennen työtämme meillä oli esimerkkejä kvanttieduista NP-ongelmiin, kuten factoring tai black box -asetuksessa jaksohaku. Mutta käy ilmi, että kaikkien näiden esimerkkien taustalla oleva kvanttialgoritmi oli pohjimmiltaan jaksohaku – vaikka jaksohaun soveltaminen näissä esimerkeissä ei useinkaan ollut triviaalia”, tohtori Zhandry sanoi. ”Paperimme osoittaa, että on olemassa ainakin toinen tapaus. Voit optimistisesti tulkita sen sanomalla, että on toivoa, että kvanttietu on laajempi kuin ehkä aiemmin luulimme.

IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) sponsoroima FOCS on johtava konferenssi teoreettisen tietojenkäsittelytieteen alalla. FOCS 2022:n, 63. vuosittaisen kokouksen, asiakirjapyynnössä kvanttilaskenta listattiin yhdeksi 17 yleisestä kiinnostuksen kohteesta. Yamakawa-Zhandry-paperi on tarkoitus esittää 31. lokakuuta 2022 klo 10 MT. Lisätietoja tästä tapahtumasta ja ilmoittautuminen on osoitteessa FOCS 2022 -sivustolta.