Peeter Shor ei kavatsenud internetti lõhkuda. Kuid 1990. aastate keskel välja töötatud algoritm ähvardas just seda teha. Sees maamärk paber, Shor näitas, kuidas hüpoteetiline arvuti, mis kasutas kvantfüüsika veidrusi, suudab suuri numbreid algteguriteks jagada palju kiiremini kui ükski tavaline klassikaline masin.

Tulemusel oli matemaatikast palju kaugemale ulatuv mõju. Sel ajal nimetas Interneti-turvalisuse oluline komponent avaliku võtme krüptograafia tugines eeldusele, et suurte arvude faktooreerimine on arvutuslikult nii keeruline, et see on tegelikult võimatu. See eeldus toetab ka tänapäeval mõningaid kriitilisi protokolle. Shori algoritm näitas, et see ebaõnnestub võimsas maailmas suurejooneliselt kvantarvutid.

Viimase 30 aasta jooksul on arvutiteadlased Shori algoritmi sujuvamaks muutnud, et valmistuda päevaks, mil kvanttehnoloogia on selle käivitamiseks piisavalt küps. Aga uus variant, New Yorgi ülikooli arvutiteadlasest Oded Regev, on põhimõtteliselt uues mõttes kiirem. See on esimene, mis parandab suhet faktoritava arvu suuruse ja selle faktoriseerimiseks vajalike kvantoperatsioonide arvu vahel.

"On tõesti tähelepanuväärne, et ilmselt on keegi suutnud selle tulemuse keerukust palju-palju aastaid hiljem parandada," ütles Ashley Montanaro, Bristoli ülikooli kvantarvutusteadlane. "See on tõesti põnev."

Martin EkeråRootsi riikliku sideturbeameti krüptograaf nõustus, et Regevi artikkel on huvitav, kuid hoiatas, et tehnika tasemest ületamine praktikas nõuab täiendavat optimeerimist. "Shori algsed algoritmid on juba üllatavalt tõhusad, nii et pole triviaalne teha suuri parandusi," kirjutas ta e-kirjas.

Regev töötas välja oma uue algoritmi, täiendades Shori algoritmi kõrgmõõtmelise geomeetriaga tegeleva krüptograafia haru tehnikatega.

"Oleksin arvanud, et iga algoritm, mis selle põhijoonega töötab, on hukule määratud," ütles Shor, praegu Massachusettsi Tehnoloogiainstituudi rakendusmatemaatik. "Aga ma eksisin."

Faktorite leidmine

Kvantarvutid saavad oma võimsuse omapärasest teabe töötlemise viisist. Klassikalised arvutid kasutavad bitte, millest igaüks peab alati olema ühes kahest olekust, tähisega 0 ja 1. Kvantbitid ehk "qubits" võivad lisaks olla 0 ja 1 olekute kombinatsioonis – seda nähtust nimetatakse superpositsiooniks. Samuti on võimalik meelitada mitut kubitti kollektiivsesse superpositsiooni olekusse: kahe kubiti superpositsioonil on neli komponenti, mis suudavad üheaegselt teha erinevaid arvutusi, ja selliste komponentide arv kasvab eksponentsiaalselt, kui kubitide arv suureneb. See võimaldab kvantarvutitel tõhusalt sooritada paralleelselt eksponentsiaalselt palju erinevaid arvutusi.

Kuid seal on konks: Superpositsioonis sooritatud arvutuse tulemuse lugemine näitab vastuse ainult ühe juhusliku komponendi poolt arvutatud osale. Superpositsioonis arvutamise eeliste kasutamiseks peate lõpptulemuse kuidagi kaardistama lihtsamasse olekusse, kus tulemust on ohutu lugeda. Enamikul juhtudel pole see võimalik ja alguses ei teadnud keegi, kuidas see ühegi probleemi puhul toimima panna. "Oli väga vähe inimesi, kellel oli isegi julgust kvantarvutuste peale mõelda," ütles Regev.

Siis 1994. aastal luges Shor paber arvutiteadlane Daniel Simon, mis näitas, kuidas kasutada kvantsuperpositsiooni väljamõeldud probleemi lahendamiseks. Shor mõtles välja, kuidas laiendada Simoni tulemust üldisemale ja praktilisemale probleemile, mida nimetatakse perioodi leidmiseks. Matemaatiline funktsioon on perioodiline, kui selle väljund tsüklib korduvalt samade väärtuste kaudu, kui sisend suureneb; ühe tsükli pikkust nimetatakse funktsiooni perioodiks.

Antud funktsiooni perioodi leidmiseks kvantarvuti abil alustage väga suure superpositsiooni seadistamisega, milles iga komponent arvutab funktsiooni väljundi erineva sisendi jaoks. Seejärel kasutage Shori meetodit selle suure superpositsiooni teisendamiseks lihtsamasse olekusse ja lugege tulemus. Sel hetkel saab klassikaline arvuti kiiresti arvutuse üle võtta ja lõpetada. Üldiselt töötab Shori perioodiotsingu algoritm eksponentsiaalselt kiiremini kui ükski klassikaline alternatiiv, kuna see arvutab superpositsiooni abil samaaegselt perioodilise funktsiooni erinevad väljundid.

Kui Shor otsis rakendusi oma kvantperioodi leidmise algoritmile, avastas ta uuesti varem tuntud, kuid ebaselge matemaatilise teoreemi: iga arvu jaoks on perioodiline funktsioon, mille perioodid on seotud arvu algteguritega. Nii et kui on mõni arv, mida soovite arvesse võtta, saate arvutada vastava funktsiooni ja seejärel lahendada probleemi perioodi leidmise abil - "milles kvantarvutid täpselt nii head on," ütles Regev.

Klassikalises arvutis oleks see piinavalt aeglane viis suure arvu arvessevõtmiseks – aeglasem isegi kui proovida kõiki võimalikke tegureid. Kuid Shori meetod kiirendab protsessi eksponentsiaalselt, muutes perioodi leidmise ideaalseks viisiks kiire kvantfaktoringu algoritmi koostamiseks.

Shori algoritm oli üks vähestest peamistest varajasetest tulemustest, mis muutis kvantarvutuse teoreetilise arvutiteaduse ebaselgest alamvaldkonnast praeguseks juggernautiks. Algoritmi rakendamine praktikas on aga hirmutav ülesanne, sest kvantarvutid on kurikuulsalt vastuvõtlikud vigadele: lisaks arvutuste tegemiseks vajalikele kubitidele vajavad nad ka paljusid teisi. lisatöö et nad ei ebaõnnestuks. A viimastel paber Ekerå ja Google'i uurija Craig Gidney prognoosib, et Shori algoritmi kasutamine turvastandardi 2,048-bitise arvu (umbes 600 numbrit pikk) faktoriks eeldaks 20 miljoni kubitiga kvantarvutit. Tänapäeva tipptasemel masinatel on kõige rohkem paarsada.

Sellepärast tuginevad mõned kriitilised Interneti-protokollid endiselt sellele, kui raske on suuri numbreid arvesse võtta, kuid teadlased ei taha liiga rahule jääda. Teoreetiline ja tehnoloogilised uuendused võivad nõutavat kubitite arvu veelgi vähendada ja pole tõendeid, et Shori algoritm on optimaalne – seal võib olla parem kvantfaktoringu algoritm, mida keegi pole avastanud.

Kui jah, ütles Regev: "Peaksime teadma võimalikult varakult, enne kui on liiga hilja."

Puude vahele kadunud

Regev alustas oma akadeemilist karjääri 1990. aastate lõpus, kui krüptograafid otsisid uut avaliku võtmega krüptograafia vormi, mis ei oleks Shori algoritmi suhtes haavatav. Kõige lootustandvam lähenemine, nn võrepõhine krüptograafia, tugineb suuremõõtmeliste punktide massiivide või võretega seotud arvutusprobleemide näilisele raskusele. Üks selline probleem on sarnane ülesandega leida metsa juhuslikule punktile lähim puu.

"Kui see on sajamõõtmeline mets, on see palju keerulisem kui kahemõõtmeline mets," ütles Greg Kuperberg, matemaatik California ülikoolist Davis.

Regev asus võrepõhist krüptograafiat õppima järeldoktori, algselt ründajana – ta tahtis uut lähenemist stressitestida, leides nõrkused, mida kvantarvuti saaks ära kasutada. Kuid ta ei suutnud edusamme teha ja ta mõtles peagi, kas sellel on sügavam põhjus. 2005. aastal leidis ta viisi, kuidas need ebaõnnestunud rünnakud a võrepõhise krüptograafia vorm parem kui kõik teised variandid.

"Oded on võredega täiesti geniaalne," ütles Kuperberg.

Aastate jooksul, kui Regev õpetas Shori algoritmi järjestikustele põlvkondadele õpilastele, leidis ta end mõtlemast, kas tema võrepõhise krüptograafia ründamiseks kasutatud tehnikad võivad faktooringualgoritmide puhul tegelikult kasulikuks osutuda. Selle põhjuseks on asjaolu, et üks samm Shori algoritmi viimases klassikalises etapis tähendab lähima punkti leidmist ühemõõtmelises võres. See ühemõõtmeline probleem on triviaalselt lihtne, kuid sarnasus analoogse probleemiga sadade mõõtmetega, mille kõvadus on võrepõhise krüptograafia aluseks, oli eksimatu.

"Kui olete keegi, kes teeb võre nagu mina, siis arvate:" OK, siin on mingi võre toimumas," ütles Regev. "Kuid mulle ei olnud selge, kuidas seda kasutada." Aastaid mängis ta teiste ideedega uute kvantfaktoringalgoritmide loomiseks, kuid ei jõudnud kunagi kuhugi. Seejärel pöördus ta eelmisel talvel tagasi probleemi juurde ja otsustas tuvastada ahvatleva seose faktooringu ja võrepõhise krüptograafia vahel. Seekord leidis ta edu.

Lisamõõtmed

Regev teadis, et ta peab alustama Shori algoritmi keskmes oleva perioodilise funktsiooni üldistamisest ühest dimensioonist mitmele mõõtmele. Shori algoritmis hõlmab see funktsioon juhusliku arvu korduvat korrutamist, mida dubleeritakse g, iseendaga. Kuid selle funktsiooni periood - kordade arv, millega peate korrutama g enne kui funktsiooni väljund hakkab korduma — võib olla väga suur ja see tähendab, et kvantarvuti peab perioodilise funktsiooni arvutamiseks kasutatava superpositsiooni mõnes komponendis korrutama suuri numbreid. Need suured korrutised on Shori algoritmi arvutuslikult kõige kulukam osa.

Analoogne kahemõõtmeline funktsioon kasutab selle asemel numbripaari, g₁ ja g₂. See hõlmab korrutamist g₁ iseendaga mitu korda ja seejärel korduvalt korrutades g₂. Selle funktsiooni periood on samuti kahemõõtmeline - see määratakse arvuga g₁ korrutised ja g₂ korrutused, mis koos panevad funktsiooni väljundi kordama. Seal on palju erinevaid kombinatsioone g₁ ja g₂ korrutused, mis ajavad asja ära.

Regev töötas läbi tehnilised üksikasjad, et üldistada algoritmi suvalise arvu dimensioonidega, mitte ainult kahega, kuid tema esialgsed tulemused ei olnud julgustavad. Perioodilise funktsiooni arvutamiseks paljudes mõõtmetes peaks kvantarvuti ikkagi palju numbreid omavahel korrutama. Iga numbrit ei pea korrutama nii mitu korda kui ühemõõtmelisel juhul, kuid korrutamiseks oli rohkem erinevaid arve. Kogu asi tundus olevat pesu.

"Arvate:" Suurepärane, ma tegin kõike lihtsalt suurtes mõõtmetes ja see on täpselt sama jooksuaeg kui Shoril," ütles Regev. "Olin sellega mõnda aega ummikus." Siis mõistis ta, et saab probleemist mööda minna, muutes korrutamise järjekorda. Selle asemel, et lisada korduvalt numbreid ühele tootele, mis kvantarvutuse käigus järk-järgult suureneks, alustas ta väikeste arvude paaridega, korrutas saadud korrutised kokku ja liikus ülespoole. Korrutuste koguarv palju ei muutunud, kuid nüüd on peaaegu kõigis suhteliselt väikesed arvud, mis teeb arvutamise kiiremaks.

"See muudab kogu maailma," ütles Vinod Vaikuntanathan, krüptograaf MIT-is.

Alguses tundus, et Regev oli just ühe probleemi teisega asendanud. Ta oli kiirendanud perioodilise funktsiooni kvantarvutamist, suurendades mõõtmete arvu, kuid järgnev klassikaline arvutus, mis oli vajalik perioodi eraldamiseks, sarnanes nüüd lähima võrepunkti leidmisega suuremõõtmelises ruumis – laialt arvatakse, et see on ülesanne. ole raske. Tema uut lähenemist motiveerinud analoogia võrepõhise krüptograafiaga näis määravat selle läbikukkumisele.

Ühel külmal märtsikuu hommikul enne reisi Princetoni ülikooli seminarile avastas Regev end ootamas kolleegi, kellega ta koos ühissõidukiga sõitis. "Ma jõudsin varakult kohale ja ta hilines autole järele," ütles ta. Sel ajal, kui ta istus ja ootas, tuli ootamatult tema juurde viimane pusletükk. "See on hetk, mil asjad loksusid paika, kuid see küpsetas mõnda aega."

Kõik taandus õige arvu mõõtmeteni. Kui võre mõõde oli liiga madal, ei saanud tema algoritm väiksemate arvude korrutamisest tulenevat kiirust täielikult ära kasutada. Kui see oli liiga kõrge, oli kvantarvutus kiire, kuid klassikaline osa nõudis liiga raske võreülesande lahendamist. Regev teadis algusest peale, et edu loomiseks peab ta kuskil vahepeal tööd tegema, kuid polnud selge, kas magus koht on olemas. Sel märtsi hommikul mõistis ta, kuidas saab algoritmi üksikasju muuta, et see mõnekümnes mõõtmes kiiresti töötaks.

Liivas kirjutamine

Paranemine oli sügav. Elementaarsete loogiliste sammude arv Regevi algoritmi kvantosas on võrdeline n^1.5 kui faktooring an n-biti number, mitte n² nagu Shori algoritmis. Algoritm kordab seda kvantosa paarkümmend korda ja kombineerib tulemused, et kaardistada kõrgdimensiooniline võre, millest saab tuletada perioodi ja arvutada arvu. Nii et algoritm tervikuna ei pruugi kiiremini töötada, kuid kvantosa kiirendamine vajalike sammude arvu vähendamise kaudu võib selle elluviimise lihtsamaks muuta.

Muidugi on kvantalgoritmi käitamiseks kuluv aeg vaid üks paljudest kaalutlustest. Sama oluline on ka vajalike kubitide arv, mis on analoogne tavalise klassikalise arvutuse ajal vaheväärtuste salvestamiseks vajaliku mäluga. Kvobitide arv, mida Shori algoritm nõuab an faktoriks n-biti arv on võrdeline n, samas kui Regevi algoritm algsel kujul nõuab kubitide arvu, mis on proportsionaalsed n^1.5 — suur erinevus 2,048-bitiste numbrite puhul.

Klassikalises andmetöötluses on kiirus tavaliselt olulisem kui mälu, sest klassikalised bitid on äärmiselt vastupidavad: saate faili arvutisse salvestada ja mitte muretseda selle pärast, et see hiljem uuesti avades muutub juhuslikult. Kvantarvutite uurijatel pole alati nii vedanud.

"Meie kubiidid üritavad pidevalt laguneda ja me püüame takistada nende lagunemist," ütles Gidney. "See on nii, nagu prooviksite liivale kirjutada ja tuul puhub selle minema." See tähendab, et Regevi algoritmi nõutavad lisakubitid võivad olla suureks puuduseks.

Kuid Regevi paber ei ole loo lõpp. Kaks nädalat tagasi leidsid Vaikuntanathan ja tema kraadiõppur Seyoon Ragavan viisi, kuidas algoritmi mälukasutust vähendada. Nende variant Regevi algoritm, nagu ka Shori algne algoritm, nõuab mitmeid kubitte, mis on võrdelised n mitte n^1.5. Ekerå kirjutas meilis, et töö "viib meid palju lähemale rakendamisele, mis oleks praktikas tõhusam."

Regevi uue algoritmi laiem õppetund lisaks faktooringule on see, et kvantarvutusteadlased peaksid alati olema üllatustele avatud, isegi aastakümneid uuritud probleemide korral.

"Seda minu algoritmi varianti ei leitud 30 aastat ja see tuli täiesti ootamatult," ütles Shor. "Tõenäoliselt on veel palju muid kvantalgoritme leida."

Toimetaja märkus: Oded Regev saab rahalisi vahendeid Simons Foundation, mis rahastab ka seda toimetuslikult sõltumatut ajakirja. Simonsi fondi rahastamisotsused ei mõjuta meie katvust. Täpsemad üksikasjad on saadaval siin.

Quanta viib läbi mitmeid küsitlusi, et meie vaatajaskonda paremini teenindada. Võtke meie informaatika lugejaküsitlus ja teid osaletakse tasuta võitmiseks Quanta kaup.