Programiranje kvantnog računala: generiranje pravih slučajnih brojeva

Računala su determinirani, predvidljivi strojevi i dizajnirani su tako da slijepo slijede niz uputa na ponovljiv način. Ovakva priroda računala služila nam je izuzetno dobro tokom većeg dijela prošlog stoljeća, ali ovaj dizajn dolazi s temeljnom manjkom: ne može obavljati slučajne operacije¹. Generatori nasumičnih brojeva danas su izuzetno važna sastavnica mnogih aplikacija, ali iako brojevi koje generiraju mogu biti dovoljno slučajni, oni su „pseudo“ slučajni i često ih je moguće na neki način predvidjeti ili preokrenuti.

Danas je moguće iskoristiti čudnu, nepredvidivu prirodu subatomskih čestica i koristiti ih za obavljanje izračuna unutar kvantnog računala. Sa samo nekoliko redaka koda možemo programirati stvarno kvantno računalo za stvaranje stvarnih slučajnih brojeva za nas. Nešto što je prethodno bilo nemoguće pomoću klasičnog računala zasnovanog na Turingu.

Generatori nasumičnih brojeva danas

Većina popularnih programskih jezika ugrađen je neki oblik generatora slučajnih brojeva koji programeri mogu koristiti. Ti generatori općenito uzimaju ulazno sjeme koje predstavlja trenutni datum i vrijeme, mijenjaju ovu vrijednost pomoću algoritma i šalju vrijednost toliko različitu od ulaza da ih doživljavamo kao slučajne. Funkcija kodiranja je predvidljivi algoritam s velikom količinom entropije (za malu promjenu unosa oni vraćaju veliku promjenu u izlazu), a svaki put dobivamo različit broj jer se ulazno sjeme mijenja s vremenom. Za gotovo sve praktične primjene ovaj sustav funkcionira savršeno dobro, ali s obzirom na to da je predvidljiv sustav, on nije zaista slučajan.

Uzmimo kao primjer generator slučajnih brojeva koji je pružio Javascript. Prije svega, budući da je Javascript jezik interpretiran u različitim okruženjima (preglednik ili node.js), na tumaču je da odluči koje će algoritme koristiti koji su u skladu s ECMAScript specifikacijom. Danas većina modernih preglednika koristi isti algoritam slučajnosti da bi aktivirao Javascript funkciju Math.random () nazvanu xorshift128 +.

Ovdje je općenita verzija ovog algoritma napisana u C²:

Svrha ovog koda je uzeti neki ulaz (sjeme) i izbrisati ga do te mjere da će se svaka dva izlaza iz dva odvojena ulaza međusobno činiti potpuno različitima i samim tim slučajnim. Algoritam to postiže premještanjem sjemenskih binarnih prikaza gore-dolje i preokretom bitnih prikaza između koraka, što rezultira pomalom predstavom broja potpuno različitog od sjemenskog unosa.

Da bi ova funkcija mogla pružiti različite rezultate svaki put kada je pokrenut, potrebno nam je sjeme koje se uvijek mijenja. Preglednici (i drugi programski jezici) često jednostavno koriste numerički prikaz trenutnog datuma i vremena³, na primjer, vrijeme UNIX epohe, broj milisekundi koji su protekli od 1. siječnja 1970. godine.

S ovim sjemenom i gornjim algoritmom entropije, možemo postići vrlo uvjerljiv generator slučajnih brojeva. Računalni sustavi stalno koriste ove funkcije bez problema, ali ne možemo ih nazvati stvarno slučajnim generatorom brojeva. Ako netko zna kako generator slučajnih brojeva radi i može predvidjeti ulazno sjeme, može predvidjeti i izlaz funkcije. Jedan od načina za poboljšanje slučajnosti ovog sustava je otežavanje predviđanja sjemena. Na primjer, mnogi sustavi koriste kozmičko mikrovalno pozadinsko zračenje (elektromagnetski radio valovi koje još uvijek ostaje veliki prasak) kao sjeme⁵ jer nitko ne može predvidjeti kako će se ovaj pozadinski šum ponašati u bilo kojem trenutku vremena.

Sustav slučajnosti koji koristi nepredvidivo sjeme poput pozadine mikrovalne u ovom je trenutku prema današnjem saznanju potpuno slučajan. Trenutno nitko ne može predvidjeti kako će se to sjeme ponašati u određenom trenutku, pa tako ni ne može predvidjeti slučajni broj koji generira. Ova vrsta sjemena možda nam je čak i nemoguće predvidjeti u budućnosti, ali ako budemo imali ista mjerenja kozmičke mikrovalne pozadine kao netko drugi i koristimo je kao ulaz u generator slučajnih brojeva, moći ćemo predvidjeti njihov rezultat ,

Da bismo stvorili doista slučajni broj, u prirodi moramo pronaći nešto što ne možemo savršeno predvidjeti, nešto što se može opisati samo vjerojatnošću. Sve do početka 20. stoljeća nije se vjerovalo da postoji, ali teorija kvantne mehanike otvorila je vrata još čudnijem i nepredvidivijem svijetu.

Vjerojatnost u kvantnom svijetu

Kvantna mehanika je teorija koja opisuje prirodu čestica na subatomskoj skali. Kaže da, dok promatramo svijet u sve manjim i manjim razmjerima, klasični opisi čestica i sila poput onih koje je definirao sir Isaac Newton u 18. stoljeću postaju manje točni i moramo se prebaciti na različite kvantne opise vođene statistikom i vjerojatnošću. Na primjer, ne može se predvidjeti točan položaj elektrona oko atoma, možemo samo predvidjeti vjerojatnost pronalaska elektrona u određenom području oko atoma u određenom trenutku⁶.

Da stvari budu još čudnije, kopenhagenska interpretacija kvantne mehanike koju su osmislili Niels Bohr i Werner Heisenberg kaže da kvantni sustavi nemaju određena svojstva prije nego što se mjere, ali postoje u svim mogućim stanjima istovremeno, u principu poznatom kao superpozicija. Tek kada se opazi sustav, superpozicija se urušava i sustav postoji u jednom određenom stanju. To je poznato kao promatrački efekt. Uzimajući primjer položaja elektrona, možemo predvidjeti vjerojatnost da će elektron biti prisutan na određenom mjestu u određeno vrijeme, ali prije tog mjerenja elektron postoji u svim mogućim položajima oko atoma. Tijekom mjerenja, elektroni će se pokazati da se nalazi na jednom mjestu, ali promatranjem i mjerenjem elektrona smo promijenili njegovo stanje i ne možemo odrediti druga svojstva poput trenutka zbog principa nesigurnosti⁷.

Ova interpretacija kvantnog svijeta razumljivo je uzdrmala tadašnju fizičku zajednicu i raspravlja se do danas. Einstein je odbio vjerovati da se realnošću upravlja vjerovatnoćom i slavno je rekao: "U svakom slučaju, uvjeren sam da On (Bog) ne baca kockice" i "Zar stvarno mislite da mjesec nije tamo ako ne tražite na tome?". Kao odgovor, Niles Bohr je kasnije odgovorio "Einstein, ne govori Bogu što da radi." ⁸

Sviđalo nam se to ili ne, kvantna teorija ostaje najbolje razumijevanje subatomskog svijeta i razvijena je u srce svih novih tipova procesora informacija. Kvantna računala oslanjaju se na sposobnost postojanja kvantnih čestica u superpoziciji više stanja odjednom za obavljanje izračuna. Budući da kvantna računala mogu manipulirati superpozicijama čestica kojima upravlja vjerojatnost, možemo ih upotrijebiti kao alat za iskorištavanje prirode kvantnog svijeta i stvaranje pravog generatora slučajnih brojeva.

Kubiti i kvantna vrata

Klasična računala koriste binarne znamenke ili bitove za predstavljanje informacija. Bit može uzeti vrijednosti 0 ili 1 i predstavljene su s dvije razine istosmjernog napona unutar računalnog procesora. Kvantna računala obično prikazuju informacije na isti način, koristeći 0 ili 1 bit, ali oni fizički provode ova stanja koristeći binarna svojstva subatomskih čestica. Ta svojstva mogu biti zavrtanje elektrona (spinovanje i centrifugiranje) ili polarizacija fotona (vodoravna i okomita polarizacija). Bilo koji od ovih prikaza može se opisati kvantnom mehanikom i može biti u superpoziciji oba stanja odjednom⁹. To znači da kvantni bit informacija ili kbit može postojati u superpoziciji oba stanja 0 i 1 istovremeno. Da bismo izmjerili rezultat izračuna, moramo izmjeriti kvantno stanje unutar računala i prisiliti te čestice da odaberu stanje 0 ili 1.

Za manipulaciju qubitima u kvantnom računalu koristimo kvantna vrata slično kao vrata klasičnog kruga. Dok klasično računalo može izvoditi operacije na bitovima poput preusmjeravanja na njihovu suprotnu vrijednost, kvantna vrata mogu obavljati te operacije i naprednije kvantne operacije poput potiskivanja qubita u superpoziciju obje moguće vrijednosti. Vrata koja gura kubit u superpoziciju nazivaju se Hadamardova vrata i jedna su od najosnovnijih i najčešće korištenih logičkih vrata u kvantnom računanju¹⁰.

Kad gurnemo spin elektrona u superpoziciju oba moguća stanja vrtenja prema dolje i dolje koje predstavljaju vrijednosti 1 i 0 kbit, može se reći da elektron ima istodobni spin obje vrijednosti, a qubit je u superpoziciji od 0 i 1. Kada mjerimo ovaj kbit, urušavamo superpoziciju i prisiljavamo je u jedno od ova dva moguća stanja, od kojih je svako jednaka vjerojatnosti¹¹. Svakom superpozicijom i mjerenjem imamo 50% šanse da izmjerimo 1 ili 0. Tada bismo izvršili ekvivalent preokreta novčića koristeći temeljne zakone subatomskog svijeta.

Da bismo generirali naš slučajni broj iz kvantnog bacanja novčića, sve što trebamo učiniti je:

  1. Nabavite qubit s unaprijed definiranim stanjem. To će učiniti 0 ili 1.
  2. Prisilite taj kbit u superpoziciju pomoću Hadamardove kapije.
  3. Izmjerite stanje kubita.
  4. Dobijte vrijednost 0 ili 1 s jednakom vjerojatnošću.

Sada sve što trebamo učiniti za stvaranje našeg pravog generatora slučajnih brojeva je pristup kvantnom računalu i programu u gornjim koracima.

Programiranje kvantnog računala

Iznenađujuće je što su neke tvrtke postavile jednostavna kvantna računala dostupna u oblaku za upotrebu široj javnosti. Jednu od tih usluga pruža IBM i zove se IBM Q Experience. Trenutno ova usluga pruža pristup dvama 5 qubit procesorima i dva 16-bitna procesora raspoređena širom svijeta. Nakon što korisnik stvori besplatan račun, vrijeme računanja dodjeljuje se pomoću kreditnog sustava, a besplatnim korisnicima daje se mali broj bodova za korištenje koji se osvježavaju svaki dan. Svoj krug možete dizajnirati putem internetskog uređivača ili programsko putem SDK-a (16 kubičnih procesora trenutno je dostupno samo korisnicima SDK-a), a kada je vaš program spreman za izvršavanje, on se postavlja u red koji će se pokrenuti kada procesor bude sljedeći dostupan.

Za izgradnju našeg generatora slučajnih brojeva koristit ćemo isporučeni SDK za IBM Q Experience zvan Qiskit. Trebat ćemo napisati svoj kôd na Pythonu, a tijekom pisanja aplikacije moći ćemo ga testirati i na simuliranom kvantnom procesoru lokalno na vlastitom stroju kako bismo uštedjeli vrijeme i kredite.

Najprije počnimo s osnovnim kodom da biste dovršili četiri gore navedena koraka:

Ovdje stvaramo kvantni krug iz dva jednostruka bitova registra, jednog kvantnog registra s jednim kbitom i klasičnog registra slične veličine za interakciju s kvantnim registrom. Zatim primjenjujemo Hadamardova vrata na naš jedinstveni kbit kako bismo ga prisilili u stanje superpozicije i izmjerimo to stanje u našem klasičnom registru. Napokon izvršimo postupak koji smo upravo opisali na lokalnom simuliranom procesoru, govoreći SDK-u da samo jednom pokrene proces. U većini drugih svrha, željeli bismo pokrenuti kvantni krug više puta i procijeniti rezultate kako bismo uklonili inherentnu slučajnost u sustavu, ali za naše će svrhe samo jedan zahvat funkcionirati savršeno. Možemo ispisati brojeve naših rezultata, koji će biti prikazani kao karta mogućih vrijednosti bita u odnosu na to koliko su puta izmjereni za svako pokretanje, npr .: {"0": 1, "1": 0}. Otkrićete da će se jednom kada se ovaj program pokrene na kvantnom procesoru mjerenje vrijednosti 0 ili 1 dogoditi s 50% vjerojatnosti.

Ovaj kôd dao nam je ekvivalent savršenog bacanja novčića, tako da sada sve što trebamo učiniti je pronaći način da uzmemo niz binarnih novčića i pretvorimo ih u slučajni broj u određenom rasponu. Jednostavan način da to učinite je uzeti slučajne vrijednosti bita koje generiramo gornjim kodom i složiti ih u nizu radi stvaranja binarnog broja. Kad ovaj binarni broj pretvorimo u decimalni, ustanovit ćemo da će svaki put biti slučajni decimalni broj.

Ako ćemo dopustiti korisničkom unosu da odabere raspon za generiranje našeg broja, morat ćemo shvatiti koliko je bita potrebno da bi predstavili zadani bazni 10 cijeli broj, tako da ćemo znati koliko slučajnih bita generirati. Jednadžba koju trebamo učiniti je:

Što u pythonu možemo predstaviti kao funkciju:

Pomoću toga možemo napisati funkciju koja generira slučajni broj do zadanog maksimuma ponavljanjem gore navedenog kvantnog kruga za svaki bit koji nam je potreban:

Ovaj kod je jezgra našeg kvantnog generatora slučajnih brojeva. Izračunavamo broj bitova potrebnih za generiranje broja do zadanog maksimuma, a za svaki potrebni bit generiramo slučajnu vrijednost pomoću Qiskita i dodamo ga u nizu generiranih bitova. Zatim raščlanimo ovaj niz kao bazni 10 cijeli broj od baze 2.

Međutim, kod ovog koda postoji ključni problem; ako je pokrenete dovoljno puta, shvatit ćete da zapravo generira brojeve do maksimalne sljedeće snage do dva. To je zato što smo izračunali koliko bita je potrebno za predstavljanje određenog broja, ali ako svi ti bitovi imaju vrijednost 1, onda bi naš broj lako mogao biti veći od zadanog maksimuma. Iznenađujuće je teško riješiti ovaj problem, a najbolji način da se taj broj drži ispod našeg maksimuma bez uvođenja neke druge statističke pristranosti je korištenje uzorkovanja odbacivanja¹³. Jednostavno bismo trebali generirati broj, a ako je prevelik odbaciti taj broj i pokrenuti postupak ponovo. Budući da imamo ograničene resurse na besplatnom računu s IBM Q Experience, kôd ćemo držati jednostavnim i samo ograničiti korisnikov unos na dvije moći zaokružujući ulaz na sljedeću najveću snagu:

Također možemo lako raščlaniti podatke naredbenog retka od korisnika kako bi uzeli željeni maksimum, kao i zastavu koja će programu reći hoće li se izvoditi na stvarnom kvantnom računalu i opciju za prosljeđivanje API ključa za IBM Q Experience:

Konačno, prije nego što pokrenemo svoj kod na stvarnom kvantnom procesoru, bilo bi najbolje optimizirati naše rješenje za minimiziranje minimalnog broja puta kako bismo uštedjeli na slobodnim resursima na našem oblačnom kvantnom procesoru. Primjerice, ako bismo koristili 5-kbitni procesor "IBM Q5 Tenerife" (pozadinsko ime ibmqx4), mogli bismo upotrijebiti svih 5 kubica prolazeći ih kroz Hadamardove kapije i kombinirajući njihove vrijednosti kada se mjere. To će nam omogućiti generiranje slučajnih brojeva do 31 s jednom petljom, a IBM Q Experience pruža dovoljno kredita za 3 upute koje nam omogućuju generiranje broja do 32767 u jednom pokretu.

Sa svim tim elementima u kombinaciji, naš konačni kod postaje:

Potpuni kod i opis kako ga pokrenuti možete pronaći na GitHub-u.

Što se upravo dogodilo?

Ako se prijavite za besplatni račun pomoću IBM Q Experience, nabavite API ključ i pokrenite ovaj program na sljedeći način:

python ./main.py -remote --qx-token  15

otkrit ćete da će postupak trebati neko vrijeme (otprilike 10–20 minuta) i vratiti slučajni cijeli broj između 0 i 16. Evo što se dogodilo dok ste čekali:

  1. Vaše je računalo račvalo unos naredbenog retka i izračunalo koliko je nasumičnih bitova potrebno da bi predstavljali broj između 0 i sljedeću snagu 2 od 15. U ovom slučaju za izgradnju broja do 16 potrebno je 4 bita, što znači samo jednu uputu poslati u kvantni procesor od 5 kbita.
  2. Niz uputa gradi Qiskit SDK i šalje ih IBM-ovom iskustvu da se izvrši.
  3. Vaše su upute smještene u red koji će voditi kvantno računalo "IBM Q5 Tenerife" u New Yorku.
  4. Nakon što je spreman, IBM Q5 Tenerife kvantno računalo dodjeljuje 4 od 5 dostupnih qubita traženom zadatku. Primjenjuje Hadamardova vrata na ova 4 kbita, uvodeći ih u superpoziciju kvantnog spina.
  5. Mjeri se centrifuzija svakog kubita, sabijajući kvantnu superpoziciju i otkrivajući slučajno binarno stanje koje se zatim izvodi u 4-bitni klasični registar.
  6. Izmjereno binarno stanje vraća se natrag u IBM Q Experience i natrag u Qiskit SDK koji radi na vašem računalu.
  7. Vaše računalo uzima ova binarna mjerenja i iz njih izrađuje 4-bitni binarni broj.
  8. Vaš se binarni broj pretvara u bazni 10 cijeli broj i vraća se korisniku.

Čestitamo, upravo ste kontrolirali kvantno računalo i iskoristili čudna nepredvidiva svojstva subatomskih čestica da biste stvorili pravi slučajni broj. Razmislite o tome da dobro iskoristite svoje novonađene supermoći.

Znate li za neke zanimljive praktične aplikacije za kvantno računanje u oblaku? Javite mi @robbiemccorkell.

Reference:

  1. Jason M. Rubin, MIT School of Engineering (2011), Može li računalo generirati doista slučajni broj?
  2. Daniel Simmons, Hackernoon (2014), kako JavaScript Math.random () generira slučajne brojeve?
  3. Adam Hyland, bocoup (2013), generiranje slučajnih brojeva u Javascriptu
  4. Specifikacije baze otvorenih grupa, broj 7 (2018), 4.16: Sekunde od epohe
  5. Jeffrey S. Lee, Gerald B. Cleaver, Sveučilišna knjižnica Cornell (2015), Kozmički mikrovalni spektar pozadinskog zračenja kao slučajni generator za simetričnu i asimetričnu ključ kriptografiju
  6. Tony Hey, Patrick Walters, Cambridge University Press (1987.), The Quantum Universe
  7. Alastair I. M. Rae, Taylor & Francis Group (2008.), Kvantna mehanika (5. izd.)
  8. Wikipedija (2018), interpretacija iz Kopenhagena
  9. Eleanor Riefffel, Wolfgang Polak, Massachusetts Institute of Technology (2011), Kvantno računanje: nježan uvod
  10. Artur Ekert, Patrick Hayden, Hitoshi Inamori, University of Oxford (2008), Osnovni pojmovi u kvantnom računanju
  11. Daniel Baumann, Sveučilište u Cambridgeu (2013.), Pojmovi iz teorijske fizike
  12. Rick Regan, Exploring Binary (2012), Broj bitova u decimalom
  13. Dr. Dimitri DeFigueiredo (2017), Generiranje slučajnih cjelobrojnih brojeva iz slučajnih bajtova

Uredi: Zahvaljujem Bobu Sutoru što je naglasio da je kvantno računalo IBM Q 5 Tenerife vezano samo za Tenerife po imenu, a ne lokaciji, a nalazi se u New Yorku.

Izvorno objavljeno na blog.red-badger.com.