Sciencemag.cz
Doporučujeme
Oblíbený problém pro testování efektivity různých algoritmů představují pozice na velkých šachovnicích; jedná se totiž o typ úloh, kdy výpočetní složitost roste s velikostí šachovnice obvykle exponenciálně. Problém se řeší prohledáváním stavového prostoru (backtracking)
V problému šachových dam máme za úkol umístit na šachovnici určitý počet dam tak, aby se vzájemně nenapadaly. Na klasické šachovnici může být dam logicky maximálně 8 (ani věží by se sem nedalo postavit víc), a ty zde lze umístit 92 způsoby. Základních pozic je 12, další získáme jejich symetriemi (1 z nich nemá 8 symetrií, proto celkový počet není 96, ale 8 x 11 + 4). Kolika způsoby lze postavit N dam na šachovnici N x N? Obecný vzorce nikdo nenašel, na šachovnici 25 x 25 jde o více než 2 miliardy pozic a nebylo vůbec lehké se k tomu výsledku dopočítat hrubou silou. Navíc si úlohu můžeme různě upravovat, třeba zakázat umístění dámy na určité diagonále, nebo na šachovnici již určitý počet dam postavit předem. S trochou práce lze najít úlohy, kdy už ve verzi 21 x 21 nedokážeme vyřešit v rozumném čase.
Vědci z University of Innsbruck nyní uvádějí, že právě na tomto problému se dá dobře demonstrovat nadřazenost kvantového počítače (quantum supremacy) nad počítači klasickými. Autoři výzkumu za tímto účelem navrhli „kvantovou šachovnici“, tedy optickou mřížku tvořenou laserovými paprsky. Dámy jsou pak představovány jednotlivými atomy. Interakce mezi jednotlivými atomy nyní můžeme naprogramovat tak, aby byly obdobou potřebného chování dam (tj. 2 atomy se „napadají“, jsou-li na stejné řadě, sloupci nebo diagonále). Atomy jsou z neplatných pozic od sebe odpuzovány. Optické rezonátory – 2 sady zrcadel nad a pod optickou mřížkou – generují toto chování i přes celý prostor šachovnice a zároveň zajišťují, že atomy-dámy se i posouvají. Jde vlastně o obdobu prohledávání stavového prostoru.
Samo o sobě jde v tomto případě o analogový, nikoliv kvantový počítač, v roli atomů by mohly vystupovat třeba odpuzující se koule kulečníku. Tímhle způsobem bychom se samozřejmě řešení nikdy nedopočítali. Je-li systém silně ochlazen, mohou ale mezi atomy vzniknout provázané stavy a kvantové počítač pak prochází (jak se obvykle uvádí) všechny možnosti najednou, atomy se nacházejí ve všech možných stavech současně atd. (Poznámka PH: Není jasné, zda současná technika umožňuje provázání všech dam, tj. všech qubitů, ale teoreticky to možné je.)
Zajímavá na tom má být ještě jedna věc. Z toho, jaké světlo vychází nakonec ze zrcadel, lze určit, zda upravená úloha (třeba s podmínkou prázdných diagonál apod.) má vůbec řešení. To ale ještě neznamená, že takové řešení známe. K tomu by bylo potřeba přečíst pozici jednotlivých dam pomocí atomové mikroskopie (Poznámka PH: A to možná ne jednou, protože při kolapsu vlnové funkce může být výsledným stavem leccos, ne nutně vyhovující řešení úlohy. Navíc asi vůbec nezjistíme, kolik takových řešení existuje.)
Faktem ovšem je, že autoři výzkumu neprovedli žádný výpočet na kvantovém počítači při nízké teplotě, nadřazenost kvantového algoritmu zde odvozují z jeho simulace na počítači klasickém. Což samo o sobě pro tento typ úloh ani nepřekvapuje.
A Quantum N-Queens Solver
Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner
Qauntum, 2019-06-03, volume 3, page 149
https://doi.org/10.22331/q-2019-06-03-149
Zdroj: Eurekalert.org a další
Problém osmi dam na Wikipedia.cz
