Kako radi kvantno računalo i zašto je toliko mahnito brže? (Hint - jer je lukavo!)

Obećava se nova velika revolucija u računalstvu. Riječ je o tzv kvantnim računalima, koje usavršavaju najveće tvrtke, i najveće države a IBM je svoje računalo čak otvorio korisnicima. U ovom vam članku pokušavamo objasniti o čemu je riječ, pri čemu će laicima okvir pri početku članka pomoći da steknu predodžbu kako kvantna računala rješavaju problem brute force (to jest da računalo ispituje svaku mogućnost pojedinačno) a oni već donekle upućeni u nastavku će se članka moći informirati o pojedinostima o kojima dosad nisu vodili računa

Kvantno računalo, poput ovog na slici, za izvođenje računa koristi kvantno-mehaničke fenomene kao što su superpozicija stanja i kvantna spregnutost.

U posljednjih godinu dana, svjedočimo nevjerojatnoj selidbi kvantnih računala iz relativno uske domene znanosti prema domeni široke upotrebe. Putem svog Quantum experience projekta, IBM bilo kome tko ima pristup internetu nudi mogućnost programiranja na kvantnim računalima. S druge strane, znanstvenici iz Googlea obećavaju komercijalno dostupna kvantna računala unutar pet godina, a svog kvantnog konja za utrku pripremaju i Microsoft i Intel. U utrci za što veće kvantno računalo ne zaostaju ni Rusi – na nedavnoj konferenciji o kvantnim tehnologijama znanstvenici iz RQC-a (Ruskog kvantnog centra) predstavili su koncept računala s 51 qubitom (kvantnim bitom), čime su oteli krunu Googleovom 49-qubitnom računalu.

O kvantnim računalima s oprezom pišu stručnjaci za internetsku sigurnost, dok ih kemičari, meteorolozi, robotičari i matematičari željno iščekuju. U rješavanju nekih problema, kvantna računala obećavaju dramatična ubrzanja. Kupuju u NSA-u, Airbusu, AT&T-u, Lockheed Martinu, HP-u, Mitsubishiju, Toshibi… O čemu se radi?

Najkraće rečeno, kvantna računala za su računala koja za rješavanje problema koriste kvantno‑mehaničke fenomene – konkretno, superpoziciju stanja i kvantno sprezanje. Pokušat ćemo ih podrobnije upoznati kroz tri teme:

Što su (konceptualno) qubiti i kako funkcioniraju?
Što kvantna računala mogu, a što ne mogu?
Kako izgledaju današnja kvantna računala? Koja je fizička izvedba qubita? Hoće li u budućnosti sva računala biti kvantna? (Neće.) Kada dolazi kvantni iPhone? (Ne dolazi.)

Prvom ćemo se temom baviti u ovom članku, a ostalima u njegovom nastavku.

PRIMJER ZA LAIKE

Zamislite na trenutak da radite u skladištu u kojem se nalaze tisuće jednakih kutija. Sve su kutije jednako teške, osim one koju tražite – ona je nešto teža. Prilikom traženja, u prosjeku će vam za N kutija trebati N/2 pokušaja da pronađete pravu (u 50% slučajeva tražena će kutija biti u prvoj polovici vaganih kutija). Ako baš nikako nemate sreće, trebat će vam N pokušaja (odnosno N – 1, jer kad izvažete predzadnju znate da je zadnja ona koju tražite). Ovakvo „traženje“ kutije analogno je traženju broja (ključa) za koji je lako provjeriti je li ispravan – zamislite da su kutije brojevi 0000, 0001, 0010… Dio sigurnosti na internetu počiva upravo u takvim ključevima, koji imaju na primjer 128 binarnih znamenki, što znači da (zlim hakerima) u prosjeku treba 2¹²⁸/2 = 2¹²⁷ ≈ 10³⁸ pokušaja da ga odgonetnu.

Kvantno računalo mijenja alate koje imate. Umjesto klasične vage, sada imate onu s dva jezička, na koju možete stavljati više kutija istovremeno. Ako polovicu svih kutija stavite na jedan kraj vage, a drugu polovicu na drugi kraj, odmah možete eliminirati polovicu kutija! Na primjer, imate li 16 kutija, prvo će ih vaganje reducirati na 8, drugo na 4, treće na 2 i četvrtim ćete saznati koja je tražena kutija. Umjesto prosječnih 8 ili nesretnih 15 vaganja, pronašli smo traženu kutiju u svega 4, što je velika ušteda.

Kvantno računalo primjenom Groverovog algoritma radi nešto slično.

**Kako rade kvantni bitovi (qubiti)?**

Na temeljnom nivou, računala funkcioniraju primjenom operacija na klasične ili kvantne bitove. U klasičnim računalima bitovi mogu biti u dva stanja (koja se najčešće označavaju s 0 i 1). Primjerice, NOT operacija na nekom slijedu bitova pretvara 0 u 1 i obrnuto:

NOT 1001 → 0110

Očito, operacije koje na računalu možemo izvoditi ovise o vrsti bitova koje imamo na raspolaganju. Dakle, ako „izmislimo“ neke nove i neobične kvantne bitove, možemo na njima primjenjivati neke nove i neobične operacije, nedostupne klasičnom računalu. I to je ideja iza kvantnih računala – ona na fundamentalnom nivou omogućuju izvođenje operacija nemogućih klasičnim računalima. Klasična računala mogu simulirati kvantna, ali ne jako efikasno – za simulaciju 49 qubita potrebno je oko 4 TB (oko 32000000000000 bita).

Superpozicija stanja

Po čemu su qubiti različiti od bitova? Osim u stanju 0 i 1, qubiti mogu biti i u superpoziciji ta dva stanja. Intuitivno, to zvuči (i često se objašnjava kao) „i 0 i 1 istovremeno“. Popularno je i objašnjenje „ili 0 ili 1, ne znamo dok ne izmjerimo“. Međutim, Scott Aaronson, jedan od vodećih svjetskih stručnjaka na polju kvantnih računala tvrdi kako takva objašnjenja baš i ne pomažu u razumijevanju kvantnih računala. Umjesto toga, superpoziciju stanja treba shvatiti kao novu ontološku kategoriju – novi način kombiniranja stanja koji jednostavno ima neke karakteristike koje možemo iskoristiti. Konkretno, qubit u superpoziciji stanja 0 i 1 (označenih |0> i |1>) ima amplitude vjerojatnosti (označene s a₁ i a₂) vezane uz svako pojedino stanje:

q = a₁|0> + a₂|1>

pri čemu vrijedi da je suma kvadrata svih amplituda jednaka 1, u ovom slučaju:

a₁² + a₂² = 1

Na primjer, ako je a₁ = 1, a₂ mora biti 0 što znači da nismo u superpoziciji već u „stanju 0“, odnosno |0>. Jednako tako, ako je a₂ = 1 i a₁ = 0, nalazimo se u |1>. (Samo) u ta dva slučaja, qubiti su ekvivalentni bitovima. Primjer jednostavne superpozicije je stanje u kojem je , što znači da su amplitude vjerojatnosti oba stanja jednake (u 50% slučajeva dobivamo |0>, a u drugih 50% |1>). No to nije jedina mogućnost – superpozicija stanja nije „još jedno stanje“ (to bi samo značilo da radimo u brojevnom sustavu s bazom 3, a ne 2), već beskonačno stanja definiranih različitim kombinacijama a₁ i a₂. To znači da se klasičnim računalom ne može lako simulirati kvantno, jer jedan qubit u superpoziciji stanja ne možemo jednostavno „prevesti“ u seriju klasičnih bitova.

Qubiti su u superpoziciji stanja sve dok ih ne izmjerimo, u kojem trenutku poprimaju vrijednost 0 ili 1, pri čemu kvadrati amplituda vjerojatnosti (a₁² i a₂²) odgovaraju vjerojatnosti mjerenja određenog stanja. Dakle, qubit u stanju će prilikom mjerenja u 90% slučajeva dati |0>, a u 10% stanje |1>. To možda zvuči neobično, ali nije osobito komplicirano – umjesto da smo u stanju |0> ili |1>, negdje smo između: možda bliže |0> ili |1> , ili možda na pola puta.

Međutim, „trik“ je u tome da amplitude vjerojatnosti mogu biti negativne, pa čak i kompleksne! To znači da se u slučaju kada imamo više qubita u superpoziciji amplitude određenih stanja mogu poništiti (jer su jednake u iznosu, ali suprotnog predznaka), a iznosi amplituda drugih stanja povećati (jer im amplitude imaju isti predznak). Ako qubite zamislimo kao valove, poništenje amplituda možemo predočiti kao destruktivnu interferenciju (susret brijega i dola, ili pozitivne i negativne amplitude), a povećanje njihova iznosa kao konstruktivnu interferenciju (susret brijega i brijega ili dola i dola –amplituda istog predznaka).

Većina „novih i neobičnih“ operacija koje izvodi kvantno računalo tako se svode na manipulaciju (kompleksnih) amplituda vjerojatnosti (ili, kako bi matematičari rekli – rotaciju vektora u dvodimenzionalnom Hilbertovom prostoru). Najkraće rečeno, u kvantnom računalu pokušavamo doći do točnog rješenja (određenog niza nula i jedinica) tako da poništimo, ili smanjimo iznose amplituda svih stanja koja nisu rješenje, a povećamo iznos amplitude stanja koje jest.

U poznatom eksperimentu iz 1927. godine, Davisson i Germer pucali su elektrone kroz jednu pukotinu i zatim ih hvatali na kristal nikla, čime su dobili smeđu krivulju. Međutim, pucanjem elektrona kroz dvije pukotine umjesto kroz jednu dobiveni se uzorak značajno promijenio – na određenim mjestima uopće nije bilo elektrona. U kvantnim računalima cilj je “postaviti pukotine” na taj način da se amplitude svih pogrešnih rješenja ponište, tako da na kraju ostane samo točno rješenje.

Upravo korištenjem superpozicija kvantno računalo postiže dramatično veću efikasnost od klasičnog. Ono nije brže od klasičnog u smislu da se operacije brže događaju, već koristi algoritme koji u drastično manje koraka dolaze do točnog rješenja. Uzmimo problem gdje je jako teško pronaći točno rješenje (neki binaran broj), ali je lako provjeriti je li neko rješenje točno. Takvih je problema u matematici puno, a neki se kriptografski sustavi čak i zasnivaju na toj pretpostavci. Klasično računalo će napraviti listu potencijalnih rješenja (na primjer, binarnih brojeva s 128 znamenki) i prolaziti kroz listu tako da ispituje jedan po jedan broj, što traje jako dugo.[a] Također, povećanjem broja znamenki vrijeme, ili broj koraka, potreban klasičnom računalu za rješavanje povećavat će se eksponencijalno (s 2ⁿ, gdje je n broj znamenki), što znači da lako možemo doći do dovoljno velikog broja znamenki da problem bude praktički nerješiv.

S druge strane, kvantno računalo s dovoljnim brojem (n) qubita može napraviti superpoziciju svih mogućih rješenja i zatim odgovarajućim algoritmom eliminirati amplitude vezane uz sva pogrešna rješenja, tako da na kraju „ostane“ samo točno rješenje. Dakle, umjesto da provjerava jedno po jedno potencijalno rješenje, kvantno računalo manipulira superpozicijom qubita koja se izvršavanjem koda sve više približava točnom rješenju. To znači da, ako imamo dovoljno qubita, problem možemo riješiti dramatično brže od klasičnog računala – konkretan primjer, vezan uz Groverov algoritam, nalazi se pri kraju članka.

Preuzeto s http://www.smbc-comics.com/comic/the-talk-3

U idućem poglavlju vidjet ćemo par primjera vrlo jednostavnog koda napisanog na kvantnom računalu, u kojem ćemo ilustrirati koncept superpozicije i vidjeti kako se qubiti mogu kvantno spregnuti.

IBM Quantum Experience

Početkom prošle godine IBM je počeo zaprimati prijave za rad na svom IBM Q projektu – kvantnom računalu dostupnom svima, koje se nalazi u cloudu. Danas, registraciju možete obaviti u svega par minuta, klikom na https://www.research.ibm.com/ibm-q/. U okviru tog projekta, IBM nudi dva univerzalna kvantna računala, s 5 i 16 qubita. Univerzalna u ovom kontekstu znači da su njihovi qubiti vrlo kvalitetni, da su u mjerenjima greške male, odnosno da pripremljena stanja ostaju stabilna relativno dugo. Svako izvođenje koda na IBM-ovom kvantnom računalu košta „jedinice“ koje se periodički obnavljaju, a ako ste štedljivi rezultat možete i simulirati na klasičnom računalu (budući da se radi o malom broju qubita to nije osobito zahtjevno).

Pogledajmo sad kontrolnu ploču za pisanje koda na IBM-ovom kvantnom računalu od 5 qubita. Na tom računalu, pisanje i izvođenje koda odvija se s lijeva na desno, na dijagramu na koji se vrata (gates, koja opisuju operacije) stavljaju slično kao što se note crtaju u kajdanku. Složeniji programi mogu se pisati u (recimo) Pythonu, te na taj način kombinirati s kodom koji se izvodi na klasičnim računalima.

Sasvim lijevo, možemo vidjeti pet qubita označenih s q[0] do q[4]. Nakon toga, oznakom |0> naznačeno je kako svi qubiti startaju u stanju |0>. Na točke, koje se nalaze na linijama svakog qubita, stavljaju se logička vrata prikazane s desne strane. Svaki kod završava s jednom ili više operacija mjerenja, koja se nalazi u donjem desnom kutu, a rezultat svakog koda je peteroznamenkasti binarni broj u kojem svaka znamenka odgovara stanju jednog qubita, odozdo prema gore (na primjer, |01001> odgovara stanju u kojem su q[3] i q[0] u stanju |1>, a ostali u stanju |0>).

U narednih par primjera, u interesu zadržavanja kakve-takve jednostavnosti, bavit ćemo se samo realnim amplitudama vjerojatnosti. Međutim, pozivam čitatelja da ne zaboravi kako su amplitude vjerojatnosti općenito kompleksni brojevi, tako da cijela stvar ima još jednu dimenziju koju kvantna računala mogu eksploatirati, a koju ovdje nećemo prikazati.

Paulijeva vrata

Želimo li promijeniti stanje npr. qubitu q[3], možemo iskoristiti operaciju označenu slovom X (Paulijeva vrata). Paulijeva vrata pretvaraju |0> u |1> i obratno, te su u ovom slučaju analogna operaciji NOT u klasičnom računalu:

čime kao rezultat dobivamo |01000> u 100% slučajeva (svi qubiti koje nismo mjerili ostaju |0>):

Hadamardova vrata

Neki qubit možemo staviti u superpoziciju stanja korištenjem Hadamardovih vrata (označenih H), koja djeluju na sljedeći način:

U ovom slučaju, kao rezultat očekujemo |00000> i |01000> s jednakom vjerojatnošću:

Iz rezultata je razvidno da je kod kroz kvantno računalo potrebno provesti čim više puta, kako bi dobili statistički signifikantne rezultate. U ovom konkretnom slučaju, nakon 100 ponavljanja dobili smo |00000> u 49,8% slučajeva i |01000> u 50,2%, što je prilično dobro.

Što se dogodi kada na isti qubit dvaput zaredom djelujemo Hadamardovim vratima?

Djelovanjem prvih vrata dobivamo:

Zatim, druga vrata djeluju na rezultat prvih, na svako stanje posebno:

U izrazu sasvim desno, amplitude vezane uz stanje |0> se zbroje, uz |1> pokrate, pa dobivamo:

odnosno

Dakle, prvim H vratima stvorili smo superpoziciju stanja, da bi smo je drugima uništili.

Kvantna spregnutost i CNOT vrata

Osim superpozicije stanja, kvantna računala koriste još jedan fenomen iz kvantne mehanike – kvantnu spregnutost (prema Struni, istoznačnice su: kvantna prepletenost, kvantna svezanost). Spregnuti qubiti imaju svojstvo da su im “sudbine” međusobno povezane – jednom kada izmjerimo jedan (bilo koji) od njih, znamo i kakav će biti rezultat mjerenja drugog. To znači da spregnute qubite moramo opisati zajedničkom superpozicijom. Qubite jednostavno možemo spregnuti CNOT vratima, koja primjenjuje Paulijeva vrata (pretvara |0> u |1> i obratno) na ciljni qubit (označenog s plusom) samo ako je kontrolni qubit (označen točkom i povezan s ciljnim) u |1>:

Važno je primijetiti da je u trenutku „izvođenja“ operacije CNOT nemoguće znati hoće li rezultat q[1] biti |0> ili |1>. Čak štoviše, mi u gornjem primjeru q[1] mjerimo nakon q[0]! To znači da je operacijom CNOT q[0] ušao u superpoziciju skupa s q[1], pa se njihovo zajedničko stanje može zapisati kao:

Dakle, korištenjem različitih operacija na kvantnom računalu možemo pripremati superpozicije više spregnutih qubita nalik gore prikazanoj.

Čemu to sve skupa služi?

Kvantno računalo primjenom Groverovog algoritma radi nešto slično primjeru opisanom u Okviru za laike na početku članka [b], u smislu da pripremi niz superpozicija (važe više kutija, odnosno brojeva istovremeno), te onda nizom koraka povećava iznos amplitude točnog odgovora, a smanjuje iznose amplituda pogrešnih odgovora. Kad krećemo s vaganjem, vjerojatnost da je bilo koja kutija „točna“ je 1/N, međutim nakon nekoliko vaganja vjerojatnost određenim kombinacijama kutija (superpozicijama!) raste, a drugima pada. Na IBM-ovom računalu Groverov algoritam izgleda ovako (tražimo među 4 broja, trebaju nam 2 qubita, rješenje je |11>):

Izvođenjem dobivamo:

Kao što možemo vidjeti, sve amplitude osim |11> su se poništile, pa u daleko najvećem broju slučajeva (85,8%) dobivamo samo |11> kao rješenje.

Kvantna računala primjenom Groverovog algoritama daju kvadratno ubrzanje u odnosu na klasično računalo, odnosno završavaju (pouzdano pronalazi rješenje) u koraka. To znači da je kvantnom računalu za razbijanje 128 bitnog ključa korištenjem Groverovog algoritma potrebno 2⁶⁴ ≈ 10¹⁹ koraka, oko 10¹⁹ puta manje nego klasičnom računalu, što je ogromno ubrzanje.

Konkretno, ako bi „1 korak“ klasičnog i kvantnog računala trajao jednako dugo i ako bi klasičnom računalu za razbijanje 128 bitnog ključa trebalo onoliko vremena koliko je star svemir, kvantno računalo (sa 128 qubita) bi to riješilo u otprilike 10 milisekundi.

Za kraj ovog dijela, naglasio bih kako kvantna računala nisu svemoguća, već mogu pomoći samo u rješavanju određenih problema, i to onih za koje znamo napisati odgovarajuće algoritme (ne mogu NP‑complete probleme riješiti u polinomijalnom vremenu, ali neke od njih mogu kvadratno ubrzati).

Slično kao i kod klasičnog računarstva, razvoj teorije kvantnog računarstva i algoritama koje kvantna računala mogu koristiti prethodili su fizičkoj izvedbi kvantnih računala, što znači da već sad imamo dobru ideju koje probleme (osim traženja ključeva) možemo efikasno riješiti kvantnim računalima. A o tome, fizičkoj strukturi kvantnih računala i još koječemu čitajte u drugom dijelu…

Link za IBM-ov projekt: https://www.research.ibm.com/ibm-q/learn/what-is-quantum-computing/

[a] U praksi najčešće postoje neke prečice tako da da ne moramo isprobati baš sve brojeve, ali skaliranje je s brojem znamenki je za takve “teške” probleme i dalje eksponencijalno.

[b] Zapravo Groverov algoritam radi dosta različito, no koristi superpoziciju i zahtjeva podjednak broj koraka kao i metoda s vagom s dva jezička, pa mi se analogija učinila korisnom.

Inovacije