Kvantová Fourierova transformace

Jak známo, Fourierova transformace mapuje funkce v časové doméně na funkce frekvenčního spektra. Její hlavní vlastností z pohledu kvantové mechaniky je, že mezi qubity vyvolává kvantovou interferenci, která je buď konstruktivní nebo destruktivní. Konstruktivní interference v signálu zvýrazňuje jisté charakteristiky (frekvence) nad charakteristikami jinými. Takovým způsobem uvádí registr do stavu, v němž naměříme jeho hodnoty s různými pravděpodobnostmi (tzn. ovlivňuje amplitudy pravděpodobností). A právě tato vlastnost má zásadní vliv na praktickou použitelnost některých algoritmů. Abychom vyhověli požadavku unitárnosti operace definujeme kvantovou diskrétní Fourierovu transformaci (KFT) jako vývoj registru $\vert a\rangle = \vert a_0\ a_1 \ldots\rangle$ na $\vert c\rangle = \vert c_0\ c_1 \ldots\rangle$ podle :

$$\vert a\rangle \rightarrow \frac{1}{\sqrt{q}} \sum_{c=0}^{q-1}{e^{2\pi iac/q}}\ \vert c\rangle,$$

kde $q$ je počet stavů registru ($0 \le a < q$) a $(a,c)$ jsou souřadnice prvků unitární matice a jsou rovny $\frac{1}{\sqrt{q}} e^{2\pi iac/q}$. Tato matice (transformace) je základem faktorizačního algoritmu a nazývá se $\textbf{\textit{A}$_q$}$. Její sloupce a řádky jsou indexovány od nuly jako celá čísla odpovídající binárním reprezentacím stavů. Aby bylo možné navrhnout efektivní algoritmy založené na KFT, bylo nutné samotnou KFT vymyslet efektivně. Shor takovou KFT navrhl pro $q$, které je mocninou dvou ($q = 2^l$). Pro její výpočet potřeboval jen ${\cal O}(l^2)$ kvantových bran, kterých jsou dva typy. Jednou je Hadamardova brána definovaná jako:

$$\begin{array}{cccc} \textbf{\textit{H}}: & \vert\rangle & \r... ...ft( \begin{array}{cc} 1 & 1 \\ 1 & -1 \\ \end{array}\right) .$$

Tato brána vyvíjí stav $\vert\rangle$ do vyvážené superpozice všech možných $2^n$ stavů (pokud je aplikována na $n$ qubitů jako $(\textbf{\textit{H}} \otimes \textbf{\textit{H}} \otimes \ldots \otimes \textbf{\textit{H}})\ \vert0 \ldots 0\rangle$ nazývá se Walsh-Hadamardova transformace W). Hadamardovu bránu ovlivňující bit na pozici $j$ označujeme $\textbf{\textit{H$_j$}}$. Druhou použitou bránou je $\textbf{\textit{S$_{j,k}$}}$, která operuje s bity na pozicích $j$ a $k$:

$$\textbf{\textit{S$_{j,k}$}} = \left( \begin{array}{cccc} 1 &... ...& 0 \\ 0 & 0 & 0 & e^{i \theta_{k-j}} \\ \end{array}\right),$$

kde $\theta_{k-j} = \pi / 2^{k-j}$. K provedení KFT aplikujeme brány v pořadí zleva doprava podle obecného schématu:

$$\textbf{\textit{H$_{l-1}$}} \textbf{\textit{S$_{l-2,l-1}$}} ... ..._{0,2}$}} \textbf{\textit{S$_{0,1}$}} \textbf{\textit{H$_0$}} .$$

Například pro tři bity ($l = 3$) aplikujeme brány $\textbf{\textit{H$_2$}} \textbf{\textit{S$_{1,2}$}} \textbf{\textit{H$_1$}} \textbf{\textit{S$_{0,2}$}} \textbf{\textit{S$_{0,1}$}} \textbf{\textit{H$_0$}} .$ Tato operace vrací registr bitově převrácený, takže pro dokončení KFT je zapotřebí výsledný registr bitově invertovat nebo jej číst z opačné strany, což je již z hlediska implementace jednoduchá operace.

Obrázek: Obvod kvantové Fourierovy transformace: pro $l = 3$; rekurzivně lze obvod rozšiřovat podle obecného vzorce. Jak je u kvantových obvodů zvykem, brány se provádějí zleva doprava, což odpovídá uvedenému zápisu. Lze si rovněž všimnout jak brány S$_{j,k}$ operují nad dvěma qubity.