Auswertung des Ergebnisses der DFT

Als letzten Schritt in unserem Quantencomputer messen wir nun den gewonnen Zustand unseres Systems (eigentlich würde es genügen, $\vert c\rangle$ zu messen, wir messen aber jetzt $\vert c\rangle$ und $\vert x^a \bmod q\rangle$), und rechnen danach klassisch weiter.

Die diskrete Fouriertransformation wird bei diesem Algorithmus dazu benötigt, die Periode im Funktionsgraphen der modularen Exponentation zu ermitteln, die unserer gesuchten Ordnung $r$ entspricht. Dabei wird praktisch der ,,Offset`` $k$ eines erhaltenen Wertes $f(k+br)$ ausgelöscht und die Periode finden wir in der gemessenen Amplitude wieder (allerdings als Kehrwert und mit einem Faktor versehen), zusätzlich tritt eine Phasenverschiebung auf, da wir aber sowieso nur die Amplitude messen, können wir diese ignorieren.

Die Wahrscheinlichkeit, einen bestimmten Zustand $\vert c\rangle$ und $\vert x^k \bmod n\rangle$ ($0 \leq k < r$) zu beobachten, beträgt:

$$\left\vert \frac{1}{q} \sum_{a:x^a \equiv x^k} e^{2 \pi i a c / q}\right\vert^2 .$$ (17)

Da $x$ nun aber die Ordnung $r$ besitzt, können wir diese Summe umschreiben, indem wir $a = b r + k$ setzen und erhalten:

$$\left\vert \frac{1}{q} \sum_{b=0}^{\lfloor(q-k-1)/r\rfloor} e^{2 \pi i (br+k) c / q}\right\vert^2 .$$ (18)

Wir können nun $\vert e^{2 \pi i k c / q}\vert = 1$ ausklammern und $r c$ durch $r c \bmod q$ ersetzen, wobei dieser Rest noch so ,,verschoben`` wird, daß er im Intervall $(-q/2,q/2]$ liegt, wir schreiben dafür $\{r c\}_q$ und erhalten

$$\left\vert \frac{1}{q} \sum_{b=0}^{\lfloor(q-k-1)/r\rfloor} e^{2 \pi i b \{r c\}_q / q}\right\vert^2 .$$ (19)

Die Summe können wir nun als Integral schreiben ([Heu98] Eulersche Summenformel) und gewinnen daraus

$$\frac{1}{q} \int \limits_{b=0}^{\lfloor(q-k-1)/r\rfloor} e^{... ...or(q-k-1)/r\rfloor}{q} (e^{2 \pi i \{r c\}_q / q} - 1)\right).$$ (20)

Wenn $\vert\{r c\}_q\vert \leq r/2$ (dies ist unabhängig von $k$!) ist obiger Fehlerterm durch $O(1/q)$ beschränkt und das Integral, also die Wahrscheinlichkeit den Zustand $\vert c, x^k \bmod n\rangle$ zu messen, ist groß. Dies kann man sich z.B. am komplexen Einheitskreis veranschaulichen, falls die einzelnen Amplituden ungefähr in die gleiche Richtung ,,zeigen``, ergibt sich eine Verstärkung.

Wenn wir nun in dem Integral $u = r b / q$ substituieren, erhalten wir

$$\frac{1}{r} \int \limits_{0}^{\lfloor(q-k-1)/r\rfloor r/q} e^{2 \pi i \frac{\{r c\}_q}{r} u} du .$$ (21)

Nun können wir, da $k < r$, mit einem Fehler von nur $O(1/q)$ die obere Grenze des Integrals durch $1$ ersetzen und bekommen

$$\frac{1}{r} \int \limits_{0}^{1} e^{2 \pi i \frac{\{r c\}_q}{r} u} du .$$ (22)

$\{r c\}_q/r$ ist im Intervall $[-\frac{1}{2},\frac{1}{2}]$, der Betrag des Integral wird also für $\{r c\}_q/r = \pm \frac{1}{2}$ minimal und beträgt $2/(\pi r)$. Der Betrag dieser Größe ist eine untere Schranke für die Wahrscheinlichkeit, einen bestimmten Zustand mit $\{r c\}_q \leq r/2$ zu beobachten, deswegen ist diese asymptotisch durch $4/(\pi^2 r^2)$ beschränkt und für genügend große $n$ mindestens $1/3r^2$.

Abbildung 5: Wahrscheinlichkeit $c$ zu beobachten, $q = 256$, $r=10$ ([Sho97])

Die Wahrscheinlichkeit $\vert c, x^k \bmod n\rangle$ zu messen, beträgt also mindestens $1/3r^2$, falls

$$-\frac{r}{2} \leq rc \bmod q \leq \frac{r}{2},$$ (23)

d.h. wenn gilt

$$\exists d: -\frac{r}{2} \leq rc - dq \leq \frac{r}{2} .$$ (24)

Daraus erhalten wir:

$$\left\vert\frac{c}{q}-\frac{d}{r}\right\vert \leq \frac{1}{2q} ,$$ (25)

wobei wir $c$ und $q$ kennen.

Würde $r$ nun $q$ teilen, erhielten wir somit direkt unsere gesuchte Ordnung $r$. Dies ist allerdings im allgemeinen nicht der Fall, wir können aber über einen kleinen Umweg trotzdem $r$ ermitteln, indem wir die sogenannte Kettenbruchentwicklung anwenden.

Da zu Beginn $q > n^2$ gewählt wurde, gibt es höchstens einen Bruch $d/r$ mit $r < n$, der obige Bedingung erfüllt. Wir erhalten diesen Bruch vollständig gekürzt, indem wir $c/q$ auf den nächsten Bruch runden, der einen Nenner kleiner als $n$ hat. Dieser Bruch kann mittels Kettenbruchentwicklung von $c/q$ effizient gefunden werden.

Ein (endlicher, einfacher) Kettenbruch ist ein Ausdruck der Form

$$a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\cdots + \frac{1}{a_N}}}}}$$ (26)

mit $a_0, \ldots, a_N \in \mathbbm{N}\cup \{0\}$. Jede positive rationale Zahl kann durch einen Kettenbruch dargestellt werden, der wie folgt berechnet wird: Sei $a_0 = \lfloor x \rfloor$ und $x = a_0 + \xi_0$ für ein $\xi_0 \in [0,1)$. Wenn $\xi_0 \neq 0$ dann sei $a_1 = \lfloor 1/\xi_0 \rfloor$ und $1/\xi_0 = a_1 + \xi_1$ für ein $\xi_1 \in [0,1)$ usw. Bei rationalem $x$ terminiert dieser Prozeß und wir erhalten die $a_i$ der Kettenbruchentwicklung (vgl. [EJ94], [Knu97] Analyse des Euklidischen Algorithmus).

Ist $d$ nun teilerfremd zu $r$, erhalten wir damit $r$ (wir bekommen durch die Kettenbruchentwicklung einen vollständig gekürzten Bruch). Es gibt $\phi(r)$ mögliche Werte von $d$ teilerfremd zu $r$ ( $\phi(m) := \vert\{k \in \{1, \ldots, m\} : {\mathrm{ggT}}(k, m) = 1\}\vert$ ist die Eulersche $\phi$-Funktion, die die Anzahl der zu $m$ teilerfremden Zahlen angibt). Jeder dieser Brüche $d/r$ ist nahe an einem Bruch $c/q$ mit $\vert c/q-d/r\vert \leq 1/2q$. Es gibt zudem r mögliche Werte für $x^k$, da $r$ die Ordnung von $x$ ist.

Da jeder dieser Zustände mit einer Wahrscheinlichkeit von mindestens $1/3r^2$ auftritt, erhalten wir $r$ mit einer Wahrscheinlichkeit größer oder gleich $\phi(r)/3r$. Wenn wir nun ausnutzen, daß $\phi(r)/r > \delta/\log \log r$ für eine Konstante $\delta$ ist (siehe [HW79], zitiert in [Sho97] und [EJ94]), müssen wir das Experiment also nur $O(\log \log r)$ mal wiederholen, um $r$ mit einer hohen Wahrscheinlichkeit zu erhalten.

Dies kann in der Praxis noch weiter verbessert werden, indem bei gemessenem $\vert c\rangle$ auch noch Zahlen nahe an $c$ wie $c \pm 1, c \pm 2, \ldots$ ausprobiert werden, da auch diese noch eine einigermaßen hohe Wahrscheinlichkeit haben, nahe an einem Bruch $qd/r$ zu sein.

Außerdem kann man die Rechnung nicht nur mit einem Kandidaten $r'$ für $r$, sondern, da der Bruch $c/q$ ja vollständig gekürzt zu $d'/r'$ vorliegt, auch für $2r', 3r', \ldots$ durchführen, ob diese Werte vielleicht die Ordnung von $x$ sind. Weiterhin ist es auch noch möglich, daß man, wenn man zwei Kandidaten für $r$ gefunden hat, das kleinste gemeinsame Vielfache dieser beiden Werte ausprobiert, auch dadurch lassen sich die Versuche auf dem Quantencomputer reduzieren, so daß man zwar mehr klassische Nachbearbeitung braucht, aber der schwierig zu realisierende Quantencomputer nur wirklich da eingesetzt wird, wo er unbedingt benötigt wird.