Shor-Algorithmus

Nun werden wir uns dem Problem der ganzzahligen Faktorisierung zuwenden und sehen, wie es auf einem Quantencomputer mithilfe von Phasenschätzung effizient gelöst werden kann. Der Algorithmus, den wir erhalten werden, ist der Shor'sche Algorithmus zur ganzzahligen Faktorisierung. Shor hat seinen Algorithmus nicht speziell im Hinblick auf die Phasenabschätzung beschrieben, aber es ist ein natürlicher und intuitiver Weg, um zu erklären, wie er funktioniert.

Wir werden zunächst ein Zwischenproblem erörtern, das so genannte Ordnungsfindungsproblem, und sehen, wie die Phasenschätzung eine Lösung für dieses Problem bietet. Wir werden dann sehen, wie eine effiziente Lösung des Ordnungsfindungsproblems eine effiziente Lösung des ganzzahligen Faktorisierungsproblems ergibt. (Wenn die Lösung eines Problems eine Lösung für ein anderes Problem dieser Art liefert, sagt man, dass das zweite Problem auf das erste reduziert wird - in diesem Fall reduzieren wir also die ganzzahlige Faktorisierung auf die Ordnungsfindung) Dieser zweite Teil von Shors Algorithmus macht überhaupt keinen Gebrauch von Quantencomputern; er ist völlig klassisch. Das Quantencomputing wird nur zur Lösung der Auftragsfindung benötigt.

---

Das Problem der Auftragsfindung

Einige Grundlagen der Zahlentheorie

Um das Problem der Ordnungsfindung zu erklären und zu zeigen, wie es mit Hilfe der Phasenschätzung gelöst werden kann, ist es hilfreich, mit einigen grundlegenden Konzepten der Zahlentheorie zu beginnen und nebenbei einige praktische Notationen einzuführen.

Zunächst definieren wir für jede beliebige positive ganze Zahl $N$ die Menge $\mathbb{Z}_N$ wie folgt.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Zum Beispiel, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ und so weiter.

Das sind zwar Zahlenmengen, aber wir können sie als mehr als nur Mengen betrachten. Insbesondere können wir uns arithmetische Operationen auf $\mathbb{Z}_N$ vorstellen, wie beispielsweise Addition und Multiplikation – und wenn wir uns darauf einigen, unsere Ergebnisse immer modulo $N$ zu betrachten (das heißt, durch $N$ zu dividieren und den Rest als Ergebnis zu nehmen), bleiben wir bei der Durchführung dieser Operationen stets innerhalb dieser Menge. Die beiden spezifischen Rechenoperationen Addition und Multiplikation, jeweils modulo $N$, machen $\mathbb{Z}_N$ zu einem Ring, der in der Algebra eine grundlegend wichtige Objektart darstellt.

Beispielsweise sind $3$ und $5$ Teilelemente von $\mathbb{Z}_7$, und wenn wir sie miteinander multiplizieren, erhalten wir $3\cdot 5 = 15$, was bei der Division durch $7$ den Rest $1$ ergibt. Manchmal drücken wir dies wie folgt aus.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Wir können aber auch einfach „ $3 \cdot 5 = 1$ “ schreiben, vorausgesetzt, es ist klar, dass wir mit „ $\mathbb{Z}_7$ “ arbeiten – einfach, um unsere Notation so einfach wie möglich zu halten.

Als Beispiel sind hier die Additions- und Multiplikationstabellen für $\mathbb{Z}_6$ aufgeführt.

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Unter den Elementen $N$ der Menge $\mathbb{Z}_N$ sind die Elemente $a\in\mathbb{Z}_N$, die die Bedingung $\gcd(a,N) = 1$ erfüllen, besonders. Häufig wird die Menge, die diese Elemente enthält, wie folgt mit einem Stern gekennzeichnet.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Wenn wir unsere Aufmerksamkeit auf die Multiplikationsoperation richten, bildet die Menge $\mathbb{Z}_N^{\ast}$ eine Gruppe – genauer gesagt eine abelsche Gruppe –, die eine weitere wichtige Objektart in der Algebra darstellt. Es ist eine grundlegende Eigenschaft dieser Mengen (und endlicher Gruppen im Allgemeinen), dass wir, wenn wir ein beliebiges Element $a\in\mathbb{Z}_N^{\ast}$ wählen und $a$ wiederholt mit sich selbst multiplizieren, letztendlich immer die Zahl $1$ erhalten.

Nehmen wir als erstes Beispiel „ $N=6$ “. Wir haben, dass „ $5\in\mathbb{Z}_6^{\ast}$ “, da „ $\gcd(5,6) = 1$ “ gilt, und wenn wir „ $5$ “ mit sich selbst multiplizieren, erhalten wir „ $1$ “, wie die obige Tabelle bestätigt.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Als zweites Beispiel nehmen wir $N = 21$. Wenn wir die Zahlen von $0$ bis $20$ durchgehen, sind diejenigen, deren GCD gleich $1$ mit $21$ ist, wie folgt.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Für jedes dieser Elemente ist es möglich, diese Zahl mit einer positiven ganzzahligen Potenz zu potenzieren, um „ $1$ “ zu erhalten. Hier sind die kleinsten Potenzen, bei denen dies funktioniert:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Natürlich arbeiten wir mit $\mathbb{Z}_{21}$ für alle diese Gleichungen, die wir nicht schreiben müssen - wir nehmen sie als implizit an, um die Dinge nicht zu überladen. Das werden wir auch im weiteren Verlauf der Lektion tun.

Problemstellung und Zusammenhang mit der Phasenschätzung

Nun können wir das Problem der Auftragsfindung formulieren.

Eingabe: positive ganze Zahlen $N$ und $a$, die erfüllen $\gcd(N,a) = 1$\ Ausgabe: die kleinste positive ganze Zahl $r$, die $a^r \equiv 1$ $(\textrm{mod } N)$

Alternativ, in der oben eingeführten Notation, sei gegeben: „ $a \in \mathbb{Z}_N^{\ast}$ “, und wir suchen die kleinste positive ganze Zahl „ $r$ “, sodass „ $a^r = 1$ “ gilt. Diese Zahl „ $r$ “ wird als Ordnung von „ $a$ “ modulo „ $N$ “ bezeichnet.

Um das Problem der Ordnungsfindung mit der Phasenschätzung zu verknüpfen, betrachten wir die auf einem System definierte Operation, deren klassische Zustände den $\mathbb{Z}_N$ entsprechen, wobei wir mit einem festen Element $a\in\mathbb{Z}_N^{\ast}$ multiplizieren.

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

Um es klar zu sagen: Wir führen die Multiplikation in „ $\mathbb{Z}_N$ “ durch, daher ist implizit, dass wir das Produkt modulo „ $N$ “ innerhalb des Kets auf der rechten Seite der Gleichung berechnen.

Nehmen wir beispielsweise $N = 15$ und $a=2$; dann ist die Wirkung von $M_2$ auf die Standardbasis $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ wie folgt.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Dies ist eine unitäre Operation, vorausgesetzt, dass $\gcd(a,N)=1$ gilt; sie mischt die Elemente der Standardbasis $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$, sodass es sich bei der Matrix um eine Permutationsmatrix handelt. Aus der Definition geht hervor, dass diese Operation deterministisch ist. Eine einfache Möglichkeit, zu erkennen, dass sie invertierbar ist, besteht darin, die Ordnung $r$ von $a$ modulo $N$ zu betrachten und zu erkennen, dass die Inverse von $M_a$ gleich $M_a^{r-1}$ ist.

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Es gibt noch eine andere Möglichkeit, sich die Umkehrfunktion vorzustellen, für die man keinerlei Kenntnisse über „ $r$ “ benötigt (was schließlich das ist, was wir berechnen wollen). Für jedes Element $a\in\mathbb{Z}_N^{\ast}$ gibt es immer ein eindeutiges Element $b\in\mathbb{Z}_N^{\ast}$, das die Bedingung $ab=1$ erfüllt. Wir bezeichnen dieses Element $b$ mit $a^{-1}$, und es lässt sich effizient berechnen; eine Erweiterung des GCD-Algorithmus von Euklid erledigt dies mit einem Aufwand, der quadratisch in $\operatorname{lg}(N)$ ist. Und somit

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Die Operation $M_a$ ist also sowohl deterministisch als auch invertierbar. Das bedeutet, dass sie durch eine Permutationsmatrix beschrieben wird und daher unitär ist.

Betrachten wir nun die Eigenvektoren und Eigenwerte der Operation $M_a$ unter der Annahme, dass $a\in\mathbb{Z}_N^{\ast}$ gilt. Wie gerade dargelegt, besagt diese Annahme, dass $M_a$ unitär ist.

Es gibt $N$ Eigenwerte von $M_a$, wobei derselbe Eigenwert möglicherweise mehrfach vorkommt, und im Allgemeinen besteht eine gewisse Freiheit bei der Auswahl der entsprechenden Eigenvektoren – aber wir müssen uns nicht um alle Möglichkeiten kümmern. Fangen wir ganz einfach an und bestimmen wir nur einen Eigenvektor von $M_a$.

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Die Zahl $r$ ist die Ordnung von $a$ modulo $N$ – hier und im gesamten weiteren Verlauf dieser Lektion. Der zu diesem Eigenvektor gehörende Eigenwert ist $1$, da er sich bei Multiplikation mit $a$ nicht ändert.

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Dies geschieht, weil $a^r = 1$ gilt, sodass jeder Standardbasiszustand $\vert a^k \rangle$ bei $k\leq r-1$ zu $\vert a^{k+1} \rangle$ verschoben wird und $\vert a^{r-1} \rangle$ wieder zu $\vert 1\rangle$ zurückverschoben wird. Vereinfacht ausgedrückt ist es so, als würden wir $\vert \psi_0 \rangle$ langsam umrühren, aber da es bereits vollständig durchgerührt ist, ändert sich nichts.

Hier ist ein weiteres Beispiel für einen Eigenvektor von $M_a$. Dieses Beispiel ist im Zusammenhang mit der Ordnungsbestimmung und der Phasenschätzung besonders interessant.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Alternativ kann man diesen Vektor auch durch Summation wie folgt schreiben.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Hier taucht die komplexe Zahl $\omega_r = e^{2\pi i/r}$ auf natürliche Weise auf, was darauf zurückzuführen ist, wie die Multiplikation mit $a$ modulo $N$ funktioniert. Diesmal lautet der entsprechende Eigenwert $\omega_r$. Um dies zu verdeutlichen, können wir zunächst folgende Berechnung durchführen.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Da nun gilt: „ $\omega_r^{-r} = 1 = \omega_r^0$ “ und „ $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$ “, ergibt sich, dass

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

Also $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$.

Mit derselben Argumentation können wir weitere Eigenvektor-Eigenwert-Paare für $M_a$ bestimmen. Für jede Wahl von $j\in\{0,\ldots,r-1\}$ gilt:

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

ist ein Eigenvektor von $M_a$, dessen zugehöriger Eigenwert $\omega_r^j$ ist.

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Es gibt noch weitere Eigenvektoren von $M_a$, aber wir brauchen uns damit nicht zu befassen – wir konzentrieren uns ausschließlich auf die Eigenvektoren $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$, die wir gerade ermittelt haben.

---

Ordnungsfindung durch Phasenschätzung

Um das Problem der Reihenfolgesuche für eine gegebene Wahl von $a\in\mathbb{Z}_N^{\ast}$ zu lösen, können wir das Verfahren zur Phasenschätzung auf die Operation $M_a$ anwenden.

Dazu müssen wir nicht nur $M_a$ effizient mit einem Quantenschaltkreis umsetzen, sondern auch $M_a^2$, $M_a^4$, $M_a^8$ und so weiter – und zwar so weit wie nötig, um aus dem Phasenschätzungsverfahren eine ausreichend genaue Schätzung zu erhalten. Hier werden wir erläutern, wie das gemacht werden kann, und später werden wir genau herausfinden, wie viel Genauigkeit erforderlich ist.

Beginnen wir zunächst mit der Operation „ $M_a$ “ an sich. Da wir mit dem Quantenschaltkreismodell arbeiten, verwenden wir natürlich die Binärschreibweise, um die Zahlen zwischen $0$ und $N-1$ zu kodieren. Die größte Zahl, die wir kodieren müssen, ist $N-1$, daher beträgt die Anzahl der benötigten Bits

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Wenn beispielsweise $N = 21$ gilt, erhalten wir $n = \operatorname{lg}(N-1) = 5$. So sieht die Kodierung der Elemente von $\mathbb{Z}_{21}$ als binäre Zeichenketten der Länge $5$ aus.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

Und hier ist eine genaue Definition, wie $M_a$ als $n$ -qubit Operation definiert ist.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

Der Punkt ist: Obwohl uns nur interessiert, wie $M_a$ für $\vert 0\rangle,\ldots,\vert N-1\rangle$ funktioniert, müssen wir dennoch festlegen, wie es für die übrigen $2^n - N$ Standardbasiszustände funktioniert – und zwar so, dass wir weiterhin eine unitäre Operation erhalten. Dies wird erreicht, indem man „ $M_a$ “ so definiert, dass es die verbleibenden Standardbasiszustände nicht beeinflusst.

Unter Verwendung der in der vorherigen Lektion behandelten Algorithmen für die ganzzahlige Multiplikation und Division sowie der Methodik für reversible, „garbage-freie“ Implementierungen dieser Algorithmen können wir eine Quantenschaltung aufbauen, die die Operation „ $M_a$ “ für eine beliebige Wahl von $a\in\mathbb{Z}_N^{\ast}$ mit einem Aufwand von $O(n^2)$ ausführt. Hier ist eine Möglichkeit, wie dies umgesetzt werden kann.

1. Baue eine Schaltung zur Durchführung der Operation

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

wo

$$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

unter Anwendung der in der vorherigen Lektion beschriebenen Methode. Damit erhalten wir einen Kreis der Größe $O(n^2)$.

2. Tauschen Sie die beiden $n$ -Qubit-Systeme mit $n$ Swap-Gates, um die Qubits einzeln zu tauschen.

3. Bauen Sie analog zum ersten Schritt eine Schaltung für die Operation

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

wobei $a^{-1}$ die Inverse von $a$ in $\mathbb{Z}_N^{\ast}$ ist.

Indem wir die unteren $n$ Qubits initialisieren und die drei Schritte zusammensetzen, erhalten wir diese Transformation:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

Das Verfahren erfordert Arbeitsraum-Qubits, die jedoch am Ende wieder in ihren initialisierten Zustand zurückversetzt werden, sodass wir diese Schaltungen zur Phasenschätzung nutzen können. Die Gesamtkosten der Schaltung betragen $O(n^2)$.

Um $M_a^2$, $M_a^4$, $M_a^8$ usw. auszuführen, können wir genau dieselbe Methode anwenden, mit dem Unterschied, dass wir $a$ durch $a^2$, $a^4$, $a^8$ usw. als Elemente von $\mathbb{Z}_N^{\ast}$ ersetzen. Das heißt, für jede von uns gewählte Potenz $k$ können wir eine Schaltung für $M_a^k$ erstellen, indem wir nicht $k$ Mal die Schaltung für $M_a$ durchlaufen, sondern stattdessen $b = a^k \in \mathbb{Z}_N^{\ast}$ berechnen und dann die Schaltung für $M_b$ verwenden.

Die Berechnung von Potenzen $a^k \in \mathbb{Z}_N$ ist das in der vorherigen Lektion erwähnte Problem der modularen Exponentiation. Diese Berechnung lässt sich auf klassische Weise durchführen, und zwar mithilfe des in der vorherigen Lektion erwähnten Algorithmus für die modulare Potenzierung (der in der computergestützten Zahlentheorie oft als „Potenzalgorithmus“ bezeichnet wird). Tatsächlich benötigen wir lediglich die power-of-2 en Potenzen von $a$, insbesondere $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$, und diese Potenzen können wir erhalten, indem wir $m-1$ -mal iterativ quadrieren. Jede Quadrierung kann durch eine Boolesche Schaltung der Größe $O(n^2)$ durchgeführt werden.

Im Grunde genommen verlagern wir hier das Problem, die Iteration „ $M_a$ “ so oft wie „ $2^{m-1}$ “ durchzuführen, auf eine effiziente klassische Berechnung. Und es ist ein Glück, dass das möglich ist! Bei einer beliebigen Wahl eines Quantenschaltkreises im Rahmen des Phasenschätzungsproblems dürfte dies nicht möglich sein – und in diesem Fall steigen die Kosten für die Phasenschätzung exponentiell mit der Anzahl der Steuerqubits $m$.

Lösung für einen geeigneten Eigenvektor

Um zu verstehen, wie wir das Problem der Reihenfolgebestimmung mithilfe der Phasenschätzung lösen können, gehen wir zunächst davon aus, dass wir das Phasenschätzungsverfahren auf die Operation $M_a$ unter Verwendung des Eigenvektors $\vert\psi_1\rangle$ anwenden. Wie sich herausstellt, ist es gar nicht so einfach, diesen Eigenvektor zu ermitteln, daher ist die Geschichte damit noch nicht zu Ende – aber es ist hilfreich, hier anzufangen.

Der Eigenwert von $M_a$, der dem Eigenvektor $\vert \psi_1\rangle$ entspricht, ist

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Das heißt, $\omega_r = e^{2\pi i \theta}$ für $\theta = 1/r$. Wenn wir also die Phasenschätzung auf $M_a$ unter Verwendung des Eigenvektors $\vert\psi_1\rangle$ durchführen, erhalten wir eine Näherung für $1/r$. Durch Berechnung des Kehrwerts können wir $r$ ermitteln – vorausgesetzt, unsere Näherung ist gut genug.

Genauer gesagt: Wenn wir das Verfahren zur Phasenschätzung unter Verwendung der Steuerungqubits „ $m$ “ ausführen, erhalten wir einen Wert $y\in\{0,\ldots,2^m-1\}$. Anschließend nehmen wir $y/2^m$ als Schätzwert für $\theta$, was im vorliegenden Fall $1/r$ ist. Um anhand dieser Näherung den Wert von $r$ zu ermitteln, ist es naheliegend, den Kehrwert unserer Näherung zu berechnen und auf die nächste ganze Zahl zu runden.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Nehmen wir beispielsweise an, dass $r = 6$ gilt, und wir führen eine Phasenschätzung auf $M_a$ mit dem Eigenvektor $\vert\psi_1\rangle$ unter Verwendung von $m = 5$ Steuerbits durch. Die beste „ $5$ “-Bit-Näherung für $1/r = 1/6$ lautet $5/32$, und wir haben eine recht gute Chance (in diesem Fall etwa $68\%$ ), bei der Phasenschätzung das Ergebnis $y=5$ zu erhalten. Wir haben

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

und nach Rundung auf die nächste ganze Zahl ergibt sich „ $6$ “, was die richtige Antwort ist.

Andererseits erhalten wir möglicherweise nicht das richtige Ergebnis, wenn wir nicht genau genug vorgehen. Nehmen wir beispielsweise $m = 4$ -Steuerqubits bei der Phasenschätzung, so erhalten wir möglicherweise die beste $4$ -Bit-Näherung an $1/r = 1/6$, nämlich $3/16$. Der Kehrwert ergibt

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

Und die Rundung auf die nächste ganze Zahl führt zu einem falschen Ergebnis von $5$.

Wie viel Genauigkeit brauchen wir also, um das richtige Ergebnis zu erhalten? Wir wissen, dass die Ordnung $r$ eine ganze Zahl ist, und intuitiv benötigen wir genügend Genauigkeit, um $1/r$ von nahegelegenen Möglichkeiten zu unterscheiden, darunter $1/(r+1)$ und $1/(r-1)$. Die Zahl, die $1/r$ am nächsten liegt und die für uns von Bedeutung ist, ist $1/(r+1)$, und der Abstand zwischen diesen beiden Zahlen beträgt

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Wenn wir also sicherstellen wollen, dass wir $1/r$ nicht mit $1/(r+1)$ verwechseln, reicht es aus, eine ausreichende Genauigkeit zu wählen, um zu gewährleisten, dass eine bestmögliche Annäherung $y/2^m$ an $1/r$ näher an $1/r$ liegt als an $1/(r+1)$. Wenn wir eine ausreichende Genauigkeit wählen, sodass

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

Damit der Fehler kleiner als die Hälfte des Abstands zwischen $1/r$ und $1/(r+1)$ ist, liegt $y/2^m$ näher an $1/r$ als an jeder anderen Möglichkeit, einschließlich $1/(r+1)$ und $1/(r-1)$.

Wir können dies wie folgt überprüfen. Angenommen, dass

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

für $\varepsilon$ zufriedenstellend

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Wenn wir den Kehrwert nehmen, erhalten wir

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Indem wir im Zähler maximieren und im Nenner minimieren, können wir wie folgt eingrenzen, wie weit wir von $r$ entfernt sind.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Wir sind weniger als $1/2$ von $r$ entfernt, daher erhalten wir, wie erwartet, $r$, wenn wir aufrunden.

Da wir noch nicht wissen, was $r$ ist, können wir leider nicht sagen, wie viel Genauigkeit wir brauchen. Stattdessen können wir die Tatsache nutzen, dass $r$ kleiner als $N$ sein muss, um sicherzustellen, dass wir eine ausreichende Genauigkeit verwenden. Insbesondere, wenn wir eine ausreichende Genauigkeit verwenden, um sicherzustellen, dass die beste Annäherung $y/2^m$ an $1/r$ folgende Bedingungen erfüllt

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

dann haben wir genug Genauigkeit, um $r$ korrekt zu bestimmen, wenn wir den Kehrwert nehmen. Mit $m = 2\operatorname{lg}(N)+1$ ist sichergestellt, dass wir mit der oben beschriebenen Methode mit hoher Wahrscheinlichkeit eine Schätzung mit dieser Genauigkeit erhalten. ( $m = 2\operatorname{lg}(N)$ reicht aus, wenn wir uns mit einer Untergrenze von 40 % für die Erfolgswahrscheinlichkeit zufrieden geben)

Allgemeine Lösung

Wie wir gerade gesehen haben, können wir, wenn wir den Eigenvektor $\vert \psi_1 \rangle$ von $M_a$ haben, $r$ durch Phasenschätzung ermitteln, sofern wir genügend Steuerqubits verwenden, um dies mit ausreichender Genauigkeit durchzuführen. Leider ist es nicht einfach, an die Eigenvektor $\vert\psi_1\rangle$ heranzukommen, daher müssen wir uns überlegen, wie wir vorgehen sollen.

Nehmen wir einmal an, wir gehen genauso vor wie oben, nur dass wir anstelle von $\vert\psi_1\rangle$ den Eigenvektor $\vert\psi_k\rangle$ verwenden, und zwar für jede beliebige Wahl von $k\in\{0,\ldots,r-1\}$, die wir betrachten wollen. Das Ergebnis, das wir aus dem Phasenschätzungsverfahren erhalten, ist eine Näherung

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Unter der Annahme, dass wir weder $k$ noch $r$ kennen, ermöglicht uns dies möglicherweise, $r$ zu identifizieren – oder auch nicht. Wenn beispielsweise $k = 0$ gilt, erhalten wir eine Annäherung $y/2^m$ an $0$, was uns leider keine Informationen liefert. Dies ist jedoch ein Sonderfall; für andere Werte von $k$ können wir zumindest etwas über $r$ erfahren.

Wir können einen Algorithmus verwenden, der als Algorithmus für fortgesetzte Brüche bekannt ist, um unsere Annäherung $y/2^m$ in naheliegende Brüche zu verwandeln - einschließlich $k/r$, wenn die Annäherung gut genug ist. Wir werden den Algorithmus für fortgesetzte Brüche hier nicht erklären. Stattdessen wird hier eine bekannte Tatsache über diesen Algorithmus dargelegt.

Für eine ganze Zahl $N\geq 2$ und eine reelle Zahl $\alpha\in(0,1)$ gibt es höchstens eine Möglichkeit, ganze Zahlen $u,v\in\{0,\ldots,N-1\}$ so zu wählen, dass $v\neq 0$ und $\gcd(u,v)=1$ die Bedingung $\vert \alpha - u/v\vert < \frac{1}{2N^2}$ erfüllen. Für $\alpha$ und $N$ ermittelt der Kettenbruch-Algorithmus $u$ und $v$ oder meldet, dass diese nicht existieren. Dieser Algorithmus lässt sich als Boolesche Schaltung mit der Größe $O((\operatorname{lg}(N))^3)$ implementieren.

Wenn wir eine sehr genaue Näherung $y/2^m$ für $k/r$ haben und den Kettenbruch-Algorithmus für $N$ und $\alpha = y/2^m$ anwenden, erhalten wir $u$ und $v$, wie in der Aufgabe beschrieben. Eine Analyse dieser Tatsache lässt den Schluss zu, dass

$$\frac{u}{v} = \frac{k}{r}.$$

Beachten Sie insbesondere, dass wir nicht unbedingt $k$ und $r$ lernen, sondern nur $k/r$ in einfachster Form.

Zum Beispiel – und wie wir bereits festgestellt haben – werden wir aus „ $k=0$ “ nichts lernen. Aber das ist der einzige Wert von „ $k$ “, bei dem dies der Fall ist. Wenn $k$ ungleich Null ist, kann es gemeinsame Teiler mit $r$ geben, aber die Zahl $v$, die wir aus dem Kettenbruchalgorithmus erhalten, muss mindestens $r$ teilen.

Es ist zwar keineswegs offensichtlich, aber es stimmt: Wenn wir die Möglichkeit haben, $u$ und $v$ für $u/v = k/r$ für $k\in\{0,\ldots,r-1\}$ zu ermitteln, die einheitlich zufällig ausgewählt wurden, dann ist es sehr wahrscheinlich, dass wir $r$ bereits nach wenigen Stichproben rekonstruieren können. Insbesondere wenn unsere Vermutung für $r$ das kleinste gemeinsame Vielfache aller beobachteten Werte für den Nenner $v$ ist, werden wir mit hoher Wahrscheinlichkeit richtig liegen. Intuitiv betrachtet sind manche Werte von $k$ nicht gut, da sie gemeinsame Faktoren mit $r$ haben, und diese gemeinsamen Faktoren bleiben uns verborgen, wenn wir $u$ und $v$ ermitteln. Zufällige Auswahlen von $k$ können jedoch Faktoren von $r$ wahrscheinlich nicht lange verbergen, und die Wahrscheinlichkeit, dass wir $r$ nicht richtig erraten, indem wir das kleinste gemeinsame Vielfache der beobachteten Nenner bilden, sinkt exponentiell mit der Anzahl der Stichproben.

Bleibt noch die Frage zu klären, wie wir an einen Eigenvektor $\vert\psi_k\rangle$ von $M_a$ kommen, mit dem wir das Phasenschätzungsverfahren durchführen können. Wie sich herausstellte, müssen wir sie gar nicht erst erstellen!

Stattdessen werden wir das Phasenschätzungsverfahren auf den Zustands $\vert 1\rangle$ anwenden; damit meinen wir die $n$ -Bit-Binärkodierung der Zahl $1$ anstelle eines Eigenvektors $\vert\psi\rangle$ von $M_a$. Bisher haben wir nur davon gesprochen, das Phasenschätzungsverfahren auf einen bestimmten Eigenvektor anzuwenden, aber nichts hindert uns daran, das Verfahren auf einen Eingangszustand anzuwenden, der kein Eigenvektor von $M_a$ ist, und genau das tun wir hier mit dem Zustand $\vert 1\rangle$. (Dies ist kein Eigenvektor von $M_a$, es sei denn, $a=1$, was für uns jedoch nicht von Interesse ist.)

Der Grund für die Wahl des Zustands $\vert 1\rangle$ anstelle eines Eigenvektors von $M_a$ ist, dass die folgende Gleichung wahr ist.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Eine Möglichkeit, diese Gleichung zu überprüfen, besteht darin, die inneren Produkte der beiden Seiten mit jedem Standard-Basiszustand zu vergleichen, wobei die zuvor in der Lektion erwähnten Formeln bei der Auswertung der Ergebnisse für die rechte Seite helfen. Infolgedessen erhalten wir genau die gleichen Messergebnisse, als hätten wir $k\in\{0,\ldots,r-1\}$ gleichmäßig nach dem Zufallsprinzip ausgewählt und $\vert\psi_k\rangle$ als Eigenvektor verwenden.

Um das genauer zu verdeutlichen, stellen wir uns vor, wir führen das Verfahren zur Phasenschätzung mit dem Zustand $\vert 1\rangle$ anstelle eines der Eigenvektoren $\vert\psi_k\rangle$ durch. Nach Durchführung der inversen Quanten-Fourier-Transformation erhalten wir folgenden Zustand:

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

wo

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

Der Vektor $\vert\gamma_k\rangle$ stellt den Zustand der oberen $m$ Qubits dar, nachdem die Umkehrung der Quanten-Fourier-Transformation an ihnen durchgeführt wurde.

Aufgrund der Tatsache, dass $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ eine orthonormale Menge ist, finden wir, dass eine Messung der obersten $m$ Qubits eine Annäherung $y/2^m$ an den Wert $k/r$ ergibt, wobei $k\in\{0,\ldots,r-1\}$ gleichmäßig zufällig gewählt wird. Wie wir bereits besprochen haben, ermöglicht uns dies, $r$ mit einem hohen Maß an Vertrauen nach mehreren unabhängigen Durchläufen zu lernen, was unser Ziel war.

Gesamtkosten

Die Kosten für die Ausführung jedes kontrollierten unitären „ $M_a^k$ “ betragen $O(n^2)$. Es gibt $m$ kontrollierte unitäre Operationen, und wir haben $m = O(n)$, sodass die Gesamtkosten für die kontrollierten unitären Operationen $O(n^3)$ betragen. Darüber hinaus haben wir $m$ Hadamard-Gates (die $O(n)$ zu den Kosten beitragen), und die inverse Quanten-Fourier-Transformation trägt $O(n^2)$ zu den Kosten bei. Somit dominieren die Kosten der kontrollierten Unitar-Operationen die Kosten des gesamten Verfahrens – das somit „ $O(n^3)$ “ ist.

Neben dem Quantenschaltkreis selbst müssen im Verlauf des Prozesses noch einige klassische Berechnungen durchgeführt werden. Dazu gehört die Berechnung der Potenzen $a^k$ in $\mathbb{Z}_N$ für $k = 2, 4, 8, \ldots, 2^{m-1}$, die zur Erzeugung der kontrollierten unitären Gatter benötigt werden, sowie der Kettenbruch-Algorithmus, der Näherungswerte von $\theta$ in Brüche umwandelt. Diese Berechnungen können mit Booleschen Schaltungen durchgeführt werden, deren Gesamtkosten bei $O(n^3)$ liegen.

Wie üblich können alle diese Grenzen mit asymptotisch schnellen Algorithmen verbessert werden; diese Grenzen setzen voraus, dass wir Standardalgorithmen für grundlegende arithmetische Operationen verwenden.

---

Factoring durch Auftragssuche

Der letzte Punkt, den wir erörtern müssen, ist die Frage, wie die Lösung des Ordnungsfindungsproblems uns hilft, zu faktorisieren. Dieser Teil ist völlig klassisch - er hat nichts speziell mit Quantencomputing zu tun.

Das ist der Grundgedanke. Wir wollen die Zahl „ $N$ “ in Faktoren zerlegen, und das können wir rekursiv tun. Konkret können wir uns auf die Aufgabe konzentrieren, $N$ zu zerlegen, d. h. zwei beliebige ganze Zahlen $b,c\geq 2$ zu finden, für die $N = bc$ gilt. Dies ist nicht möglich, wenn $N$ eine Primzahl ist, aber wir können zunächst mithilfe eines Primzahlprüfalgorithmus effizient prüfen, ob $N$ eine Primzahl ist, und wenn $N$ keine Primzahl ist, versuchen wir, sie zu zerlegen. Sobald wir $N$ zerlegt haben, können wir einfach rekursiv $b$ und $c$ durchlaufen, bis alle unsere Faktoren Primzahlen sind und wir die Primfaktorzerlegung von $N$ erhalten.

Das Aufteilen von geraden ganzen Zahlen ist einfach: Wir geben einfach „ $2$ “ und „ $N/2$ “ aus.

Es ist außerdem einfach, perfekte Potenzen zu zerlegen, d. h. Zahlen der Form $N = s^j$ für ganze Zahlen $s,j\geq 2$, indem man einfach die Wurzeln $N^{1/2}$, $N^{1/3}$, $N^{1/4}$ usw. näherungsweise berechnet und benachbarte ganze Zahlen als Kandidaten für $s$ überprüft. Wir müssen nicht weiter als $\log(N)$ Schritte in dieser Folge vorgehen, da die Wurzel an dieser Stelle unter $2$ fällt und keine weiteren Kandidaten mehr liefert.

Es ist gut, dass wir beides tun können, denn die Ordnungssuche hilft uns nicht beim Faktorisieren gerader Zahlen oder bei Primzahlpotenzen, bei denen die Zahl $s$ zufällig eine Primzahl ist. Ist $N$ jedoch ungerade und keine Primzahlpotenz, so können wir dank der Ordnungsfindung $N$ aufteilen.

1. Wähle zufällig „ $a\in\{2,\ldots,N-1\}$ “ aus.

2. Berechne $d=\gcd(a,N)$.

3. Wenn „ $d > 1$ “ gilt, dann gib „ $b = d$ “ und „ $c = N/d$ “ aus und beende das Programm. Andernfalls fahren Sie mit dem nächsten Schritt fort, in dem Wissen, dass „ $a\in\mathbb{Z}_N^{\ast}$ “ gilt.

4. Sei $r$ die Ordnung von $a$ modulo $N$. (An dieser Stelle brauchen wir die Auftragsermittlung.)

5. Wenn $r$ ausgeglichen ist:

   5.1 Berechne$x = a^{r/2} - 1$ modulo$N$

   5.2
   Berechne$d = \gcd(x,N)$ . 5.3
   Wenn$d>1$ , dann gib$b=d$ und$c = N/d$ aus und beende die Berechnung.

6. Ist dieser Punkt erreicht, ist es dem Algorithmus nicht gelungen, einen Faktor von $N$ zu finden.

Bei der Ausführung dieses Algorithmus kann es vorkommen, dass ein Faktor von $N$ nicht gefunden wird. Konkret tritt dies in zwei Fällen auf:

• Die Reihenfolge von $a$ modulo $N$ ist ungerade.
• Die Ordnung von $a$ modulo $N$ ist gerade und $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$.

Mit Hilfe der elementaren Zahlentheorie lässt sich beweisen, dass bei einer zufälligen Wahl von $a$ mit einer Wahrscheinlichkeit von mindestens $1/2$ keines dieser Ereignisse eintritt. Tatsächlich beträgt die Wahrscheinlichkeit, dass eines der beiden Ereignisse eintritt, höchstens $2^{-(m-1)}$, wobei $m$ die Anzahl der verschiedenen Primfaktoren von $N$ ist, weshalb die Annahme erforderlich ist, dass $N$ keine Primzahlpotenz ist. (Damit diese Tatsache gilt, muss außerdem die Annahme gelten, dass $N$ ungerade ist.)

Das bedeutet, dass bei jedem Durchlauf die Wahrscheinlichkeit, dass „ $N$ “ aufgeteilt wird, mindestens 50 % beträgt. Wenn wir den Algorithmus also $t$ -mal ausführen und dabei jedes Mal zufällig $a$ auswählen, gelingt es uns mit einer Wahrscheinlichkeit von mindestens $1 - 2^{-t}$, „ $N$ “ aufzuteilen.

Die Grundidee des Algorithmus ist die folgende. Wenn wir eine Auswahl von $a$ haben, für die die Reihenfolge $r$ von $a$ modulo $N$ gerade ist, dann ist $r/2$ eine ganze Zahl und wir können die zahlen

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Unter Verwendung der Formel „ $Z^2 - 1 = (Z+1)(Z-1)$ “ kommen wir zu dem Schluss, dass

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Nun wissen wir, dass $a^r \; (\textrm{mod}\; N) = 1$ gemäß der Definition der Ordnung gilt – was nichts anderes bedeutet, als dass $N$ ein Teiler von $a^r - 1$ ist. Das bedeutet, dass $N$ ein Teiler des Produkts ist

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Damit das stimmt, müssen alle Primfaktoren von $N$ auch Primfaktoren von $a^{r/2} - 1$ oder $a^{r/2} + 1$ (oder von beiden) sein - und bei einer zufälligen Auswahl von $a$ stellt sich heraus, dass es unwahrscheinlich ist, dass alle Primfaktoren von $N$ einen der Terme teilen und keiner den anderen. Solange einige der Primfaktoren von $N$ den ersten Term teilen und einige den zweiten Term teilen, können wir einen nicht-trivialen Faktor von $N$ finden, indem wir den GCD mit dem ersten Term berechnen.