Google PageRank na kvantovém počítači

Tým vědců z řady institucí publikoval ve Physical Review Letters článek o tom, že Google PageRank by šel na kvantovém počítači sestavit efektivněji.
Celé tvrzení je třeba vysvětlit hned z několika pohledů. Především, vědci nezkonstruovali žádný fyzický kvantový počítač, ale navrhli pouze kvantový algoritmus; asi jako známe kvantový algoritmus Shorův (pro faktorizaci) nebo Groverův (pro seřazení databáze). Ačkoliv zdrojový článek vlastně nepopisuje, co tedy „algoritmus pro PageRank“ přesně dělá, mělo by asi jít hlavně o práci s maticemi.
Google PageRank je způsob, jak přiřadit webové stránce koeficient určující její relativní významnost (i když ono „Page“ se primárně neodvozuje od stránky, ale od jména autora algoritmu, spoluzakladatele Googlu L. Pagea). Algoritmus se inspiruje tím, jak se ve vědeckém světě stanovují různé citační a publikační indexy. Webová stránka je tím významnější, čím více jiných stránek na ni odkazuje, a to samozřejmě v závislosti na tom, jak jsou významné tyto stránky.
Jak se zdá, nemáme jak začít počítat, protože ke zjištění hodnoty stránky bychom potřebovali znát hodnoty jiných stránek atd. Úlohu lze řešit buď jako soustavu rovnic o obrovském počtu neznámých (matice bude mít tolik řádků a sloupců, kolik je počítaných stránek). Prakticky je asi jednodušší pracovat s iterací, na počátku přiřadit všem stránkám třeba stejné koeficienty a pak začít přepočítávat a po každém kroku zkontrolovat, zda jsme se přiblížili dostatečně (tj. zda se výsledky nezměnily už jen neznatelně). To každopádně dělá i Google. Nový výpočet PageRanku se provádí jako přepočet toho předešlého.
Matematika, která za tím vším stojí, je poměrně složitá. Ze samotného zadání nijak nevyplývá, zda úloha vůbec má nějaké řešení, zda nemá více řešení, zda iterační postup konverguje a navíc konverguje v rozumném čase atd. Je třeba nějak korigovat „kapsy“, tj. místa na Internetu, která odkazují samy na sebe, ale už ne nikam ven, a podobných komplikací původního jednoduchého modelu je víc, včetně toho, že majitelé stránek se pokoušení algoritmus různě přechytračit. Realita ovšem ukazuje, že Google PageRank sestavit dokáže.
Každopádně – výpočet Google PageRank je podle všeho jeden z nejsložitějších výpočetních procesů, které se dnes provádějí. Google jej přitom realizuje „v cloudu“, takže úlohu je navíc třeba efektivně distribuovat/paralelizovat. Jak tahle kouzla provádět s maticemi o miliardách řádků, to je mnohem cennější know-how než samotný algoritmus (který v rozporu s častým tvrzením není tajný, ale byl téměř celý publikován).
Protože obsah Internetu dále roste, bude i pro Google možná obtížné držet s tímto trendem krok. Efektivní kvantový algoritmus je proto zajímavá věc, byť sám o sobě je samozřejmě k ničemu.
Jeden z autorů výzkumu Daniel Lidar z University of Southern California vysvětluje, že vědci provedli pouze simulaci na tisících stránek. Z ní vyplynulo, že kvantový algoritmus by výsledky vracel rychleji a s tím, jak poroste počet stránek, se jeho výhoda proti algoritmu klasickému bude ještě zvyšovat. Exponenciální urychlení proti klasickému algoritmu by měl ten kvantový dávat i při odpovědi na otázku, zda pro danou stránku je třeba PageRank vůbec přepočítávat...
Zdroj: Phys.org

Poznámka: PageRank není ovšem jediným algoritmem, jímž Google hodnotí významnost stránek.