next up previous contents
Nächste Seite: Auswertung des Ergebnisses der Aufwärts: Realisierung beim Quantencomputer Vorherige Seite: Modulare Exponentation   Inhalt

DFT$_q$

Als nächsten wichtigen Schritt führen wir nun die diskrete Fouriertransformation $\bmod\ q$ auf unserem ersten Register aus, die $a$ ($0 \leq a < q$) wie folgt abbildet:

\begin{displaymath}
\vert a\rangle \mapsto \frac{1}{\sqrt{q}} \sum_{c=0}^{q-1} \vert c\rangle
e^{2 \pi i a c / q} .
\end{displaymath} (15)

Das heißt, wir wenden die unitäre Abbildung auf $a$ an, die der Matrix mit den $(a, c)$-Einträgen $\frac{1}{\sqrt{q}} e^{2\pi i a c /
q}$ entspricht. Diese Transformation ist auf einem Quantencomputer effizient durchführbar ( $\mathrm{DFT}_{2^n}$ in $O(n^2)$ möglich, im Gegensatz dazu benötigt man dabei auf einem klassischen Computer mittels der Fast Fourier Transformation $O(2^n n)$ Schritte) und Thema eines eigenen Vortrages.

Wir erhalten nun den folgenden Zustand:

\begin{displaymath}
\frac{1}{q} \sum_{a=0}^{q-1} \sum_{c=0}^{q-1} e^{2 \pi i a c / q} \vert c\rangle \vert x^a \bmod n\rangle .
\end{displaymath} (16)

Abbildung: Ergebnis der Anwendung der DFT$_q$ für $n = 187, q = 804$
\includegraphics {shorklein.png}



Stefan Röhrich stefan@roehri.ch
1999-11-27 19:52:04