Odpověď na názor

Ta bývá často zmiňována v souvislosti se simulací kvantového počítače na "normálním" počítači (z pohledu kvantové fyziky můžeme s jistou nadsázkou a humorem tvrdit, že "normální" počítač je vlastně zkolabovaný kvantový počítač - on se tak někdy i chová;-)).

Je asi dobré připomenout, že jádrem kvantového počítače není procesor, ale kvantový registr, který udržuje momentální stav výpočtu a jehož vývojem (popsáno jako lineární operace na příslušném stavovém prostoru) se provádí výpočet.

Vezměme si kvantový registr o 2 qubitech. Ten lze popsat Hilbertovým prostorem dimenze 2^2 = 4. Jeho bázové vektory můžeme označit jako |00>, |01>, |10> a |11> (symboly "|x> a <y|" patří do Diracovy ket-bra notace, která fyzikům umožňuje přehledný zápis určitých matematických operací a je tudíž v oblibě; zde je můžeme ignorovat jako zvláštní syntaktické značky). Libovolný stav, ve kterém se může náš registr během výpočtu nacházet, pak můžeme popsat jako lineární kombinaci bázových vektorů: R = a1|00> + a2|01> + a3|10> + a4|11>, kde ai jsou komplexní čísla. Dále platí, že pro každé ai, 1 <= i <= 4, odpovídá hodnota |ai|^2 pravděpodobnosti, že následující měření bude mít výsledek odpovídající i-tému bázovému vektoru. Například ve stavu R = sqrt(0.7)|00> + sqrt(0.1)(|01> + |10> + |11>) můžeme jako nejpravděpodobnější výsledek měření očekávat stav |00> (zde jsme se omezili na čistě reálné koeficienty v superpozici). Hodnoty |ai| se vůbec chovají podle míry pravděpodobnosti, čili například |a1|^2 + |a2|^2 + |a3|^2 + |a4|^2 = 1. Matematici proto někdy žertem nazývají kvantovou mechaniku jako "druhou odmocninu z teorie pravděpodobnosti".

Pokud chceme chování takového registru simulovat normálním počítačem, potom potřebujeme pro jeden přechod registru ze stavu Rj do R(j+1) upravit celkem 4 koeficienty v superpozici stavu. Přidáme-li další qubit, zjistíme, že těchto koeficientů je 2^3 = 8. Toto můžeme zobecnit do tvrzení, že n-qubitový registr lze popsat Hilbertovým prostorem dimenze 2^n. S rostoucím počtem qubitů nám tak exponenciálně stoupá složitost simulace.

Tuším, že to byl právě Richard P. Feynman, který si jako první blíže povšiml této zákonitosti a s intuicí jemu vlastní ho napadlo ji využít obráceně: Pokud na normálním počítači roste exponenciálně složitost simulace kvantového počítače, potom by mohly existovat exponenciálně složité úlohy, které jsou na kvantovém počítači řešitelné v polynomiálním čase. Čas dal tomuto vynikajícímu vědci za pravdu.

Tomáš Rosa