next up previous contents
Next: Kvantová Fourierova transformace Up: qc Previous: Univerzální kvantové brány   Obsah

Kvantové algoritmy

Kvantové počítače byly zpočátku brány jako zajímavá kuriozita, kterou snad bude jednou možné využít až technologie a výzkum postoupí patřičně kupředu. V 80.letech, kdy byly kvantovým počítačům položeny základy, se neobjevil žádný algoritmus, z něhož by bylo zřejmé, že budou kvantové počítače použitelné pro praktické řešení problémů. Hledaly se tedy možné oblasti využití kvantových počítačů, které by zahnaly pochybnosti. O zásadní průlom v konstrukci kvantových algoritmů se zasloužil v roce 1994 Peter Shor z AT&T, který navrhl algoritmus provádějící rozklad celého čísla na jeho prvočinitele. Nejlepší klasické algoritmy tuto úlohu dokáží řešit neefektivně v čase exponenciálně rostoucím s velikostí vstupu. Shorův algoritmus však běží v polynomiálním čase. Takové zlepšení si už zasloužilo větší analýzu a tak se na základě postupu jeho algoritmu začaly vynořovat další praktické algoritmy, které naplňovaly naděje o schopnostech kvantových počítačů. V této kapitole se seznámíme s nejdůležitějšími kvantovými algoritmy, které byly vyvinuty v 90.letech. Budeme také hovořit o jejich dopadu na některá odvětví informatiky jako je například kryptografie v případě Shorova faktorizačního algoritmu. Pokusíme se vždy vyjít z paralely klasického problému a poukázat na jednotlivé odlišnosti kvantového a klasického řešení. Abychom však mohli kvantové algoritmy popisovat, potřebujeme se na úvod seznámit s jedním z hlavních triků, kterým Shor (a později i další) svůj kvantový algoritmus vybavil.



Podkapitoly
next up previous contents
Next: Kvantová Fourierova transformace Up: qc Previous: Univerzální kvantové brány   Obsah
Bashar 2001-01-23