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:

$$\vert a\rangle \mapsto \frac{1}{\sqrt{q}} \sum_{c=0}^{q-1} \vert c\rangle e^{2 \pi i a c / q} .$$ (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:

$$\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 .$$ (16)

Abbildung: Ergebnis der Anwendung der DFT$_q$ für $n = 187, q = 804$