Staré a nové problémy v matematice

Matematiku si nelze představit bez problémů. I k získání doktorátu musíte vyřešit alespoň malý problém. Největšího ocenění se dočká ten, kdo vyřeší slavný starý problém. Ale nejde jen o soutěž matematiků, také teorie se hodnotí podle toho, jaké problémy umožní vyřešit. K nejkrásnějším výsledkům pak patří řešení problémů založená na vybudování nové teorie. Jistěže nejde vždy jenom o problémy; je samozřejmě neméně důležité, zda výsledek, či matematická teorie pomůže jiné vědecké disciplíně, popřípadě přímo v životě. Nicméně pro matematika i vědecky zaměřeného laika jsou slavné problémy nejzajímavější téma.

Snad vůbec nejproslulejší problém je tzv. Fermatova věta (nebo také Velká Fermatova věta, popř. Poslední Fermatova věta), která čekala na své řešení víc než 350 let.

Může si problém podstatně mladší získat srovnatelnou proslulost? Vlastně není zas tak překvapivé, že je to možné; pokud se problém týká nějakých zcela fundamentálních pojmů, jeho věk nemůže být podstatný. Např. slavná Riemannova hypotéza byla formulována až v 19. století, ale vzhledem k tomu, že implikuje řešení mnoha dalších dílčích problémů, je často považována za důležitější tvrzení než Fermatova věta. Názory na to, co je nejdůležitější problém, se samozřejmě různí. Fermatova věta sice nemá zajímavé důsledky, ale je to problém, který ovlivnil nejvíce matematických oborů.

"

A co novější problémy? Nových problémů je mnoho; ten, kterým se zde chci zabývat, je považován za nejdůležitější problém v informatice. Je jenom asi čtvrt století starý a zatím není tak slavný jako uvedené dva problémy z teorie čísel, ale jeho význam si uvědomuje stále více matematiků. Problém vznikl v teoretické informatice v době, kdy se klasičtí matematici na tuto disciplínu dívali s despektem jako na obor, kde se dají "dobře prodávat lacino získané výsledky". Doba se změnila a např. na zmíněném posledním matematickém kongresu byla z tohoto oboru jedna plenární přednáška a pět přednášek v sekci "Matematické aspekty informatiky". Navíc Nevanlinnova cena za výsledky z teoretické informatiky byla udělena na kongresu současně s Fieldsovými medailemi, které zastupují chybějící Nobelovu cenu za matematiku. Všechny tyto přednášky, kromě snad jedné, i dílo, za které byla udělena Nevanlinnova cena, s tímto problémem nějak přímo souvisely.

Každý problém, na který je jednoznačná odpověď ano či ne, se dá pomocí vhodné definice formulovat jako otázka rovnosti dvou tříd. To platí i o slavném problému, označovaném "P = NP?", který se týká složitosti výpočtů.

Nejdříve si však uveďme několik příkladů otázek na složitost výpočtů. Jeden z nejznámějších takových problémů je otázka, kolik aritmetických operací je potřeba na vynásobení dvou matic n×n. Pokud násobíme matice podle definice, potřebujeme, kromě jiného, alespoň n³ operací násobení (pro každý prvek výsledné matice potřebujeme provést n násobení). Roku 1969 Volker Strassen nalezl poměrně jednoduchý algoritmus, který potřebuje pouze const.n^2,80... operací. Podstatně složitějšími metodami se později postupně podařilo snížit počet operací až na const.n^2,37... Naopak pouze víme, že je potřeba alespoň n² operací, protože potřebujeme alespoň jednu operaci pro každý prvek výsledné matice. Nikdo neumí zatím zlepšit tento triviální dolní odhad.

Další důležitý problém je složitost rozkladu přirozených čísel v součin. Chceme-li najít vlastního dělitele čísla N, stačí vyzkoušet čísla menší nebo rovná √N, protože pokud je N složené číslo, má dělitele alespoň jednoho ≤ √N. Pokud budeme uvažovat algoritmy, které používají náhodné generátory, lze pomocí složitějších algoritmů najít dělitele v průměru rychleji. Přesto i nejlepší algoritmy jsou schopny rozkládat čísla s počtem cifer jen o málo větším než 100. S rozkladem čísel souvisí testování, zda je dané číslo prvočíslo. Tato úloha je však podstatně lehčí, protože stačí testovat některé příznaky prvočísel, aniž bychom zkoušeli dělitele.

Následující úloha je poněkud jiného druhu. Máme dáno n bodů v rovině a náš úkol je najít nejkratší čáru, která vychází z nějakého z nich, prochází všemi dalšími body a vrací se do výchozího bodu.¹⁾ Tato úloha se nazývá příznačně úloha obchodního cestujícího. Název naznačuje jednu možnou aplikaci (i když ve skutečnosti se pro tento účel asi sotva používá), další najdeme všude, kde je potřeba vykonávat činnost na různých místech a je potřeba minimalizovat časové ztráty spojené s přesuny z místa na místo. Typické příklady jsou sběr odpadků ve městě a vrtání děr do čipů. To, co nás zajímá, není řešení jednoho konkrétního případu, ale chceme najít rychlý algoritmus pro všechny možné případy. Protože se takový algoritmus nedaří najít, domníváme se, že neexistuje, ale zatím to neumíme dokázat.

Pojem algoritmu byl matematicky formalizován až ve třicátých letech tohoto století. Už zpočátku bylo zřejmé, že pro praktické účely není zcela adekvátní. Podle definice je úloha algoritmicky řešitelná, když existuje postup, který po konečném počtu kroků dá správnou odpověď. Nicméně "konečný počet" může být z praktického hlediska téměř nekonečný. Např. algoritmus založený na vyzkoušení všech dělitelů 100ciferného čísla N, i kdybychom zkoušeli jen dělitele menší než √N, by potřeboval zhruba 10^√50 kroků. Zatímco 100ciferná čísla lze, pokud máme dost trpělivosti, sčítat a násobit i na papíře a na počítači proběhnou tyto operace ve zlomcích sekund, není množství 10^√50 operací myslitelné ani při jakémkoliv zlepšení technologie. Protože s praktickými výpočty bylo málo zkušeností, nebylo jasné, kde stanovit hranici mezi uskutečnitelným a neuskutečnitelným. V sedmdesátých letech se informatika již bouřlivě rozvíjela a představy o této hranici vykrystalizovaly k zásadnímu rozlišení: úlohy, u nichž počet elementárních kroků potřebných k řešení při daných vstupních datech roste (v závislosti na velikosti těchto dat) způsobem, který lze omezit nějakou polynomiální funkcí (např. n³), a úlohy, u nichž má tento růst exponenciální charakter (odpovídá např. funkci 3ⁿ).

Základní důvod pro toto rozlišení je, že pro "obvyklé" exponenciální funkce dostáváme extrémně velké hodnoty již pro malé argumenty, zatímco pro "obvyklé" polynomiální funkce tomu tak není. Pro konkrétní algoritmy v praxi dostáváme v naprosté většině právě takovéto funkce, tedy skutečně to funguje. Existuje ale ještě další dobré zdůvodnění. Představme si, že při současné technologii můžeme řešit úlohy, které vyžadují nanejvýše zhruba t kroků. Mějme např. nějaké dvě úlohy A a B, pro A stačí n² kroků, B vyžaduje 2ⁿ kroků pro vstupní data velikosti n. Můžeme tedy zpracovávat data velikosti √t pro A a nanejvýš velikosti log₂t pro B. Je zřejmé, že √t roste podstatně rychleji než log₂t, ale zajímavější je následující pozorování. Pokud se technologie zlepší tak, že místo t budeme mít k dispozici řekněme 4t, budeme moci zpracovat data dvakrát větší pro A, ale jen o 2 větší pro B! Tedy pro takto exponenciální úlohy máme poměrně ostrou hranici, kam až můžeme jít. Konkrétně např. pro hledání rozkladu čísel: jestliže s dnešními algoritmy umíme rozkládat 120ciferná čísla, můžeme doufat, že se dostaneme se zlepšením technologie k 130ciferným až 140ciferným, ale 200ciferná čísla nerozložíme, pokud nenajdeme lepší algoritmy.

Můžeme uvést další praktické důvody pro tuto hranici, ale pro mnoho matematiků (včetně autora tohoto článku) je možná důležitější, že je s tím spojen zajímavý a těžký matematický problém. Pro mnoho úloh máme totiž jen exponenciální algoritmy a rádi bychom věděli, jestli pro ně existují algoritmy polynomiální. Dva takové problémy jsme popsali nahoře, rozklad čísel a úlohu obchodního cestujícího; podobných problémů byly popsány stovky.

Problém "P = NP?" je otázka po rovnosti dvou tříd problémů. První třída, P, je třída problémů, pro které existují polynomiální algoritmy (algoritmy s počtem kroků omezeným nějakým polynomem v závislosti na velikosti vstupu). Definovat třídu NP je poněkud obtížnější. Zhruba řečeno, daný problém náleží do třídy NP, když jeho řešení lze ověřit (tedy nikoliv vypočíst) v polynomiálním počtu kroků.

Většina běžně používaných algoritmů pracuje v polynomiálním čase. Např. algoritmy pro základní aritmetické operace, které se učíme ve škole, jsou v podstatě polynomiální. Další příklady jsou Eukleidův algoritmus pro největšího společného dělitele dvou přirozených čísel a Gaussova eliminační metoda řešení soustavy lineárních rovnic. Toto sice nejsou rozhodovací úlohy, ale snadno z nich takové vyrobíme. Důležitá rozhodovací úloha, kterou můžeme takto dostat, zní, zda daná soustava lineárních rovnic má řešení. Tato rozhodovací úloha má polynomiální algoritmus, protože takové systémy rovnic umíme dokonce vyřešit v polynomiálním čase. Formálně tedy říkáme: množina systémů lineárních rovnic, které mají řešení, náleží do třídy P.

Příkladem množiny v NP jsou složená čísla. Pro složené číslo N je libovolný vlastní dělitel M certifikátem náležení do množiny složených čísel (viz rámeček). M je jistě nejvýše polynomiálně delší než N (je dokonce kratší, protože je menší než N). Obvyklý algoritmus pro dělení se zbytkem vyžaduje pouze polynomiální čas, takže se takto můžeme přesvědčit, že M je skutečně certifikátem.

Množinu A ∈ NP si můžeme představovat jako množinu, u níž sice nemusíme umět snadno rozhodovat, zda do ní nějaký prvek náleží, ale když už nám někdo, kdo má nadpřirozené schopnosti, nějaký prvek z A nabídne, snadno si ověříme, že je opravdu prvkem A. (V případě, že nenáleží do A, je to horší, protože v definici NP nepožadujeme certifikáty pro "nenáležení".)

Všimněme si, že z definice NP úlohy vyplývá, že každá taková úloha má exponenciální algoritmus. Nechť např. jsou certifikáty kódovány posloupnostmi nul a jedniček a nechť je jejich délka omezena polynomem n². Potom můžeme rozhodnout, zda x ∈ A, pro x délky n tak, že probereme všech 2ⁿ²⁺¹ - 1 možností pro potenciální certifikáty. (Algoritmus probírání všech možností se nazývá příhodně algoritmus Britského muzea, protože v Britském muzeu v Londýně najdeme odpověď na každou otázku, pokud máme dost času a trpělivosti.) Problém "P = NP" můžeme tedy parafrázovat jako problém, zda se lze vyhnout zdlouhavému probírání všech možností.

Naše praktické životní zkušenosti nám říkají, že se tomu vyhnout nelze. Když zapomeneme, kam jsme dali knížku, nezbývá nám než prohledat všechny police knihovny. Tento intuitivní argument ale není dobrý. Vezměme si zase jako příklad problém najít dělitele čísla N (to sice není pouze rozhodovací úloha, ale - jak uvidíme dále - to nevadí). Pokud je N dáno, jsou dělitelé jednoznačně určeni a nemůžeme se na vlastnost býti dělitelem dívat jako na náhodnou vlastnost.

Než postoupíme dále, musíme vyjasnit vztah mezi rozhodovacími a vyhledávacími úlohami. Z našich příkladů jsou vyhledávací úlohy úloha o rozkladu čísla a úloha o obchodním cestujícím. Z úlohy o rozkladu čísla utvoříme rozhodovací úlohu následovně. Jako vstupní data budeme uvažovat dvojici čísel N, i a otázka bude: existuje vlastní dělitel M čísla N, který má na i-tém místě binárního zápisu jedničku? Je snadné ukázat, že tyto dvě úlohy jsou ekvivalentní v tom smyslu, že pokud máme polynomiální algoritmus pro jednu, potom máme polynomiální algoritmus i pro druhou. Podobně dostaneme ekvivalentní úlohu pro obchodního cestujícího tak, že se nebudeme ptát po nejkratší cestě, ale pouze zda existuje cesta kratší než nějaké zadané číslo k. Obě tyto rozhodovací úlohy jsou příklady množin v NP. Např. triviálně každá cesta kratší než k je certifikátem toho, že existuje cesta kratší než k. To ukazuje, že se při formulaci problémů, jako je "P = NP?", můžeme bez újmy na obecnosti omezit na rozhodovací úlohy.

Třída NP má ještě jednu pozoruhodnou vlastnost. V této třídě existují v určitém smyslu nejtěžší úlohy, které nazýváme NP-úplné. Jsou to takové úlohy, na které se dá libovolná jiná převést polynomiálním algoritmem. Tudíž pokud by existoval polynomiální algoritmus pro jednu NP-úplnou úlohu, existoval by také pro libovolnou úlohu z NP, tj. bylo by P = NP. Poznamenejme, že NP-úplné úlohy nejsou žádná vzácnost, naopak bylo nalezeno několik stovek přirozeně definovatelných různých NP-úplných úloh. Typickou takovou úlohou je právě rozhodovací úloha, kterou dostaneme z úlohy obchodního cestujícího. Úloha obchodního cestujícího patří do skupiny, které říkáme optimalizační úlohy. Jak název naznačuje, jsou to úlohy, kde máme zadánu množinu možných řešení a pro každé řešení nějaké číslo, které udává "kvalitu" tohoto řešení. Cílem je najít optimální řešení. Kdyby platilo P = NP, potom bychom měli polynomiální algoritmy pro všechny tyto úlohy. Problém, zda P = NP, však zůstává nadále otevřený.

Složitost a kryptografie

Jednou z nejzajímavějších aplikací teorie složitosti je kryptografie. Konkrétněji jde o tzv. veřejné kódovací klíče. Představme si, že máme nějaký podnik, který od svých zákazníků potřebuje získávat informace. Obvykle je nežádoucí, aby posílané zprávy byly přístupné jinému zákazníkovi nebo cizí osobě. Proto podnik přidělí každému zákazníkovi svůj kódovací klíč. To se dá vyřešit fyzickým kontaktem se zákazníkem, popřípadě poštou (jak se to děje u PIN pro platební karty). Uvažujme ale situaci, kde je jediný kontakt zprostředkován počítačovou sítí. Potom kódovací klíče nelze dost dobře utajit. Myšlenka veřejného kódovacího klíče je založena na pozorování, že dekódování může být zásadně jiná operace než kódování, tudíž nemusí vadit, že kódovací klíč není utajen, pokud se z něho nedá odvodit dekódovací klíč.²⁾

Základní podmínkou dobrého kódování je použití náhodného procesu při generování klíče. Schematicky vypadá systém veřejného klíče takto. Máme funkce F, G, E, D, které se dají snadno vyčíslit. Funkce F a G slouží k tomu, abychom z náhodného čísla r vypočítali kódovací klíč e = F(r) a dekódovací klíč d = G(r). Daná zpráva x se zakóduje pomocí funkce E a kódovacího klíče e na y = E(e, x) a dekóduje pomocí funkce D a dekódovacího klíče d, takže x = D (d, y). Protože takových systémů není mnoho, musíme předpokládat, že protivník zná funkce F, G, E, D. Dále předpokládáme, že se dozví i e, ale d bude utajeno. Samozřejmě, že potom musíme utajit také r (to vlastně už nepotřebujeme a můžeme ho zničit).

Kritické místo takového systému je funkce F. Jde o to, že nesmí být možné z funkční hodnoty e odvodit argument r, pro který e = F (r). Jakmile má protivník r, může spočítat d pomocí G. Tedy F musí být dosti zvláštní funkce: vypočítat funkční hodnotu má být snadné, ale vypočítat argument funkce z funkční hodnoty musí být složité. Takové funkce se nazývají jednosměrné. (Předpokládáme, že x a F (x) mají přibližně stejnou délku; potom se samozřejmě x dá z F (x) určit algoritmem Britského muzea, ale to vyžaduje exponenciálně mnoho kroků.)

Nejdůležitější ze systémů veřejných klíčů je RSA (akronym podle autorů: Rivest, Shamir, Adleman). V tomto systému se náhodně volí dvě prvočísla p_l a p₂; součástí klíčů je jejich součin N. Nebudeme zabíhat do detailů, podstatné je to, že ze znalosti p_l, p₂ a kódovacího klíče e lze snadno vypočítat dekódovací klíč d (viz J. Adámek: Šifrování pomocí velkých prvočísel, Vesmír 71, 615, 1992/11). ). Z toho plyne, že základním předpokladem spolehlivosti systému je nemožnost snadného rozkladu čísla N v součin.

V teorii složitosti definujeme jednosměrné funkce pomocí pojmu polynomiálního času. Navíc ještě umožňujeme používat generátor náhodných čísel. Je jen několik málo konkrétních funkcí, o kterých se domníváme, že jsou jednosměrné. Většina z nich přímo nebo nepřímo předpokládá, že rozklad čísel v součin je těžký. Jak jsme se už zmínili, neumíme dokázat, že nelze rozkládat čísla polynomiálním algoritmem. Existuje tedy vůbec nějaká jednosměrná funkce? Toto je také otevřený problém. Je to asi problém ještě těžší než "P = NP? ", protože platí: když existují jednosměrné funkce, potom P ≠ NP. Kdybychom tedy chtěli mít kryptografii bez nedokázaných předpokladů, museli bychom dokázat tvrzení, které je pravděpodobně silnější než že P ≠ NP.

Veřejné klíče se skutečně používají. Jejich bezpečnost je založena jen na znalosti toho, jaké jsou v současné době nejlepší algoritmy na rozklad čísel a na další úlohy, na nichž jsou klíče založeny. I když to zní poněkud paradoxně, právě proto je potřeba se zabývat algoritmy na rozklad čísel. V roce 1993 se uskutečnil zajímavý experiment. Arjen Lenstra z laboratoří BELCORE (Morristown, USA) zorganizoval akci na rozklad 129místného čísla. Byl to pokus o rozklad dosud největšího čísla, o kterém nebylo nic zvláštního známo, kromě toho, že je součinem dvou prvočísel. Do akce se zapojilo více než 600 dobrovolníků z dvaceti čtyř zemí spojených sítí INTERNET. Výhodou algoritmů na rozklad je, že se dají dobře paralelizovat, tj. rozdělit na mnoho dílčích úkolů, které se mohou zpracovávat nezávisle na sobě. Každý z účastníků projektu dostal část těchto úkolů a výsledky byly shromažďovány na MIT (Cambridge, USA). Nakonec byla získaná data předána do BELCORE, zpracována na superpočítači a rozklad byl nalezen. Dělitelé jsou dvě čísla, jedno 64místné a druhé 65místné.

Chcete-li mít představu, jak taková čísla vypadají, napište si náhodně 129 číslic atd. Pokud si přece jenom chcete zkusit násobit na svém počítači 64místná a 65místná čísla, nebo věříte v mystiku velkých čísel, zde je nalezený rozklad:

3 490 529 510 847 650 949147 849 619 903 898133 417 764 638 493 387 843 990 820 577 x

32 769132 993 266 709 549 961988190 834 461413177 642 967 992 942 539 798 288 533 =

114 381625 757 888 867 669 235 779 976146 612 010 218 296 721242 362 562 561842 935 706 935 245 733 897 830 597123 563 958 705 058 989 075147 599 290 026 879 543 541.

129místné číslo vymysleli autoři RSA systému r. 1977 a použili ho k zakódování zprávy. Rozluštění této zprávy byla výzva pro matematiky zabývající se základy kryptografie.

Jak to spolu souvisí?

Vidíme, že jsou jakési souvislosti teorie čísel s teorií složitosti. Není to ale přesto zbytečný luxus věnovat tolik lidského úsilí na řešení problému, jako je Fermatova věta, když je spousta mnohem praktičtějších problémů? Toto je obvyklá diskuse mezi teoretiky a praktiky. Praktici říkají, že je škoda, že se nejlepší mozky zabývají problémy, které nám nejsou k ničemu, zatímco je mnoho problémů, jejichž řešení by nám přineslo bezprostřední užitek. Teoretici namítají, že teorie nepřináší užitek bezprostředně, ale později, a potom mnohem více než takové dílčí výsledky. Hlavně ovšem nejde o to, abychom vyráběli více a více, spotřebovávali více a více atd., ale spíše o to, abychom byli vzdělanější, lépe poznali přírodu a svět.

Podíváme-li se blíže na konkrétní problémy, zjistíme, že i tak abstraktní věci, jako Fermatova věta či Riemannova hypotéza, souvisejí s takovými praktickými problémy, jako jsou veřejné kódovací klíče. Vezměme si třeba důkaz Fermatovy věty. To, co vlastně Wiles dokázal, je jakási věta o eliptických křivkách.³⁾ Na druhé straně jeden z nejúčinnějších algoritmů pro rozklad čísel je založen také na eliptických křivkách. Podstata vědeckého pokroku tedy není v tom, že víme, že Fermatova věta platí, nebo že máme další algoritmus pro rozklad čísel, ale v teorii eliptických křivek.

Eliptická křivka je zadána rovnicí

y² = x³ + ax + b.

Význam eliptických křivek spočívá v tom, že pokud jsou splněny určité obecné předpoklady, na takových křivkách lze kanonickým způsobem definovat grupovou operaci.

Souvislost s Riemannovou hypotézou je méně překvapivá. Je to tvrzení, které umožňuje získat informaci o prvočíslech a prvočísla jsou základem současné kryptografie. Konkrétněji, pro systém RSA potřebujeme zvolit náhodně dvě velká prvočísla. To můžeme udělat např. tak, že budeme náhodně generovat čísla určité velikosti a testovat, zda jsou prvočísla. Existují účinné pravděpodobnostní algoritmy na testování prvočíselnosti. To v praxi stačí, nicméně bychom rádi věděli, jestli existuje algoritmus, který rozhodne, zda číslo je prvočíslo v polynomiálním čase bez použití náhodných čísel, tj. zda množina prvočísel je v P. Tento problém je také otevřený a souvisí s Riemannovou hypotézou. G. L. Miller dokázal, že takový algoritmus existuje, pokud platí jisté zobecnění Riemannovy hypotézy (nazývané prostě zobecněná Riemannova hypotéza).

Kvantové počítače

O nejnovější překvapení v teorii složitosti se postarali zcela nečekaně fyzici. David Deutsch z Oxfordské univerzity se zabýval otázkou, zda lze výpočetně simulovat fyzikální systémy, a při tom navrhl nový výpočetní prostředek, který nazval kvantový Turingův stroj. Turingův stroj je standardní zjednodušený matematický model počítače. Protože zde nepotřebujeme přesnou definici, budeme prostě mluvit o kvantovém počítači.

Pro ty, kteří nic nevědí o kvantové teorii, vysvětlíme kvantovou interferenci na příkladě. Uvažujme následující pokus se světelným paprskem a zrcadly. Máme dvě obyčejná zrcadla a dvě polopropustná. Polopropustné zrcadlo propustí 50 % světla jako čiré sklo a 50 % odrazí jako zrcadlo (samozřejmě, že je to idealizace, zanedbání pohlcování světla však pro náš pokus není podstatné. Zrcadla jsou umístěna přesně do vrcholů obdélníka, zdroj světla míří ve směru hrany čtverce na polopropustné zrcadlo, viz obrázek.

Když se paprsek dostane na polopropustné zrcadlo, polovina světla bude pokračovat dále přímo a polovina světla se odrazí kolmo dolů. V dalších dvou rozích jsou umístěna obyčejná zrcadla, která odrazí oba paprsky do zbylého vrcholu. Podle klasických představ by se zde oba paprsky měly ještě dále rozpůlit, takže v každém ze dvou směrů by mělo nakonec pokračovat 25 % + 25 % = 50 % světla. Ve skutečnosti zjistíme světlo jen ve směru rovnoběžném s původním!

Pokud si světlo představujeme jako vlnění, můžeme to snadno vysvětlit interferencí: v kolmém směru se vlny vyruší, v rovnoběžném se sečtou. Představme si však, že zdroj světla zeslabíme natolik, že bude vydávat jednotlivá světelná kvanta - fotony - jeden za druhým s dostatečným časovým odstupem. O tom, že jde skutečně o jednotlivé fotony, se můžeme přesvědčit nějakým detektorem, např. citlivým fotografickým filmem. V každém bodě dráhy zachytíme buď celý foton, nebo nic. To platí i o bodech dráhy mezi polopropustnými zrcadly! Foton se tedy na polopropustném zrcadle nerozpůlí, ale s pravděpodobností 1/2 pokračuje přímo a s pravděpodobností 1/2 se odrazí do kolmého směru. Přesto za druhým zrcadlem detegujeme fotony pouze v jednom směru.

Řešení, které podává kvantová fyzika, je založeno na tom, že výskytu fotonu v určitém místě přiřadíme jakési číslo, nazývané amplituda, ze kterého lze spočítat pravděpodobnost výskytu fotonu v tomto místě, ale které se chová trochu jinak než pravděpodobnost. Amplitudy nejsou pouze reálná čísla mezi nulou a jedničkou, ale obecná komplexní čísla. Speciálně dvě taková čísla mohou mít opačná znaménka, čímž se při sčítání vyruší; to u čísel udávajících pravděpodobnosti není možné, protože jsou vždy nezáporná. Pravděpodobnost se z amplitudy vypočítá jako kvadrát absolutní hodnoty.

Kvantový počítač by měl právě takové jevy využívat. Představme si, že máme vyhledávací úlohu, kde bychom museli normálně prohledat exponenciálně mnoho možností. Kvantový počítač nemusí tyto možnosti probírat sekvenčně; místo toho se jeho výpočet rychle rozvětví do exponenciálně mnoha možností, podobně jako se foton rozdvojil na polopropustném zrcadle. Například když vyšleme n fotonů současně do n polopropustných zrcadel. Po průletu zrcadly budeme mít z klasického hlediska 2n možných stavů dané soustavy. Z hlediska kvantové teorie bude soustava v jakési superpozici těchto stavů. Podobným způsobem se může rozvětvit do exponenciálně mnoha stavů i klasický počítač, který používá zdroj náhodných čísel. U klasického počítače však nemůžeme eliminovat pravděpodobnost neúspěšných pokusů ve prospěch úspěšných, což právě kvantové počítače mohou využít. Uvedený příklad se zrcadly sice nic nepočítá, ale ukazuje, jak by se mohl rozvětvený výpočet zase spojit v jeden.

Samozřejmě, že to není tak jednoduché. Řešený problém musí mít dosti speciální strukturu, aby se kvantová interference dala využít. Model kvantového počítače byl navržen r. 1985, ale teprve zhruba před rokem Peter Shor nalezl kvantové polynomiální algoritmy pro řešení konkrétních problémů, pro které nejsou známy klasické polynomiální algoritmy (viz [6]). Jde právě o dva problémy, jejichž složitost se využívá ve veřejných kódovacích klíčích. Jeden z nich je nám už dobře známý problém rozkladu přirozených čísel. Kvantovým počítačem tedy lze rozkládat složená čísla v součin v polynomiálním čase a v důsledku toho také např. rozbít nejpopulárnější kryptosystém RSA.

Zatím nikdo kvantový počítač nesestrojil, je to jenom teoretický model. Nikdo také nedokázal, že kvantové stroje umějí něco lépe než klasické, protože zatím neumíme vyloučit, že rozklad čísel se dá počítat v polynomiálním čase i na obyčejných počítačích. Problém, zda "kvantové" P je různé od klasického P, se jen zařadil do fronty beznadějných problémů v teorii složitosti. Kdyby se však kvantový počítač podařilo sestrojit, potom v každém případě s ním padne téměř celá současná kryptografie.

Lze tedy skutečně sestrojit kvantový počítač? To už není matematický problém, přenechme ho raději fyzikům.