TEMA BROJA

Vladimir Božin

Kvantni računari / Tajne ključeva za dešifrovanje

Nerazjašnjeno dejstvo na daljinu

U jesen 2023. godine, nekoliko kompanija objavilo je da su napravili kvantne računare sa preko 1000 kubita, što se može shvatiti kao prelomna tačka u ovoj oblasti. Najpre Atom Computing, a potom i IBM oborili su ovaj rekord, a pažnja masovnih medija bila je ove jeseni ponovo fokusirana na ovu potencijalno revolucionarnu oblast, od strateške važnosti u međunarodnoj trci za nadmoć u informacionim tehnologijama.
S druge strane, Skot Aaronson, jedan od vodećih eksperata u ovoj oblasti, koji već dugi niz godina vodi popularni blog na ovu temu, bio je vidljivo suzdržan, i napisao je da će, na srednje staze, veštačka inteligencija igrati daleko veću ulogu od kvantnih računara.

Ričard Fejnman, nobelovac i ikona američke fizike dvadesetog veka, jednom prilikom je u svom maniru izjavio da niko ne razume kvantnu mehaniku. Njegov rad iz 1982. godine, "Simuliranje fizike kompjuterima" ukazao je na naizgled fundamentalnu nemogućnost da se kvantna mehanika efikasno simulira na klasičnim računarima. Britanski fizičar Dejvid Dojč je 1985. godine formalizovao pojam kvantnog računara. Međutim, oblast je dobila krila tek sa spektakularnim rezultatom Pitera Šora iz 1994. godine, kojim je pokazao da je na kvantnom računaru moguće efikasno faktorisati prirodne brojeve, u broju koraka koji raste kao treći stepen broja cifara broja - drastično efikasnije nego što to radi najbolji poznati klasični algoritam. Šor je za ovo svoje otkriće obasut najvišim priznanjima, uključujući i najprestižniju Nevalininu nagradu, na Svetskom kongresu matematičara 1998. godine. Ovaj teorijski rezultat je pokrenuo čitavu oblast, i velika tehnološka ulaganja kako bi se kvantni računari i napravili. Usko povezane kvantne informacione tehnologije, kvantna kriptografija i kvantne komunikacije su počele intenzivno da se razvijaju, a prošle godine je značaj ove oblasti krunisan i Nobelovom nagradom koju su dobili Alen Aspe, Anton Cajlinger i Džon Klauzer za fundamentalna istraživanja u kvantoj mehanici, specijalno u vezi fenomena kvantne upletenosti. Istraživačka grupa Antona Cajlingera, iz Beča, sarađivala je blisko i sa Beogradskom školom kvantne mehanike, koju je, sa velikom inspiracijom, vodio nedavno preminuli akademik Fedor Herbut.

Šorov i Groverov algoritam

Razlog zbog kojeg je rezultat Pitera Šora izazvao toliku pažnju je u tome što se na nemogućnosti da se veliki prirodni brojevi faktorišu zasniva sigurnost mnogih kriptografskih sistema koji se koriste u praksi - kartice za plaćanje i sigurni internet koriste takozvani RSA algoritam za kriptografiju sa javnim ključem. U ovom sitemu, poruke se razmenjuju izmedju strana u šifrovanom obliku. Na primer, korisnik internet, lokalno na svom računaru, generiše par ključeva: tajni, za dešifrovanje, koji je samo njemu poznat, i javni, koji šalje kako bi se pomoću njega poruka šifrovala. Šifrovanje i dešifrovanje se svode na izračunavanje ostatka stepena broja, koji predstavlja poruku, pri deljenju sa nekim fiksiranim velikim brojem. U ovom sistemu se taj fiksirani broj uzima da je proizvod dva prosta broja. Dešifrovanje se vrši na isti način - stepenovanjem šifrovane poruke po tom fiksiranom modulu. Stepeni koji se koriste za šifrovanje i dešifrovanje su zapravo javni i tajni ključ. Problem je u tome što, ukoliko neko zna koja dva prosta broja se koriste za fiksiranu osnovu sistema, onda može lako na osnovu javnog ključa da dobije tajni ključ. Međutim, obzirom da nije poznat efikasan klasični algoritam koji faktoriše prirodne brojeve, ovo se smatra sigurnim. Ukoliko bismo imali kvantni računar, ovaj sistem bi prestao da bude bezbedan. I u nekim drugim oblastima, posedovanje kvantnih računara dalo bi veliku prednost - recimo, transakcije bitkoin kriptovalute prestaju da budu sigurne posle jednog korišćenja uz kvantne računare, što se takođe zasniva na Šorovom otkriću u nešto drugačijoj varijaciji (traženje perioda funkcije). Šorov algoritam zasniva se na zapravo jednostavnom zapažanju da je moguće izvršiti diskretnu Furijeovu transformaciju vrlo jednostavno i efikasno na kvantnom računaru, čime se mogu nalaziti periodi funkcija.

Još jedan bitan algoritam iz 90-tih godina prošlog veka je značajan. To je Groverov algoritam za kvantnu pretragu. Njime je moguće broj provera pri traženju rešenja nekog, proizvoljnog, problema redukovati na koren broja mogućnosti koje se razmatraju. Recimo, blokčejn tehnologija kriptovaluta zasniva se na distribuiranoj validaciji novčanih transakcija. Ovo se realizuje tako što je za validaciju transakcije potrebno rešiti izvestan matematički problem, ali za rešavanje tog problema nema boljeg načina nego da se isprobaju sve moguće opcije, što blokčejn validaciju pretvara u neku vrstu lutrije. Bitkoin rudari, kako se nazivaju oni koji vrše validacije, dobijaju znatnu nadoknadu ukoliko pogode rešenje. Kvantni računar bi broj mogućnosti koje treba isprobati drastično redukovao - sa stotina milijardi milijardi, koliko je "težina" problema, odnosno broj mogućnosti, na koren iz toga, na desetine milijardi puta manje.
Međutim, sem ova dva problema i simuliranja kvantnih sistema, zasad nije pronađen nijedan bitan suštinski novi problem koji bi kvantne računare činio drastično efikasnijim od klasičnih. Fizička realizacija bar nekog od algoritama koji je mnogo efikasniji za konkretan problem od klasičnog naziva se postizanjem "kvantne nadmoći", iako je bilo nekoliko najava da je to postignuto u poslednjih par godina, zasad ne deluje previše ubedljivo. Realizacija kvantnih računara u praksi je izuzetno teška i, uprkos nedavnom napretku, praktična primena algoritama poput Šorovog decenijama je daleko. Pa ipak, kriptografija igra vrlo široku ulogu u modernom društvu. Zbog toga su razvijani kriptografski sistemi koji su sigurni i za kvantne računare, zasnovani na pomenutom fenomenu kvantne upletenosti.

“Kvantna nadmoć”

Kvantni računari koriste na fundamentalan način osobine kvantne mehanike. Jedinica kvantne informacije je kubit, koju predstavlja neki sistem sa dva moguća kvantna stanja, poput spina elektrona ili polarizacije fotona. Kvantno stanje kubita opisuje se vektorom u dvodimenzionalnom prostoru dva osnovna stanja, sa dva parametra, dve koordinate koje su kompleksni brojevi. Ukoliko imamo sistem koji ima n kubita, broj parametara koji su potrebni za opisivanje ovog sistema je 2 na stepen n, što raste eksponencijalno i već za 100 kubita ima toliko parametara da se oni ne mogu zapamtiti ni u jednoj memoriji superkompjutera. Kvantni računar radi tako što se na odabranom podskupu od dva ili tri kubita primenjuje neka kvantna operacija, koja može biti proizvoljna. Matematički, ova operacija se prikazuje određenom dva sa dva ili tri sa tri matricom (za operacije na dva odnosno tri odabrana kubita). Posle niza ovakvih operacija, vrši se merenje. Rezultat je jedno klasično stanje koje možemo shvatiti kao niz od n klasičnih bitova. Verovatnoća da se dobije određeni rezultat merenja je jednaka kvadratu apsolutne vrednosti parametra koji odgovara tom nizu bitova. U izvesnom smislu, kvantni računar radi paralelno sa svim mogućim stanjima klasične memorije od n klasičnih bitova. Međutim, iako je moguće raditi paralelno sa svim stanjima memorije, rezultat koji na kraju dobijemo, da bi bio koristan u praksi, mora imati dovoljno veliku verovatnoću da se realizuje merenjem, što znači da je potrebno na vešt način interferisati različite tokove izračunavanja, zbog čega je ova osobina kvantnih računara iskorišćena za projektovanje tek nekoliko upotrebljivih algoritama gde bi došla do izražaja "kvantna nadmoć".
Glavni problem u realizaciji kvantnih računara je u tome, što kvantni sistemi interaguju sa okolnom, čime se narušava kvantno stanje i remeti rad kvantnog računara, tako da postaje neupotrebljiv posle određenog broja koraka. Ovo se naziva kvantnom dekoherencijom, a stanje kvantnog sistema koje se opisuje na gorepomenuti način, sa 2 na n parametara naziva se koherentnim stanjem. Takvo stanje nije upleteno ili spregnuto sa stanjem okoline, što je veoma teško postići i održati. Zbog toga je jedan od načina na koji se kvantni računari realizuju - da se koriste vrlo niske temperature. Kvantni računar kojeg je napravio Google je jedna ogromna skalamerija za hlađenje, kao podrška sistemu na kome se vrše izračunavanja. Ovo bitno ograničava kvantne računare, a najbolje postignuti rezultat za faktorisanje Šorovim algoritmom je faktorisanje dvocifrenih brojeva, i to uz matematičku pripremu na klasičnom računaru. Ni realizovanih 1000 kubita koji su se pojavili ove jeseni nisu zapravo to - jedan deo kubita koristi se za podršku ostalima, kako bi bilo moguće izvršiti veći broj koraka kvantnog računa. A broj tih koraka je takođe zasad vrlo skroman, tek par stotina.

Misteriozni prirodni fenomen

Kako bi se rešio problem kvantne dekoherencije i kvantni računari postali upotrebljivi za praktične probleme, koristi se kvantna korekcija greške. Korišćenjem većeg broja kubita, mogu se korigovati šumovi usled interakcija sa okolinom. Međutim, još nije dosegnut prag gde bi broj koraka računa postao praktično neograničen. Pa ipak, treba konstatovati da je postignut veliki napredak u realizaciji kvantnih računara - krajem devedesetih godina, kada se sa ovom oblašću počelo, bilo je moguće raditi sa samo nekoliko kubita, a sada je taj broj premašio hiljadu.
U osnovi čitave ove oblasti, leži fenomen kvantne upletenosti. Kvantna upletenost je fundamentalna i misteriozna osobina kvantne mehanike. Klasičan sistem ima osobinu da je broj parametara koji su neophodni da se sistem opiše proporcionalan broju delova sistema. Kod kvantnog sistema ovaj broj parametara raste eksponencijalno sa brojem delova sistema. Ovo je usko povezano sa fenomenom kvantne nelokalnosti. Stanje sistema opisano je ne samo lokalnim osobinama sistema već i svim mogućim korelacijama između različitih delova sistema. Poznata je skepsa koju je Albert Ajnštajn imao prema kvantnoj mehanici, a on je kvantnu nelokalnost nazivao misterioznim dejstvom na daljinu. U poznatom radu iz 1935. godine, Ajnštajn, Podolski i Rozen razmatrali su kvantnu upletenost i predložili misaoni eksperiment, poznat po inicijalima autora kao EPR, u kome se generiše par upletenih fotona koji nastaju anihilacijom para čestica-antičestica, i koji imaju korelisane vrednosti polarizacija. Iako je vrednost koja se dobija merenjem polarizacije slučajna, vrednost merena na jednom fotonu savršeno odgovara vrednosti koja se meri na drugom. Obzirom da informacija ne može putovati brzinom većom od brzine svetlosti, kako onda drugi foton "zna" koji je rezultat merenja bio na prvom fotonu?
Mogućnost da foton ima neku određenu vrednost koja određuje rezultat mogućih merenja i koju nosi sa sobom, što bi odgovaralo takozvanoj lokalnoj teoriji skrivenih varijabli, je isključena Belovim nejednakostima, tako da su korelacije na daljinu misteriozni prirodni fenomen. One ne omogućavaju prenošenje informacija brzinom većom od brzine svetlosti, ali ipak se kose sa intuicijom. Kasnije su ovi fenomeni sa parom čestica i eksperimentalno potvrđeni. Leonard Saskind, teorijski fizičar sa Stenforda, poznat kao "nevaljali dečko teorijske fizike" zbog svojih smelih i često divljih ideja, koje su se ne jednom pokazale kao ispravne, sugerisao je čak da postoji veza između EPR parova čestica i fenomena kao što su gravitacione crvotočine ili tuneli koji spajaju udaljene delove prostora. Na fenomenu kvantne upletenosti zasniva se oblast kvantnih komunikacija i kvantne kriptografije, koja ima potencijal da bude korisna u praksi mnogo pre nego što budu rešeni praktični problemi sa kvantnim računarima.
Iako su obećanja kvantnih računara ogromna, a napredak u poslednjim godinama veliki, čini se da će proći još neko vreme dok oni ne postanu značajan faktor i u praksi. Godina 2024. predstavlja tridesetogodišnji jubilej od otkrića Šorovog algoritma; a ako je nečemu doprineo intenzivni razvoj oblasti kvantnih informacija, onda je to detaljno bavljenje fundamentalnim aspektima kvantne mehanike - teorije, koja je u osnovi našeg shvatanja fizičkog sveta, teorije koja nema opšteprihvaćenu interpretaciju, ispletene velom misterije, sa puno iznenađenja i uzbudljivog potencijala, a koju, kako je to Ričard Fejnman rekao, niko zapravo ne razume.

Vladimir Božin

Kompletni tekstove sa slikama i prilozima potražite u magazinu
"PLANETA" - štampano izdanje ili u ON LINE prodaji Elektronskog izdanja
"Novinarnica"