Študent Grad je rešil temeljno vprašanje kvantnega računanja


Spomladi leta 2017 se je Urmila Mahadev znašla v tem, kar bi večina diplomantov menila, da ima precej sladek položaj. Pravkar je rešila velik problem pri kvantnem računanju, študiju računalnikov, ki izvirajo iz čudnih zakonov kvantne fizike. V kombinaciji z njenimi prejšnjimi dokumenti, nov rezultat Mahadeva, o tem, kar se imenuje slepo računanje, je "jasno, da je naraščajoča zvezda," je povedal Scott Aaronson, računalniški znanstvenik na Univerzi v Teksasu v Austinu.

Revija Quanta


fotografija avtorja

O podjetju

Prvotna zgodba, ki jo je prejel z dovoljenjem revije Quanta, uredniško neodvisna publikacija fundacije Simons, katere poslanstvo je izboljšati razumevanje znanosti s področja javnega obveščanja tako, da pokriva raziskovalne dosežke in trende v matematiki ter fizikalnih in življenjskih znanostih.

Mahadev, ki je bila tedaj 28 let, je že v sedmem letu diplomiranja na Univerzi v Kaliforniji, Berkeley, ki je bila davno oddaljena od dneva, ko je večina študentov postala nestrpna za diplomiranje. Zdaj, končno, je imela opravila "zelo lepo doktorat znanosti. "je dejala Umesh Vazirani, njen doktorski svetovalec v Berkeleyju.

Toda Mahadev tega leta ni diplomiral. Ni niti razmišljala o diplomiranju. Ni bila končana.

Že več kot pet let je v svojih pogledih imela drugačno raziskovalno težavo, ki jo je Aaronson imenoval "eno od najpomembnejših vprašanj, ki jih lahko vprašate pri kvantnem izračunu." Namreč: Če zaprosite za kvantni računalnik, da opravi izračun kako lahko veste, ali je v resnici sledil vašim navodilom ali sploh kaj naredil kvantno?

To vprašanje bo kmalu daleč od akademskega. Pred pretekom preteklih let, raziskovalci upajo, kvantni računalniki morda lahko ponudijo eksponentno hitrost pri številnih težavah, od modeliranja obnašanja okoli črne luknje do simulacije, kako se zruši velik protein.

Toda, ko lahko računalniški računalnik opravi izračune, ki jih klasični računalnik ne more storiti, kako bomo vedeli, ali jih je pravilno naredil? Če ne zaupate navadnemu računalniku, lahko v teoriji natančno preučite vsak korak svojih izračunov zase. Ampak kvantni sistemi so temeljito odporni na tovrstno preverjanje. Njihova notranja obdelava je neverjetno zapletena: za opis notranjega stanja računalnika s samo nekaj sto kvantnimi bitji (ali "kubi") bi potrebovali trdi disk, ki je večji od celotnega vidnega vesolja.

In tudi če bi nekako imeli dovolj prostora, da bi napisali ta opis, ne bi bilo mogoče priti do tega. Notranje stanje kvantnega računalnika je navadno superpozicija mnogih različnih nekonkurnih, "klasičnih" stanj (kot je Schrödingerjeva mačka, ki je hkrati mrtva in živa). Toda takoj, ko merite kvantno stanje, se zruši v eno od teh klasičnih stanj. Preverite v 300-kvubitnem kvantnem računalniku, v bistvu pa vse, kar boste videli, je 300 klasičnih bitov – ničle in tiste – nasmehljivo nasmejanih.

"Kvantni računalnik je zelo močan, vendar je tudi zelo skrivnosten", je dejal Vazirani.

Glede na te omejitve so se računalniški znanstveniki že dolgo spraševali, ali je kvantni računalnik mogoče zagotoviti kakršno koli garancijsko garancijo, da je dejansko storila tisto, kar je zahtevala. "Je interakcija med kvantnim in klasičnim svetom dovolj močna, da je dialog možen?" Je vprašal Dorit Aharonov, računalniški znanstvenik na Hebrejski univerzi v Jeruzalemu.

V svojem drugem letu šolanja je Mahadev zaradi tega vznemirila ta vzrok, tudi zato, ker ji ni v celoti razumela. V letih, ki so sledila, je poskušala en pristop za drugim. "Imela sem veliko trenutkov, ko mislim, da delam stvari prav, potem pa zelo hitro ali po enem letu zlomijo," je dejala.

Toda ona se ni odrekla. Mahadev je pokazal raven trajne odločenosti, ki jo je Vazirani nikoli ni videl. "Urmila je v tem smislu povsem izredno", je dejal.

Po osmih letih šolanja je Mahadev uspel. Prišla je z interaktivnim protokolom, s katerim lahko uporabniki brez lastnih kvantnih pooblastil kljub temu uporabljajo kriptografijo, da bi uporabili kvantni računalnik in ga vozili, kjerkoli želijo, z gotovostjo, da kvantni računalnik sledi njihovim naročilom. Mahadjev pristop, je dejal Vazirani, daje uporabniku "vzvoda, da se računalnik ne more odtrgati."

Za podiplomski študent, da doseže tak rezultat, kot solo napor je "precej presenetljivo," je dejal Aaronson.

Mahadev, ki je zdaj postdoktorski raziskovalec v Berkeleyju, je nedavno predstavila svoj protokol na letnem simpoziju o temeljih računalništva, eni največjih konferenc teoretične računalniške znanosti, ki je letos potekal v Parizu. Njeno delo je dobilo nagrade najboljšega papirja in najboljšega študentskega papirja, redko čast za teoretičnega računalniškega znanstvenika.

Thomas Vidick, računalniški znanstvenik na Kalifornijskem tehnološkem inštitutu, ki je v preteklosti sodeloval z Mahadevom, je v svojem blogu rekel, da je njen rezultat "ena od najbolj izjemnih idej, ki so se pojavile na vmesniku kvantnega računalništva in teoretične računalništva v V zadnjih letih."

Kvantni raziskovalci so vznemirjeni ne samo o tem, kaj doseže protokol Mahadeva, ampak tudi o radikalno novem pristopu, ki jo je prinesla na problem. Uporaba klasične kriptografije v kvantnem področju je "resnično nova ideja", napisal je Vidick. "Pričakujem, da bo še veliko rezultatov nadaljevalo pri oblikovanju teh idej."

Dolga cesta

Mahadev se je v družini zdravnikov odprla v Los Angelesu, kjer se je udeležila Univerze v Južni Kaliforniji, kjer je odšla iz ene študijske točke v drugo, najprej prepričana samo, da ne želi postati zdravnica. Nato je bil razred, ki ga je poučeval računalniški znanstvenik Leonard Adleman, eden od ustvarjalcev znanega šifrirnega algoritma RSA, navdušil nad teoretično računalniško znanostjo. V Berkeley se je prijavila na podiplomski šoli, v njeni vlogi pa je pojasnila, da jo zanima vse vidike teoretičnega računalništva – razen kvantnega računanja.

"Zvenelo je kot najbolj tuje, kar sem vedel vsaj," je rekla.

Toda, ko je bila v Berkeleyju, so ji dostopne razlage Vazirana kmalu spremenile misli. Uvedel jo je na vprašanje, kako najti protokol za preverjanje kvantnega izračuna, in problem je "resnično uprla svojo domišljijo", je dejal Vazirani.

"Protokoli so kot uganke," je pojasnil Mahadev. "Menim, da so lažje vstopiti kot druga vprašanja, saj lahko takoj začnete razmišljati o protokolih in jih nato zlomiti, kar vam omogoča, da vidite, kako delujejo." Izbrala je težavo za svoje doktorske raziskave, ki se je začela na kar je Vazirani imenoval »zelo dolga pot«.

Če kvantni računalnik lahko reši problem, ki ga klasični računalnik ne more, to ne pomeni samodejno, bo rešitev težko preveriti. Vzemimo, na primer, problem faktoringa velikih števil, nalogo, ki bi jo velik kvantni računalnik lahko rešil učinkovito, vendar se domneva, da je izven dosega katerega koli klasičnega računalnika. Tudi če klasični računalnik ne more dejavnik števila, lahko brez težav preveri, ali je faktorizacija računalnika v računalniku pravilna – samo je potrebno množiti dejavnike skupaj in preveriti, ali dajejo pravi odgovor.

Vendar računalniški znanstveniki verjamejo (in so pred kratkim naredili korak proti dokazovanju), da številne težave, ki jih lahko reši kvantni računalnik, nimajo te značilnosti. Z drugimi besedami, klasični računalnik jih ne more rešiti le, temveč tudi ne more prepoznati, ali je predlagana rešitev pravilna. Glede na to okoli leta 2004 je Daniel Gottesman, fizik na Perimetrskem inštitutu za teoretično fiziko v Waterlooju, Ontario, postavil vprašanje, ali je mogoče sprejeti vsak protokol, s katerim lahko kvantni računalnik dokaže, kvantni opazovalec, da je resnično storil, kar je trdil.

V štirih letih so raziskovalci kvantnih računov dosegli delni odgovor. Možno je, da sta dve različni ekipi pokazali, da je kvantni računalnik dokazal svoje izračune, in ne povsem klasičen preveritelj, ampak preveritelju, ki ima dostop do zelo majhen kvantni računalnik sama. Raziskovalci so kasneje izpopolnili ta pristop in pokazali, da je vsa preveritvena potreba zmožna meriti en sam kubit hkrati.

In leta 2012, skupina raziskovalcev, vključno z Vazirani, je pokazala, da lahko povsem klasični preveritelj preveri kvantne izračune, če jih izvaja par kvantnih računalnikov, ki ne morejo komunicirati drug z drugim. Toda ta dokument je bil prilagojen temu specifičnemu scenariju, zdelo se je, da je težava zadela tisti del, je dejal Gottesman. "Mislim, da so bili verjetno ljudje, ki so mislili, da ne morete iti dlje."

Tokrat je Mahadev naletel na problem preverjanja. Sprva je poskušala priti do "brezpogojnega" rezultata, ki ne predpostavlja, kaj lahko kvantni računalnik naredi ali ne. Toda po tem, ko je za nekaj časa delala na problemu brez napredka, je Vazirani namesto tega predlagal možnost uporabe "post-kvantne" kriptografije – to je kriptografije, za katero raziskovalci verjamejo, da je zmožen celo kvantnega računalnika, ne vem zagotovo. (Metode, kot je RSA algoritem, ki se uporabljajo za šifriranje stvari, kot so spletne transakcije, niso post-kvantne – bi lahko velik kvantni računalnik zlomil, ker je njihova varnost odvisna od trdote faktoringa velikih številk.)

V letu 2016 je Mahadev in Vazirani delal na drugačnem problemu, ki se je kasneje izkazal za ključnega pomena. V sodelovanju s Paulom Christianom, računalniškim znanstvenikom, ki je zdaj v podjetju OpenAI v San Franciscu, so razvili način uporabe kriptografije, da bi dobili kvantni računalnik, da bi zgradil tisto, kar bomo imenovali "skrivnostno stanje" – tisto, za katerega je znan opis klasični preveritelj, ne pa kvantni računalnik sam.

Njihov postopek se opira na tisto, kar se imenuje funkcija "vrača" – tista, ki jo je mogoče enostavno izvesti, vendar ga je težko obrniti, če imate tajni kriptografski ključ. (Raziskovalci niso vedeli, kako bi dejansko lahko zgradili ustrezno funkcijo vračanja – to bi prišlo kasneje.) Funkcija je prav tako potrebna, da je "dva v eno", kar pomeni, da vsaka proizvodnja ustreza dvema različnima vhodoma. Pomislite, na primer na funkcijo, da številke kvadratov – razen številke 0, vsak izhod (na primer 9) ima dva ustrezna vhoda (3 in -3).

Oborožene s takšno funkcijo lahko dobite kvantni računalnik, da ustvarite skrivno stanje na naslednji način: Najprej zahtevate, da računalnik zgradi superpozicijo vseh možnih vhodov v funkcijo (to se lahko zdi zapleteno, če računalnik izvede, vendar je pravzaprav enostavno). Potem poveste računalniku, da aplikacijo uporabite za to velikansko superpozicijo in ustvarite novo stanje, ki je superpoloženje vseh možnih rezultatov funkcije. Vhodni in izhodni superposojci bodo zapleteni, kar pomeni, da bodo meritve na enem od njih takoj vplivale na drugo.

Nato zahtevate, da računalnik izmeri izhodno stanje in vam pove rezultate. To merjenje poruši izhodno stanje navzdol samo na enega od možnih izhajanj in stanje vhoda se takoj zruši, da se bo ujemalo, ker so zapletene – na primer, če uporabljate funkcijo kvadratiranja, potem če je izhod stanje 9, vnos bo propadel navzdol do superpozicije 3 in -3 stanja.

Ampak ne pozabite, da uporabljate funkcijo vračanja. Imate skrivni ključ v vratih, tako da lahko preprosto ugotovite dve državi, ki sestavljata vhodno superpozicijo. Toda kvantni računalnik ne more. In ne more preprosto izmeriti vhodne superpozicije, da bi ugotovili, iz česa je izdelana, ker bi ta meritev sesula še naprej, tako da bi računalnik zapustil enega od obeh vhodov, ne da bi drugače ugotovil drug način.

Leta 2017 je Mahadev ugotovil, kako zgraditi funkcije za vračanje v jedru metode tajnega stanja z uporabo vrste kriptografije, imenovane učenje z napakami (LWE). Z uporabo teh funkcij za zaklepanje je lahko ustvarila kvantno različico "slepo" računanja, s katero lahko uporabniki računalništva v oblaku lahko prikrijejo svoje podatke, tako da računalniški računalnik v oblaku ne more prebrati, tudi če se računalniško podpira. Kmalu zatem so se Mahadev, Vazirani in Christiano združili z Vidickom in Zvika Brakerski (Weizmannovega inštituta za znanost v Izraelu), da bi še bolj nadgrajevali te funkcije, s pomočjo metode tajnega stanja razvili brezhiben način za kvantni računalnik za ustvarjanje dokazljivo naključnih števil.

Mahadev bi lahko dosegel moč teh rezultatov, vendar je bila odločena nadaljevati delo, dokler ni rešila težave s preverjanjem. "Nikoli nisem razmišljal o diplomi, ker moj cilj ni bil nikoli diplomiral," je rekla.

Ne vedo, ali bi jo lahko rešila, je bila stresna včasih. Ampak, rekla je, "sem porabila nekaj časa, da se učim o stvareh, ki me zanima, zato ne bi bilo resnično izguba časa."

V kamnu

Mahadev je preizkusil različna načina pridobivanja metode tajnega stanja za protokol za preverjanje, a za nekaj časa ni dobil ničesar. Nato je pomislila: Raziskovalci so že pokazali, da lahko preveritelj preveri kvantni računalnik, če je preveritelj sposoben meriti kvantne bitove. Po definiciji klasični preveritelj nima te sposobnosti. Kaj pa, če bi klasični preveritelj nekako prisilil kvantni računalnik, da sam opravi meritve in jih iskreno poroča?

Zapleten del, ki ga je Mahadev spoznal, bi bil, da bi se kvantni računalnik zavezal, do katere države bo ukrepal, preden bi vedel, katere vrste meritev bi preveritelj zahteval – v nasprotnem primeru bi bilo enostavno, da bi računalnik lahko prevaril preveritelja . Takrat pride v stik metoda skrivnega stanja: Mahadev protokol zahteva, da bi kvantni računalnik najprej ustvaril skrivno stanje in ga potem zapletel z državo, ki naj bi jo merila. Šele potem računalnik ugotovi, kakšno mero je treba izvesti.

Ker računalnik ne pozna sestavine skrivnega stanja, vendar preveritelj ne, je Mahadev pokazal, da je nemogoče, da bi kvantni računalnik znal goljufati, ne da bi pri tem pustil nedvoumne sledi svoje dvojnosti. V bistvu je Vidick zapisal, da je kubit, ki ga računalnik meri, "nastavljen v kriptografskem kamnu". Zaradi tega, če rezultati meritev izgledajo kot pravi dokaz, se lahko preveritelj prepriča, da so resnično.

"To je čudovita ideja!" Je zapisal Vidič. "Olušči me vsakič, ko ga Urmila razloži."

Mahadev protokol za preverjanje – skupaj z generatorjem naključnih števil in slepim načinom šifriranja – je odvisen od predpostavke, da kvantni računalniki ne morejo razbiti LWE. Trenutno se LWE šteje za vodilnega kandidata za post-kvantno kriptografijo in ga bo lahko Nacionalni inštitut za standarde in tehnologijo kmalu sprejel kot svoj novi kriptografski standard, ki bi nadomestil tiste, ki bi jih lahko prekinil kvantni računalnik. To ne zagotavlja, da je resnično varno pred kvantnimi računalniki, je Gottesman opozoril. "Toda doslej je dober," je dejal. "Nihče ni našel dokazov, da je verjetno zlomljiv."

V vsakem primeru je odvisnost od LWE protokola Mahadevevemu delu okus, ki je zmagal, je zapisal Vidick. Edini način, da bi kvantni računalnik lahko prevaril protokol, je, če je nekdo iz svetovnega kvantnega računalništva ugotovil, kako prekiniti LWE, kar bi bilo sama po sebi izjemen dosežek.

Protokol Mahadeva verjetno ne bo izveden v pravem kvantnem računalniku v bližnji prihodnosti. Zaenkrat protokol zahteva preveč računalniške moči, da je praktičen. Toda to se lahko spremeni v prihodnjih letih, saj se bodo kvantni računalniki povečali in raziskovalci racionalizirali protokol.

Protokol Mahadeva verjetno ne bo izvedljiv v naslednjih petih letih, vendar "niti v fantaziji ni popolnoma izključeno", je dejal Aaronson. "To je nekaj, na kar bi lahko začeli razmišljati, če vse gre dobro, na naslednji stopnji evolucije kvantnih računalnikov."

In glede na to, kako hitro se polje premika, ta stopnja lahko prispeva prej in ne kasneje. Konec koncev, je dejal Vidick, raziskovalci mislili, da bi bilo veliko let, preden bi kvantni računalnik lahko rešil kakršne koli težave, ki jih klasični računalnik ne more storiti. "Zdaj", je dejal, "ljudje mislijo, da se bo zgodilo čez eno leto ali dve."

Kar se tiče Mahadeva, je reševanje njene najljubše težave pustilo malo občutka na morju. Ona želi, da bi lahko razumela samo tisto, kar je v zvezi s tem problemom, zaradi česar je bilo prav za njo, je dejala. "Zdaj moram najti novo vprašanje, zato bi bilo lepo vedeti."

Toda teoretični računalniški strokovnjaki vidijo Mahadevovo poenotenje kvantnega računanja in kriptografije ne toliko kot konec zgodbe, temveč kot začetno raziskavo o tem, kaj upa bo dokazano bogato vino idej.

"Moj občutek je, da bo veliko spremljanja," je dejal Aharonov. "Veselim se več rezultatov iz Urmile."

Prvotna zgodba ponatisnil z dovoljenjem Revija Quanta, uredniško neodvisna delitev SimonsFoundation.org katerega poslanstvo je izboljšati razumevanje znanosti s strani javnosti s pomočjo kritja raziskovalnega razvoja in trendov v matematiki ter fizikalnih in življenjskih znanosti.


Več velikih WIRED zgodbe