Kvantové Počítače #1

Rád som si prečítal (a podľa ohlasov aj ďalší ľudia) sériu článkov o kvantovej kryptografii. Nedávno som spracovával jeden zo svojich posledných semestrálnych projektov. Týkal sa práve algoritmov výpočtov pomocou kvantových počítačov. Rozhodol som sa teda, že odovzdám to niečo, čo viem v tomto kúte vedy do rúk ďalších.

Hneď na začiatok chcem napísať, že údaje v tomto článku sú čiastočne veci z odbornej literatúry a čiastočne z mojej hlavy, keďže si nepamätám odkiaľ sa to v mojej kocke vzalo. Veci, čo tu sú napísané som nevymyslel ja, preto je možná podobnosť s niektorými odsekmi iných článkov, v iných jazykoch, na iných miestach na internete. Mojou snahou je pokúsiť sa podať v dvoch (troch) pokračovaniach ucelenú sadu informácií o tejto problematike. (Ja som takú nikdy nenašiel (možno len neviem hľadať) ) Tento článok ma popísať kvantové počítače, ich architektúry, princíp ich fungovania a možno ešte niečo, čo mi medzičasom napadne :)

História.

História kvantových počítačov sa začala písať koncom 70tych rokov, kedy bol vyvrátený pôvodný názor, že systém predsa pri prevádzaní výpočtov vytvára teplo, ktoré musí byť odvádzané, aby sa predošlo poškodeniu chúlostivých súčastí elektrických obvodov. To však pre príliš rýchly, či príliš integrovaný počítač nie je v princípe možné, čiže sa miniaturizácia a integrita systému nemôže dostať na úroveň, kedy prestávajú platiť zákony fyziky a začínajú platiť zákony kvantové. V roku 1978 bol navrhnutý počítač, ktorý pracuje fyzikálne vratným spôsobom (aj obrátený fyzikálny dej je možný). Americký fyzik Richard Feynman, si pri rozbore teoretických aspektov simulácií kvantových systémov na klasických počítačoch všimol, že nároky na výpočtový čas rastú geometrickým radom v počte stupňov voľnosti kvantového systému (každý stupeň voľnosti zodpovedá jednej z nezávislých súradníc systému – pr. jedna klasická častica má 3 stupne voľnosti, dve potom 6, tri 9 a pod.). Feynman vyslovil obrátenú hypotézu, že simulácia výpočtu klasického počítača pomocou cielenej evolúcie nejakého vhodného kvantového systému môže viesť k podstatnému urýchleniu niektorých algoritmov. Posledný krok smerom k prvej definícií spravil oxfordský matematik David Deutsch v práci z r. 1985. V nej ako prvý vyslovil prvú definíciu kvantového počítača: Kvantovým počítačom je fyzikálny systém, ktorého určité kvantové stavy (napr. stavy zodpovedajúce energetickým hladinám) kódujú klasické logické (boolovské) hodnoty (nuly a jednotky) a jeho časový vývoj zodpovedá prevedenia určitého algoritmu. Zvýšený záujem o celú problematiku nastal v roku 1994, kedy Peter Short z Bellových laboratórií prišiel s kvantovým algoritmom pre faktorizáciu veľkých čísel s algoritmom prehľadávania nezotriedenej databázy.
Zložitosť samotného problému určujeme podľa času, ktorý je potrebný na vykonanie toho najrýchlejšieho známeho algoritmu. Inými slovami čím je problém zložitejší, tým na jeho vyriešenie potrebujeme uskutočniť viac krokov. Táto definícia zložitosti plne zodpovedá našej intuitívnej predstave. Typickým príkladom zložitého problému je rozklad na prvočísla. Momentálne síce nevieme povedať nakoľko je tento problém zložitý, pretože stále ešte nepoznáme ten najrýchlejší algoritmus na jeho riešenie. Veríme však tomu, že ide o úlohu veľmi ťažkú. Dokonca sme na tomto fakte založili aj bezpečnosť našich informácií na internete (RSA šifra). Skúste si samy zistiť násobkom ktorých dvoch prvočísiel je 403. Opačná úloha, t.j. zistiť výsledok 19x23, je oproti tomu hračkou. Rozlúštiť moderné šifry by pri dnešnom výpočtovom výkone trvalo stovky rokov. Kvantovému počítaču by to trvalo desiatky sekúnd, nanajvýš niekoľko minút.

V čom je teda rozdiel?

Podla Deutchovho popisu ste si asi povedali, že v čom je teda rozdiel medzi kvantový a číslicovým počítačom, keďže tá definícia s miernymi obmenami sedí aj na nami dobre známe digitálne počítače. (dvojková sústava, časový beh zodpovedá dĺžke behu deterministického algoritmu)

Kvantový počítač je svojbytný kvantový systém, ktorého logické stavy nie sú len typu TRUE-FALSE, ale tiež ich ľubovoľná superpozícia. To vedie k pojmu kvantový bit – qubit (analógia klasického dvoj hodnotového bitu.) Rovnako zodpovedajúci klasickým hradlám pre operácie NOT, X-OR a pod. Spontánny preto lebo počas behu algoritmu nesmieme získavať kontrolné výsledky akýmkoľvek meraním, lebo by sme tým zmenil konečný výsledok.
Táto spontánnosť bola veľmi dobre vysvetlená v článku o kvantovej kryptografii tu na blackhole, ktorý som vyššie spomínal. Veľmi laicky povedané odčítaním čiastkového výsledku by sme zmenil stav qubitov v danom okamihu. (ako keby ste rátali integrál a niekto by vám v polovici prepísal čiastkové výsledky) Pokým sa na elektrón nepozriete, neviete, kde presne sa nachádza. A naviac sa v istom ohľade môže nachádzať na viacerých miestach súčasne. Súvisí to s ďalšou vlastnosťou kvantovej fyziky a totiž, že častice sú zároveň vlny. Kľúčovým pojmom je tzv. vlnová funkcia, čo je matematický predpis určujúci možné stavy častice a ich pravdepodobnosti. Pokým je častica ponechaná sama sebe, nachádza sa súčasne vo všetkých stavoch umožnených vlnovou funkciou. Vo chvíli, keď sa pokúsime zmerať vlastnosti objektu, dôjde k tzv. kolapsu vlnovej funkcie a my zmeriame jednu konkrétnu hodnotu. Zatiaľ čo základná jednotka klasického počítača môže existovať len v jednom z dvoch stavov, tzv. qubit kvantového počítača sa nachádza v obidvoch stavoch súčasne. Stavy „n“ častíc potom môžeme skladať (tento jav sa nazýva superpozícia) a celý systém sa tak v jednom okamžiku môže nachádzať v 2^n stavoch. Napríklad pre kvantový systém 3 qubitov dostávame celkom 8 kombinácií: 000, 001, 010, 011, 100, 101, 110, 111. Superpozícia je kľúčovým momentom celého kvantového počítania. S ňou sa stáva kvantový počítač masívne paralelným zariadením, ktorého výkon rastie s pridávaním ďalších stavebných kameňov exponenciálne.

Vráťme sa k prvočíslam.

V roku 1994 Peter Shor našiel spôsob ako efektívne uskutočniť diskrétnu Fouriérovu transformáciu za pomoci kvantového počítača. Ako sme si povedali, táto transformácia je tým komplikovaným krokom v probléme rozkladu na prvočísla. Vďaka tomuto výsledku sa kvantový počítač stal jedným z hlavných potenciálnych nepriateľov niektorých kryptografických protokolov.

Pri rozklade N na prvočísla nás zaujíma, či nejaké číslo delí N, alebo nie. Inými slovami zaujíma nás podiel. Problémom je, že výpočet tej istej funkcie (podielu) potrebujeme urobiť veľmi veľa krát. Vlastne pre každé číslo zvlášť až pokým nenarazíme na ten správny výsledok. S kvantovými bitmi však akoby túto funkciu počítame naraz pre všetky hodnoty, pretože máme stavy, ktoré sú superpozíciou všetkých hodnôt. Táto vlastnosť kvantových výpočtov sa nazýva kvantovým paralelizmom, pretože kvantový počítač súčasne (paralelne) vykonáva všetky úlohy.

Proces výpočtu si môžeme predstaviť tak, že v algoritmoch na výpočet funkcie používame akúsi čiernu skrinku. Napríklad pri hľadaní rozkladu táto čierna skrinka počíta podiel čísla, ktoré rozkladáme a nášho tipu na výsledok. Ak dostaneme celočíselný výsledok, tak vieme, že sme hľadaný rozklad našli. Ak nie, tak pokračujeme ďalším tipom. Kvantová mechanika nám umožňuje iba pri jednom použití „kvantovej“ čiernej skrinky zistiť hodnoty funkcie pre všetky potenciálne tipy. Jediným problémom zostáva, že tento výsledok má tiež formu superpozície a je stále skrytý v kvantovom svete. Musíme vykonať meranie, ktoré náhodne vyberie iba jedinú hodnotu, čím sme zdanlivo tam, kde sme boli aj predtým. Nie je to však úplne tak. Nás totižto zaujíma tento výpočet iba pre hodnotu, pre ktorú je výsledkom delenia celé číslo bezo zvyšku. O tejto hodnote vieme, že je jediná. Vhodnou manipuláciou (ďalším kvantovým výpočtom) sa pokúsime nastaviť pravdepodobnosti, tak, aby sme zvýhodnili práve tento prípad. Vďaka tomu s vysokou pravdepodobnosťou nameriame hodnotu, ktorú hľadáme. Kvantová mechanika za nás skúsi paralelne všetky možnosti a vyberie tie, ktoré hľadáme.

Podobný príklad by som vedel uviesť pri rátaní nejakej vlastnosti funkcie (párnosť). Ak chceme zistiť, či spĺňa podmienky musíme si zobrať sadu hodnôt x, vyrátať k nim f(x) a na základe toho potvrdiť alebo vyvrátiť odhad. Algoritmus číslicovom počítači by vyrátal f(x) pre každé x ako samostatný úkon. Algoritmom na kvantovom počítači by pomocou jedného spustenia algoritmu vedeli s určitou pravdepodobnosťou povedať hneď či spĺňa podmienky danej vlastnosti alebo nie. Nastavíme sadu qubitov do superpozičného stavu tak, aby obsahovali všetky nami spomenuté hodnoty x. po vykonaní algoritmu dostávame f(x) pre všetky x naraz. (spomínaný kvantový paralelizmus)

Záver

Tak teda úvod máme za sebou. Nabudúce si povieme o niektorých ďalších princípoch, ktoré tu neboli spomenuté. Povieme si o tom ako to vlastne prebieha v praxi (čo sú črevá kvantového počítača) Rozoberiem nedávno popísaný Zeno efekt, taktiež, že prvý kvantový počítač určený na fabrikovú výrobu je už na svete a nakoniec zhnutie a malý pohľad do budúcnosti.

Vrelá DÍK ak ste to dočítali dokonca :)