Kvantový algoritmus pro faktorizaci

Nejlepší dnes známý klasický algoritmus pro faktorizaci (rozklad na prvočinitele) vyžaduje počet elementárních operací rostoucí (asymptoticky) s délkou vstupu L jako exp[L^1/3]. Kvantový algoritmus zvládá faktorizaci v polynomiálním čase (P. Shor, 1994).

Poznámka: Pro jednotlivé kroky existují dokonce i rychlejší algoritmy. Např. pro násobení nebo DFT.

Vraťme se teď stručně k otázce, jak konkrétní operace realizovat pomocí elementárních kvantových hradel pospojovaných do kvantových obvodů. Příkladem budiž realizace kvantové diskrétní Fourierovy transformace.