Put prema kvantnom računalu koje razbija sve šifre

Najnovija e-pošta koju ste poslali vjerojatno je šifrirana isprobanom metodom koja se oslanja na ideju da čak ni najbrže računalo ne bi moglo učinkovito rastaviti ogroman broj na faktore.

Kvantna računala, s druge strane, obećavaju da će brzo razbiti složene kriptografske sustave koje klasično računalo možda nikada neće moći razotkriti. Ovo obećanje temelji se na kvantnom algoritmu faktoringa koji je 1994. predložio Peter Shor, koji je sada profesor na MIT-u.

No dok su istraživači poduzeli velike korake u posljednjih 30 godina, znanstvenici tek trebaju izgraditi kvantno računalo dovoljno snažno da pokrene Shorov algoritam.

Dok neki istraživači rade na izgradnji većih kvantnih računala, drugi pokušavaju poboljšati Shorov algoritam kako bi mogao raditi na manjem kvantnom krugu. Prije otprilike godinu dana, računalni znanstvenik Oded Regev sa Sveučilišta New York predložio je  veliko teorijsko poboljšanje. Njegov algoritam mogao bi raditi brže, ali bi sklop zahtijevao više memorije.

Nadovezujući se na te rezultate, istraživači MIT-a predložili su pristup koji je najbolji od oba svijeta i koji kombinira brzinu Regevovog algoritma s memorijskom učinkovitošću Shorova. Ovaj novi algoritam brz je kao Regevov, zahtijeva manje kvantnih građevnih blokova poznatih kao kubiti i ima veću toleranciju na kvantni šum, što bi ga moglo učiniti izvedivijim za implementaciju u praksi.

Dugoročno gledano, ovaj bi novi algoritam mogao utjecati na razvoj novih metoda šifriranja koje mogu izdržati moć razbijanja koda kvantnih računala.

Kvantni krug koji je Shor predložio ima veličinu proporcionalnu kvadratu broja koji se faktorizira. To znači da ako se faktorira 2048-bitni cijeli broj, krug bi trebao milijune vrata (gates).

Regevov sklop zahtijeva značajno manje kvantnih vrata, ali treba mnogo više kubita da osigura dovoljno memorije. Ovo predstavlja novi problem.

Istraživači s MIT-a pronašli su pametan način za izračunavanje eksponenata pomoću niza Fibonaccijevih brojeva koji zahtijeva jednostavno množenje, koje je reverzibilno, umjesto kvadriranja. Njihova metoda treba samo dvije kvantne memorijske jedinice za izračunavanje bilo kojeg eksponenta.

Također su se uhvatili u koštac s izazovom ispravljanja pogrešaka. Krugovi koje su predložili Shor i Regev zahtijevaju da svaka kvantna operacija bude ispravna kako bi njihov algoritam radio, kaže Vaikuntanathan. Ali kvantna vrata bez grešaka bila bi neizvediva na stvarnom stroju.

Prevladali su ovaj problem koristeći tehniku ​​za filtriranje pokvarenih rezultata i obradu samo onih pravih, a krajnji rezultat je sklop koji je značajno memorijski učinkovitiji. Osim toga, njihova bi tehnika ispravljanja pogrešaka učinila algoritam praktičnijim za primjenu.

Rad znanstvenika MIT-a možete pronaći na ovoj poveznici.