Hlavní navigace

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

Pavel Houser

V předešlém dílu našeho zamyšlení o matematických zajímavostech souvisejících s šifrováním jsme za zabývali především prvočísly a faktorizací. Nyní se dostaneme k oblíbené otázce týkající se vztahu NP úplných problémů k problémům s polynomiální složitostí a ke kvantovým počítačům. Ohrozí kvantové počítače metodu RSA či kryptografii?

Na úvod je vhodné sebekriticky zopakovat, že následující text není dílem profesionálního matematika ani kryptologa. Tento text navazuje na článek Jak dlouho nám vydrží dnešní šifrovací metody?.
Co je co

Faktorizace: Rozklad čísla na dvě prvočísla. Faktorizace čísla 15 znamená zjistit, že 15 = 3×5. Faktorizovat obrovská čísla je výpočetně náročné.

Výpočetní složitost: Závislost trvání výpočtu na velikosti vstupu. Ještě jinak – jak s růstem velikosti vstupu roste doba výpočtu. Problémy, jejichž výpočetní složitost roste se vstupem exponenciálně, se obecně pokládají za prakticky nezvládnutelné.

NP úplné problémy: Třída problémů, pro které není znám algoritmus řešící je v polynomiálně rostoucím čase (a všeobecně se předpokládá, že žádný takový algoritmus ani neexistuje). Pokud je ovšem nějaké řešení už známo, lze jeho platnost v polynomiálně rostoucím čase ověřit (do nedeterminismu a věštíren se nebudeme zaplétat). Do této třídy problémů spadá například obchodní cestující, splnitelnost či určení pravdivostní hodnoty logické formule. Jednotlivé NP úplné problémy jsou na sebe vzájemně převoditelné.

DNA počítač: Zařízení, v němž se výpočetní postupy realizují prostřednictvím toho, jak se jednotlivé molekuly DNA „hodí/párují“ k sobě.

Heuristika: Přibližný postup, jakási zkratka, nebo spíše intuitivní strategie, která s určitou pravděpodobností vede k řešení a má smysl tam, kde nelze použít rigoróznějších postupů (algoritmus není znám, byl by příliš pomalý apod.)

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

MIF17

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?

Anketa

Proč přestalo být o kvantové kryptografii v posledním roce slyšet?

Našli jste v článku chybu?