Student World

***pravidelné páteční „přetištění“ staršího článku

Zjednodušená história výpočtov ukazuje, že zatiaľ čo výpočty boli v 19. storočí považované za mentálny proces ľudí, v 20. storočí už boli prevažne pokladané za proces strojov; všetko nasvedčuje tomu, že v 21. storočí budú výpočty procesy prislúchajúce prírode.
Kvantové počítače boli navrhnuté na začiatku 80. rokov 20. storočia a koncom tejto dekády bol ich návrh tiež formalizovaný. Veľké úsilie bolo v tejto oblasti vynaložené od začiatku 90. rokov, pretože sa ukázalo, že kvantové počítače budú pri riešení niektorých problémov výkonnejšie ako tie klasické. Existujú dobre známe algoritmy pre kvantové počítače, ako napríklad Shorov algoritmus na rozklad čísel na prvočísla a Groverov algoritmus na vyhľadávanie záznamov v databázach.
Výskum spájajúci evolučné algoritmy a kvantové výpočty začal na konci deväťdesiatych rokov. Vyvinuté algoritmy môžu byť rozdelené do dvoch skupín. V prvej skupine sú algoritmy pre kvantové počítače, zatiaľ čo v druhej skupine sú algoritmy pre klasické počítače, ktoré sú inšpirované kvantovými princípmi, ako sú interferencia, superpozícia a pozorovania kvantových stavov.
Kvantovo inšpirované evolučné algoritmy (skratkou QEA, z anglického qunatum-inspired evolutionary algorithms) patria práve do druhej zo spomínaných skupín. Sú to stochastické optimalizačné algoritmy, ktoré sa inšpirujú kvantovými javmi: superpozíciou stavov a reprezentáciou jednotky informácie pomocou kvantových bitov. Práve reprezentácia informácie je kľúčovým faktorom, na ktorom kvantovo inšpirované evolučné algoritmy stoja.
Zatiaľ čo v doteraz známych evolučných technikách (respektíve všeobecne v stochastických optimalizačných technikách, kam QEA patria) sa používalo kódovanie informácie binárnymi hodnotami, reálnymi číslami alebo symbolmi, kvantovo inšpirované evolučné algoritmy používajú pravdepodobnostné kódovanie. Najmenšou jednotkou informácie uloženej v dvojstavovom kvantovom počítači je kvantový bit, alebo skrátene qbit (z anglického quantum bit, k čomu ale pre úplnosť treba objasniť, že bit je skratka pre binary digit, t.j. pre binárnu číslicu).
Qbit môže byť v stave 0, v stave 1, ale na rozdiel od klasického bitu môže byť aj v ľubovoľnej superpozícii týchto stavov. Konkrétny stav qbitu sa reprezentuje dvojicou dvoch komplexných čísel, ktorých druhá mocnina modulu dáva pravdepodobnosti, že kvantový bit bude pozorovaný v stave 0 alebo v stave 1.
Pre vysvetlenie poslednej formulácie je treba vysvetliť inšpiráciu spomínanej reprezentácie v kvantovej mechanike. Zvyčajne si laici i fyzici predstavujú elektrón ako miniatúrnu záporne nabitú guľôčku obiehajúcu okolo jadra atómu po určitých dráhach, ale keďže ide o pohybujúcu sa guľôčku, vždy je možné povedať, že sa táto guľôčka – elektrón – nachádza na nejakom konkrétnom mieste. Laici celkom prirodzene toto vysvetlenie prijímajú a v mnohom celkom dobre vyhovuje aj fyzikom, i keď títo vedia, že skutočnosť taká ideálna nie je: nikdy nie je možné polohu elektrónu určiť presne, možno iba určiť miesto, kde sa pravdepodobne nachádza.
Werner Heinsenberg odvodil, že presný stav sa nikdy nedá pozorovať; buď sa uspokojíme s nepresnou informáciou o polohe elektrónu, a naše meranie stav elektrónu neovplyvní, alebo sa pokúsime zmerať polohu elektrónu veľmi presne, ale naše meranie tak silno naruší stav meranej sústavy, že stav po meraní vôbec nezodpovedá stavu pred meraním, a teda „presný“ výsledok merania je k ničomu, pretože po meraní už neplatí.
Uvedený princíp sa nazýva Heinsenbergov princíp neurčitosti. V reprezentácii informácii pomocou kvantových bitov sa prejavuje tak, že zatiaľ čo qbit môže byť v ľubovoľnej superpozícii stavov 0 a 1, t.j. môže sa nachádzať v jednom z nekonečného množstva možných stavov, v momente, keď je kvantový bit pozorovaný, skolabuje do jedného zo stavov 0 a 1. Qbit, hoci sa nachádza v jednom z nekonečného množstva stavov, je pozorovaný iba v jednom konkrétnom stave. Tento stav však nie je možné predvídať pred pozorovaním; jediný spôsob, ako ho zistiť, je pozorovanie vykonať.
V klasických evolučných optimalizačných technikách sa používajú variačné operátory mutácie a kríženia. Variačné operátory v kvantovo inšpirovaných evolučných algoritmoch musia byť vzhľadom na reprezentáciu jednotky informácie pomocou qbitov iné. I tieto operátory sú prebrané z kvantových výpočtov. Jedná sa o takzvané kvantové hradlá (anglicky quantum gates).
Hoci existuje viacero kvantových hradiel používaných alebo uvažovaných v kvantových počítačoch, v kvantovo inšpirovaných evolučných algoritmoch sa používa iba operátor NOT (ktorý si možno predstaviť ako negáciu kvantového stavu qbitu, kedy sa vymenia pravdepodobnosti jeho pozorovania v stave 1 a v stave 0), a takzvané rotačné hradlo (anglicky rotation gate). Práve rotačnému hradlu vďačia kvantovo inšpirované evolučné algoritmy za svoje optimalizačné schopnosti. Mení totiž pravdepodobnosti pozorovania qbitu v stave 0 alebo 1 takým spôsobom, aby s väčšou pravdepodobnosťou bol tento kvantový bit pozorovaný práve v tom stave, ktorý sa javí ako výhodnejší, t.j. je ohodnotený lepšou hodnotou funkcie vhodnosti.
Kvantovo inšpirované evolučné algoritmy boli úspešne použité na riešenie ťažkých kombinatorických úloh. Za zmienku stojí napríklad alokácia miesta na disku na uloženie súborov. Pravdepodobnostná reprezentácia informácie v QEA však nie je úplne nová myšlienka, ako to prezentujú autori QEA Jong-Hwan Kim a jeho študent Kuk-Hyun Han. Rovnakú pravdepodobnostnú reprezentáciu jedinca i narábanie s touto reprezentáciou používa už mnoho rokov jeden známy stochastický optimalizačný algoritmus (horolezecký algoritmus s učením – anglicky hillclimbing with learnig, HCwL). Tento algoritmus vzišiel z úplne opačného konca stochastických optimalizačných techník, dá sa povedať, že s toho najprimitívnejšieho. Jeho znovuobjavenie úplne inou cestou – od zložitých a vysoko sofistikovaných evolučných techník a kvantových výpočtov – potvrdzuje jeho použiteľnosť pre technické problémy.
Určite bude zaujímavé sledovať, aká budúcnosť postretne kvantovo inšpirované evolučné algoritmy; možno sa dočkajú slávy najskôr v akademickej obci a neskôr aj v praktickom nasadení, alebo sa stanú len jedným z mnohých pokusov „robiť veci inak“. Nakoľko však sú kvantovo inšpirované evolučné algoritmy zatiaľ iba komplikovanou interpretáciou jednoduchého horolezeckého algoritmu s učením – i keď nepochybne interpretáciou veľmi zaujímavou – predpovedám im druhú z načrtnutých verzií vývoja. Technická prax potrebuje dobre fungujúce a jasne formalizovateľné nástroje, nie zložité metafory.

autor Jozef Babjak