Kvantové Počítače #1

15.11.2007 11:49 | blackhole

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 :)

    • Re: Kvantove Pocitace (part 1) 15.11.2007 | 13:58
      Avatar fiwo   Používateľ

      tesime sa na pokracovanie ;-)
      otazka pre adminov: nepridame v menu polozku typu kvantove zalezitosti zacina ich tu byt viac ;-)

    • Re: Kvantové Počítače (part 1) 15.11.2007 | 14:31
      Avatar blackhole   Návštevník

      Super clanok, aj ja sa tesim na pokracovanie. Mam jednu otazocku, ak je nazov toho "Zeno efektu" odvodeny od Zenonovych paradoxov, nemal by sa potom volat Zenonov efekt? Ak ide o v obore zauzivane pomenovanie doslovne prebrate z anglictiny tak potom som nic nepovedal...

      • Re: Kvantové Počítače (part 1) 15.11.2007 | 14:46
        Avatar blackhole   Návštevník

        Zeno effect.

        Pokial hovorime o kvantovych pocitacoch tak sa tento jav pouziva v pripade kedy dostaneme vysledok algoritmu bez toho aby sa algoritmus vobec spustil. :)

        viac na:http://technology.newscientist.com/article/mg18925405.700.html

        • Re: Kvantové Počítače (part 1) 15.11.2007 | 15:02
          Avatar blackhole   Návštevník

          Dik za odkaz. V tejto oblasti nie som celkom doma, pytam sa preto, ze na http://en.wikipedia.org/wiki/Zeno_effect je na konci zmienka podla coho sa ten jav pomenoval: The quantum Zeno effect takes its name from Zeno's arrow paradox, which is the argument that since an arrow in flight does not move during any single instant, it couldn't possibly be moving at all. Takze by sa to malo snad volat Zenonov efekt ak to uz teda nie je zauzivane inak. Neber to moc ako rypanie, len ma to zarazilo ked som si precital ten clanok na wikipedii, ze preco sa tomu po slovensky hovori Zeno efekt... a tak sa pytam :)

    • Re: Kvantové Počítače (part 1) 15.11.2007 | 17:37
      Avatar blackhole   Návštevník

      Bud som to nepochopil, alebo tam mas chybu, pises, ze 1->3, 2->6, 3->9 je exponencialny rast, tie ciselka by asi mali byt ine.

      Ale aj napriek tomu, ze si niesom isty, ci vsetkemu rozumiem spravne, ma clanok zaujal a tesim sa na pokracovania.

      Thx
      ==
      Ved to zakomentuj, uvidime co sa zrube.

      • Re: Kvantové Počítače (part 1) 15.11.2007 | 20:16
        Avatar blackhole   Návštevník

        mas pravdu. mam tam preklep a vobec som si to nevsimol. jasne ze ten rast nie je exponencialny. opravene.

        • Re: Kvantové Počítače (part 1) 15.11.2007 | 21:29
          Avatar blackhole_ventYl   Používateľ

          mas tam ale jeden drobny fakticky problem. Jedna castica moze mat viac, ako 3 stupne volnosti, co by som povedal, ze hlavne pri pocitani pozicie castice v kvantovej mechanike moze zohrat dost podstatnu ulohu, totizto castica, ktora je plne sfericka (atom) sa moze hybat v troch osiach, ale nech sa lubovolne otaca, je stranovo invariantna (voci svojmu okoliu), takze ma naozaj len 3 stupne volnosti, ale ked zoberes napriklad casticu molekula kyslika, co je dvojatomarny kyslik, ten obsahuje 2 atomy spojene vazbou, takze je to castica, ktora ma jednu os a nie je stranovo invariantna vo vsetkych smeroch, ale moze sa otacat okolo dvoch osi (pri otacani okolo osi rovnobeznej s pomyselnou vazbou je uhlovo invariantna, teda tento stupen sa nerata), takato castica ma 5 stupnov volnosti (3 posuvne a 2 rotacne). nejaka komplikovanejsia castica moze mat stupnov volnosti dokonca az 6 (3 posuvne a 3 rotacne).
          Neviem, nakolko relevantna je rotacia castice v kvantovej mechanike, ale povedal by som, ze vzhladom k tomu, ze asi nevieme zmerat "pociatok" castice v priestore a jej presnu rotaciu, tak to zavazi, kedze to zavazi pri takej banalite, ako pri termodynamike.

          ---
          Cuchat s nadchou, to je ako sniffovat bez promiscu.

          --- Cuchat s nadchou, to je ako sniffovat bez promiscu.
          • Re: Kvantové Počítače (part 1) 15.11.2007 | 21:53
            Avatar blackhole   Návštevník

            nie som si isty ci si teraz reagoval na moj posledny prispevok do diskusie alebo na cast clanku. ale skor asi to prve. ja som chcel len nacrtnut v akom duchu sa bude niest druha cast. jednym z pristupov ako obmedzit neziadany pohyb je ochladenie na obsolutnu nulu... ale o tom az neskor.....

            • Re: Kvantové Počítače (part 1) 16.11.2007 | 09:48
              Avatar blackhole_ventYl   Používateľ

              no, reagoval som na clanok, ale ked tu uz boli pochybnosti ohladom spravnosti poctu stupnov volnosti, tak som tu reply prihodil sem ;)

              ---
              Cuchat s nadchou, to je ako sniffovat bez promiscu.

              --- Cuchat s nadchou, to je ako sniffovat bez promiscu.
    • Re: Kvantové Počítače (part 1) 15.11.2007 | 18:02
      Avatar vid   Používateľ

      vyborny clanok, diky. vecsinu z tohoto som uz poznal, ale zdroje z ktorych som to studoval boli ovela nezrozumitelnejsie pisane.

      dufam ze v pokracovaniach vysvetlis ten princip, ako zo superpozicie vysledkov vyseparujeme ten jeden ktory nas zaujima - tomu stale nerozumiem.

      • Re: Kvantové Počítače (part 1) 15.11.2007 | 20:56
        Avatar blackhole   Návštevník

        Ono je to v texte viac menej napisane. Presny postup po bodoch bohuzial neviem. V principe je to ale dalsia kvantova operacia na mnozine vysledkov prvej. len zistujes ktore z vysledkov su celociselne a robis to znova tak ze qubity su v stave superpozicie vsetkych vysledkov prveho algoritmu. a nechas zbehnut dalsi.

        • Re: Kvantové Počítače (part 1) 15.11.2007 | 21:03
          Avatar vid   Používateľ

          Aha, zhruba chapem.

          Bude tam aj nieco praktickejsie? lebo zatial si neviem predstavit ako vyzera taka operacia nad qubitmi, ktora nieco uzitocne robi, a este ovela menej ako vyzera ta finalna operacia ktora vyberie ten vysledok co nas zaujima.

          Na asmcommunity.net inac pisal jeden clovek ktory tvrdil ze je v tom teame co spravil ten 16qubit pocitac (asi si pocul), a ze programovanie pren je dost podobne Ccku.

          • Re: Re: Kvantové Počítače (part 1) 15.11.2007 | 21:11
            Avatar blackhole   Návštevník

            no v druhej casti bude praxe dost ale nie takej ako si asi predstavujes. druha cast bude venovana hlavne ako to v praxi funguje. budem hovorit o tom ze qubity su v reali reprezentovane atomami. ze ich stavy 0,1,superpozicia 0,1 su riesene ozarovanim atomu fotonami (pomocou laseru) a tym nabijeme atom vacsou energiou co ma za nasledok poskocenie elektronu o nejake spiny vyssie na vzdialenejsiu obeznu drahu a pod.... jednoducho kvantovy pocitac v praxi.

            samozrejme mozem spravit aj treti diel uz o konkretnych algoritmoch :)

            co sa tyka podobnosti s C. podla mojich informacii na programovanie algoritmov pre kvantovy pocitac potrebujes okrem rozhladu v programovacich jazykoch aj pomerne dobre znalosti vyssej matematiky a urcite vediet aspon tolko z kvantovej mechaniky kolko treba na uplne pochopenie spravania kvantoveho pocitaca. pokial sa ale bavime o programovani na highlevel urovni... potom to v podstate nemoze byt ine ako jeden z konvencnych pristupov programovania aky pozname. (ci uz proceduralne, objektove ci nieco haskeloidne...)

    • Re: Kvantové Počítače (part 1) 16.11.2007 | 21:26
      Avatar blackhole   Návštevník

      fajn clanok. Tieto clanky z kvantovej mechaniky sa mi pacia.

    • Re: Kvantové Počítače (part 1) 16.11.2007 | 22:08
      Avatar NeSHo   Používateľ

      Super článok moc sa mi to páčilo som to čítal cca. 4x aby som aspon dačomu rozumel ale zaujíma ma ďalšia časť určite si to prečítam.

    • Re: Kvantové Počítače (part 1) 17.11.2007 | 11:39
      Avatar Ripxter   Používateľ

      Skvely clanok ;) Celkovo ako vlastnosti dnes bezne vyuzivanych materialov na vyrobu chipov, pri neustalom zmensovani vyrobneho procesu (65nm sucastnost, 45nm penryn, 32nm az 10nm), zacnu narazat na fyzikalne hranice, tak prave kvantove PC su buducnost.
      --------------
      Chyby sú užitočné, musia byť však rýchlo objavené.

      Maynard Keynes

      ------------------------------------------ Predpoklad na úspech je v tom, že konáme to, čomu dobre rozumieme, nepomýšľajúc pritom na slávu --Henry Wadsworth Longfellow
    • Re: Kvantové Počítače #1 11.10.2011 | 21:20
      Avatar blackhole   Návštevník

      Prečital som si to a ani mäkkemu f nerozumien... snáď aspoň dačo pochopím v druhej časti...