Obstojí výpočetní složitost před kvantovými počítači?

Začneme problémem NP úplných problémů versus P. Clayův matematický ústav zařadil tuto otázku mezi 7 největších matematických problémů současnosti – každá z těchto úloh je přitom oceněna milionem dolarů. „Tržní“ cena problému NP/P je ovšem nejspíš mnohem vyšší.

V dalším textu budeme opět vycházet především z knihy Keitha Devlina Problémy pro třetí tisíciletí, jejíž české vydání by se mělo objevit ještě během letošního podzimu. Důkaz, že NP úplné problémy jsou řešitelné v polynomiálním čase, by (přinejmenším potenciálně) otřásl metodou RSA, protože by zároveň přinášel důkaz, že v polynomiálním čase je řešitelná také faktorizace. Ale co víc – zatímco efektivní algoritmy speciálně pro faktorizaci by umožnily postavit nové šifrování třeba na asymetrii problému obchodního cestujícího (neexistuje důkaz, že faktorizace spadá mezi NP úplné problémy), důkaz, že NP úplné problémy jsou totožné s problémy složitosti P, by už podobnou možnost přestavby šifrovacích systémů neumožňoval.

Devlin se nicméně domnívá, že nakonec se podaří dokázat různost NP úplných problémů od třídy P. Dokonce tvrdí, že jde o jediný z velkých problémů současné matematiky, u kterého je alespoň teoreticky možné, že řešení objeví amatér (u ostatních na seznamu Clayova ústavu je pro amatéra už mnohdy nemožné vůbec v plné šíři porozumět zadání). Možná dokonce, že pro řešení NP/P postačí jen JEDINÁ nová myšlenka. Devlin přitom pokládá za nejnadějnější následující postup: Objevíte úlohu, k jejíž „vlastní podstatě“ patří nemožnost řešení v polynomiálním čase – a potom nějak dokážete její ekvivalenci s třídou NP úplných problémů. Devlin však přiznává, že sám tímto způsobem nepokročil vůbec nikam.

Podrobnosti o těchto Devlinových názorech lze dohledat v článku na Science Worldu, přičemž podstatně podnětnější než původní článek je následující diskuse.

Mimochodem – dvorní matematik Science Worldu vystupující v diskusích pod nickem Mefisto se naopak domnívá, že v případě problémů NP/P bude dokázána jeho nerozhodnutelnost. Stejný názor zastává matematik Ian Stewart ve svém příspěvku o budoucnosti matematiky, který vyšel ve sborníku Příštích padesát let (Stewartův text je online dostupný také zde). Na Science Worldu najdete k celému problému NP/P také anketu – hlasování je jistě adekvátní cestou k řešení matematických záhad :-).

A zcela na okraj – když už jsme se dostali k Ianu Stewartovi, v jeho knize Čísla přírody najdete i hezkou hříčku týkající se prvočísel, kterou jsem v minulém článku zapomněl zmínit. Jak jistě víte, prvočísla se vyskytují kolem násobků čísla 4 nebo násobků 6. Otázka zní – lemují je nějak přednostně shora, nebo zdola? (jinak řečeno, je v zadaném dostatečně velkém intervalu více prvočísel tvaru 4n-1 než 4n+1, respektive 6n-1 versus 6n+1?)

Nyní přejdeme k druhé části tohoto zamyšlení, tedy ke kvantovým počítačům. Faktorizace je na kvantovém počítači skutečně realizovatelná s polynomiální složitostí. Výklady o tom, že se tak děje kvůli tomu, že by kvantový výpočet probíhal v paralelních vesmírech, jsou ovšem poněkud přitažené za vlasy. V češtině existuje podle mých informací zřejmě pouze jediný srozumitelný text, který by vysvětloval, jak vlastně onen kvantový (Shorův) faktorizační algoritmus funguje. Pochází z knihy Zkratka napříč časem, přičemž úryvky vyšly opět na Science Worldu. Kromě vlastní faktorizace stojí snad za pozornost, že v textu najdete také vysvětlení, jak si vlastně představit kvantový Turingův stroj nebo kvantový celulární automat.

Kvantový počítač však prozatím teorií výpočetní složitosti neotřásl. I když pomineme potíže s faktickou realizací kvantových počítačů (nově zjištěné problémy se samovolnou ztrátou koherence jsou popsány např. v článku na serveru Osel), faktorizace na kvantovém počítači je tak efektivní díky drobnému fíglu při manipulaci s čísly v rámci hodinové aritmetiky pomocí Fourierovy transformace (asi nemá smysl si nic nalhávat – většina z nás už stejně beznadějně zapomněla, o co v této proceduře jde).

Shrnuto, Shorův algoritmus se opravdu hodí de facto pouze pro faktorizaci. Pro efektivní řešení NP úplných úloh na kvantovém počítači v tuto chvíli není známa žádná procedura efektivnější než klasické postupy. Z čehož, jak se zdá, vyplývá, že i eventuální masivní technologický pokrok při konstrukci kvantových počítačů by sice ohrozil metodu RSA, ne však asymetrickou kryptografii jako takovou.

Závěrečná poznámka ke vztahu kvantových efektů a šifrování. Před zhruba rokem se objevovalo velké množství článků o tom, že ta a ta banka nasazuje systém pro kvantovou kryptografii. Na spadnutí měly být systémy fungující nejen v optickém kabelu, ale i při přenosech vzduchem. Dokonce se objevily zprávy, že EU chystá s ohledem na americký systém Echelon v této oblasti vlastní gigantický projekt (PC World). Poté ale vše nějak usnulo a o kvantové kryptografii prakticky přestalo být slyšet. Máte také ten dojem?