Oglas
Kvantno računanje jedna je od onih tehnologija koje su toliko skrivene da TV znakovi ispadaju kad žele zvučati pametno.
Kvantno računanje kao ideja postoji već neko vrijeme - teorijsku mogućnost izvorno su uveli Yuri Manin i Richard Feynman 1982. godine. Zadnjih nekoliko godina, međutim, polje se zabrinjava što bliže praktičnosti.
Tvrtke poput Googlea i Microsofta, kao i vladine agencije poput NSA, već godinama grozničavo provode kvantna računala. Tvrtka pod nazivom D-Wave proizvela je i prodaje uređaje koji (iako nisu odgovarajuće računalo, mogu izvode samo nekoliko algoritama) koriste kvantna svojstva i još su jedan korak koji je više koraka na putu prema potpuno Turing-potpun Što je Turingov test i hoće li ga ikada pobijediti?Turingov test ima za cilj da odredi misle li strojevi. Je li program Eugene Goostman doista prošao Turingov test ili su ga autori jednostavno prevarili? Čitaj više kvantni stroj.
Ne čini se nerazumnim reći da bi moglo doći do proboja koji će omogućiti izgradnju velikog kvantnog računala u roku od deset godina.
Pa zašto svi interesi? Zašto bi se trebao brinuti? Računala postaju brža cijelo vrijeme Što je Mooreov zakon i kakve to veze ima s vama? [MakeUseOf objašnjava]Loša sreća nema nikakve veze s Mooreovim zakonom. Ako je to udruga koju ste imali, to miješate s Murphyjevim zakonom. Međutim, niste bili daleko jer Mooreov zakon i Murphyjev zakon ... Čitaj više - što je tako posebno u kvantnim računalima?
Da bismo objasnili zašto su ovi strojevi toliko važni, morat ćemo napraviti korak unatrag i istražiti što su točno kvantna računala i zašto rade. Za početak, razgovarajmo o konceptu koji se naziva "složenost vremena izvođenja".
Što je složenost vremena izvođenja?
Jedno od velikih iznenađenja u ranim danima informatike bilo je otkriće da, ako imate računalo koje rješava problem određena veličina u određenom vremenu, udvostručenje brzine računala, ne mora nužno i dva puta rješavati probleme velik.
Neki se algoritmi povećavaju u ukupnom vremenu izvršenja vrlo, vrlo brzo, kako veličina problema raste - neki se algoritmi mogu brzo dovršiti danih 100 podatkovnih točaka, ali za kompletiranje algoritma s 1000 podatkovnih točaka potrebno je računalo veličine Zemlje koja radi na milijardu godine. Složenost izvođenja formalizacija je ove ideje: ona gleda krivulju brzine rasta složenosti problema i koristi oblik te krivulje za razvrstavanje algoritma.
Te su klase teškoće uglavnom izražene kao funkcije. Algoritam koji postaje proporcionalno teži kada se skup podataka koji radi na njemu povećava (poput jednostavne funkcije brojanja) kaže se da je funkcija sa složenošću izvođenja "n” (kao u, potrebno je n jedinice vremena za obradu n podatkovne točke).
Alternativno, to bi se moglo nazvati "linearnim", jer kad ga nacrtate dobijete ravnu crtu. Mogle bi biti i druge funkcije n ^ 2 ili 2 ^ n ili n! (n faktografski). To su polinomni i eksponencijalni. U posljednja dva slučaja eksponencijalni rastu toliko brzo da se gotovo u svim slučajevima ne mogu riješiti ništa osim vrlo trivijalnih primjera.
Složenost izvođenja i kriptografija
Ako ove stvari čujete prvi put, a zvuče besmisleno i suzdržljivo, pokušajmo savladati ovu raspravu. Složenost izvođenja ključna je za kriptografiju koja se oslanja na to da bi dešifriranje bilo mnogo lakše za ljude koji znaju tajni ključ nego za one koji to nemaju. U idealnoj kriptografskoj shemi dešifriranje bi trebalo biti linearno ako imate ključ i 2 ^ k (gdje je k broj bita u ključu) ako nemate.
Drugim riječima, najbolji algoritam za dešifriranje poruke bez ključa trebao bi biti jednostavno nagađanje mogućih tipki, što je za ključeve neizrecivo samo nekoliko stotina bita.
Za kriptografiju simetrične ključeve (u kojoj dvije strane imaju priliku sigurno razmijeniti tajnu prije nego što započnu komunikaciju) to je prilično jednostavno. Za asimetričnu kriptografiju je teže.
Asimetrična kriptografija u kojoj se ključevi za enkripciju i dešifriranje razlikuju i ne mogu ih se lako izračunati jedan od drugog, mnogo je teža matematička strukturu implementirati od simetrične kriptografije, ali također je i snažnija: asimetrična kriptovaluta omogućava vam privatne razgovore čak i preko prisluškivanja linije! Omogućuje vam i stvaranje „digitalnih potpisa“ koji će vam omogućiti da provjerite od koga je poruka došla i da je nije u nju dirao.
Ovo su snažni alati i čine osnovu moderne privatnosti: bez asimetrične kriptografije korisnici elektroničkih uređaja ne bi imali pouzdanu zaštitu od znatiželjnih očiju.
Budući da je asimetričnu kriptografiju teže izraditi od simetrične, standardni načini šifriranja koji se danas koriste nisu tako snažni kao što bi mogli biti: najčešći standard šifriranja, RSA, može se probiti ako efikasno možete pronaći glavne faktore vrlo velike broj. Dobra vijest je da je to vrlo težak problem.
Najpoznatiji algoritam za razvrstavanje velikog broja u njihove sastavne baze naziva se sito s općim brojem polja i ima složenost izvođenja koja raste malo sporije od 2 ^ n. Kao posljedica toga, ključevi moraju biti desetak puta duži kako bi pružili sličnu sigurnost, što ljudi obično toleriraju kao troškove poslovanja. Loša vijest je da se cijeli igrački položaj mijenja kada kvantna računala budu bačena u miks.
Kvantna računala: Promjena kripto-igre
Kvantna računala djeluju jer mogu imati više unutrašnjih stanja istovremeno, kroz kvantni fenomen nazvan "superpozicija". To znači da mogu istovremeno napadati različite dijelove problema i podijeliti se na moguće verzije svemira. Mogu se konfigurirati i tako da grane koje rješavaju problem završavaju sa najvećom amplitudom, tako da kad otvorite okvir na Schrodingerova mačka, verzija internog stanja s kojom ćete se najviše predstavljati je samozadovoljna mačka koja drži dešifrirano poruka.
Više informacija o kvantnim računalima potražite u naš nedavni članak na tu temu Kako djeluju optička i kvantna računala?Dolazi Exascale Age. Znate li kako djeluju optička i kvantna računala i hoće li ove nove tehnologije postati naša budućnost? Čitaj više !
Zaključak ovoga je da kvantna računala nisu samo linearno brža, kao što je to normalno: dobivanje dva ili deset ili stotinu puta brže ne pomaže puno kada je riječ o konvencionalnoj kriptografiji koju ste stotine milijardi puta prespori za obradu. Kvantna računala podržavaju algoritme koji imaju sve veće složenosti vremena pokretanja nego što je to inače moguće. To je ono što kvantna računala bitno razlikuje od ostalih budućih računalnih tehnologija, poput računanje grafena i memristera Najnovija računalna tehnologija u koju morate vjerovatiPogledajte neke od najnovijih računalnih tehnologija koje su postavljene da transformišu svijet elektronike i osobnih računala u sljedećih nekoliko godina. Čitaj više .
Konkretan primjer, Shor-ov algoritam, koji se može izvesti samo na kvantnom računalu, može faktoriti velike brojeve u zapisnik (n) ^ 3 vrijeme, što je drastično bolje od najboljeg klasičnog napada. Korištenjem općeg sita s brojevima za faktore broj s 2048 bita potrebno je otprilike 10 ^ 41 jedinica vremena, što je više od trilijuna bilijuna biliona. Korištenjem Shor's algoritma, isti problem traje samo oko 1000 jedinica vremena.
Učinak postaje izraženiji što su dulje tipke. To je snaga kvantnih računala.
Nemojte me krivo shvatiti - kvantna računala imaju puno potencijalnih ne-zlih namjena. Kvantna računala mogu učinkovito riješiti problem putničkog prodavača, omogućujući istraživačima izgradnju učinkovitijih brodskih mreža i oblikovanje boljih krugova. Kvantna računala već imaju snažne koristi u umjetnoj inteligenciji.
To bi moglo reći da će njihova uloga u kriptografiji biti katastrofalna. Tehnologije šifriranja koje našem svijetu omogućuju da funkcionira ovise o problemu cijelog faktorizacije koji je teško riješiti. RSA i povezani programi šifriranja ono što vam omogućuju povjerenje da ste na pravom web mjestu, a to su datoteke koje vi preuzimanje nije prepuno zlonamjernog softvera i ljudi ne špijuniraju vaše internetsko pregledavanje (ako upotrebljavate Tor).
Kriptografija čuva vaš bankovni račun i osigurava svjetsku nuklearnu infrastrukturu. Kad kvantna računala postanu praktična, sva ta tehnologija prestaje raditi. Prva organizacija koja je razvila kvantno računalo, ako svijet i dalje radi na tehnologijama koje danas koristimo, bit će u zastrašujuće moćnom položaju.
Dakle, je li kvantna apokalipsa neizbježna? Možemo li učiniti nešto u vezi s tim? Kako se ispostavilo... da.
Postkvantna kriptografija
Postoji nekoliko klasa algoritama za enkripciju koje, koliko znamo, nisu značajno brže riješiti na kvantnom računalu. Oni su zajednički poznati kao postkvantna kriptografija i pružaju neku nadu da svijet može prijeći na kriptosustave koji će ostati siguran u svijetu kvantne enkripcije.
Obećavajući kandidati uključuju šifriranje zasnovano na rešetki, poput Ring-Learning With Error, koje svoju sigurnost crpi iz demonstrirano složenih problem strojnog učenja i multivarijantna kriptografija koja svoju sigurnost crpi iz poteškoće rješavanja vrlo velikih sustava jednostavnih jednadžbe. Više o ovoj temi možete pročitati na Članak Wikipedia. Pazite: mnogo je stvari složeno, a možda ćete otkriti da je matematička pozadina potrebno znatno poboljšati, prije nego što se stvarno možete pozabaviti detaljima.
Mnogo toga je činjenica da su postkvantni kriptoshemi vrlo cool, ali i vrlo mladi. Potrebno im je više rada da bi bili učinkoviti i praktični, a također i da pokažu da su sigurni. Razlog zbog kojeg možemo vjerovati kriptosistemima je taj što smo dovoljno dugo klinički paranoične genije bacali na njih da su do sada otkriveni bilo kakvi očigledni nedostaci, a istraživači su dokazali različite karakteristike koje ih čine jaka.
Suvremena kriptografija ovisi o svjetlosti kao dezinficijensu, a većina postkvantnih kriptografskih shema jednostavno je previše nova da bi se mogli pouzdati u svjetsku sigurnost. Dolaze, ipak, i uz malo sreće i malo pripreme, sigurnosni stručnjaci mogu dovršiti prelazak prije nego što se prvo kvantno računalo ikad pojavi na mreži.
Ako ipak ne uspiju, posljedice mogu biti teške. Pomisao na svakoga tko ima takvu silu uznemiruje, čak i ako ste optimistični u njihovim namjerama. Pitanje tko prvi razvija radno kvantno računalo postavlja pitanje koje bi svi trebali pomno promatrati dok krećemo u sljedeće desetljeće.
Zabrinuti ste zbog nesigurnosti kriptografije na kvantnim računalima? Što ti misliš? Podijelite svoje misli u komentarima ispod!
Slikovni krediti: Binarna kugla Via Shutterstock
Pisac i novinar sa sjedišta na jugozapadu, Andre je zajamčeno da će ostati funkcionalan do 50 Celzijevih stupnjeva, a vodootporan je do dubine od dvanaest metara.