Shor-Algorithmus

Für dieses Qiskit-in-Classrooms-Modul benötigen Studierende eine funktionierende Python-Umgebung mit den folgenden installierten Paketen:

• qiskit v2.1.0 oder neuer
• qiskit-ibm-runtime v0.40.1 oder neuer
• qiskit-aer v0.17.0 oder neuer
• qiskit.visualization
• numpy
• pylatexenc

Zum Einrichten und Installieren der oben genannten Pakete siehe die Anleitung Qiskit installieren. Um Jobs auf echten Quantencomputern auszuführen, müssen Studierende ein Konto bei IBM Quantum® einrichten, indem sie den Schritten in der Anleitung IBM Cloud-Konto einrichten folgen.

Dieses Modul wurde getestet und verbrauchte drei Sekunden QPU-Zeit. Dies ist nur eine Schätzung. Dein tatsächlicher Verbrauch kann abweichen.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Einführung

In den frühen 1990er Jahren wuchs die Begeisterung über das Potenzial von Quantencomputern, Probleme zu lösen, die für klassische Computer schwierig waren. Einige talentierte Informatiker hatten Algorithmen entwickelt, die die Leistungsfähigkeit des Quantencomputings für einige Nischen- und konstruierte Probleme demonstrierten, aber niemand hatte eine einzige „Killeranwendung" des Quantencomputings gefunden, die das Feld sicher revolutionieren würde. Das änderte sich 1994, als Peter Shor das entwickelte, was heute als Shor-Algorithmus zur Faktorisierung großer Zahlen bekannt ist.

Es war damals allgemein bekannt, dass das Finden der Primfaktoren einer großen Zahl für einen klassischen Computer extrem schwierig war. Tatsächlich beruhten die Internet-Sicherheitsprotokolle auf dieser Schwierigkeit. Shor fand einen Weg, diese Faktoren exponentiell effizienter zu finden, indem er einige der schwierigeren Schritte auf einen theoretischen, zukünftigen Quantencomputer auslagerte.

In diesem Modul werden wir den Shor-Algorithmus erkunden. Zunächst geben wir etwas mehr Kontext zum Algorithmus, formalisieren das Problem, das er löst, und erklären die Relevanz für die Cybersicherheit. Dann geben wir eine Einführung in die modulare Mathematik und wie man sie auf das Faktorisierungsproblem anwendet, wobei wir zeigen, wie sich die Faktorisierung auf ein anderes Problem namens „Ordnungsfindung" reduziert. Wir zeigen, wie die Quanten-Fourier-Transformation und die Quanten-Phasenschätzung, die wir in einem früheren Modul kennengelernt haben, ins Spiel kommen und wie man sie zur Lösung des Ordnungsfindungsproblems verwendet.

Schließlich werden wir den Shor-Algorithmus auf einem echten Quantencomputer ausführen! Bedenke jedoch, dass dieser Algorithmus wirklich erst nützlich sein wird, wenn wir einen großen, fehlertoleranten Quantencomputer haben, was noch einige Jahre entfernt ist. Daher werden wir nur eine kleine Zahl faktorisieren, um die Funktionsweise des Algorithmus zu demonstrieren.

Das Faktorisierungsproblem

Das Ziel des Faktorisierungsproblems ist es, die Primfaktoren einer Zahl $N$ zu finden. Für einige Zahlen $N$ ist das ziemlich einfach. Wenn $N$ zum Beispiel gerade ist, wird einer seiner Primfaktoren 2 sein. Wenn $N$ eine Primzahlpotenz ist, also $N=p^k$ für eine Primzahl $p$, ist es auch recht einfach, $p$ zu finden: Wir approximieren einfach die $k^{\text{th}}$-Wurzel von $N$ und suchen nach nahegelegenen Primzahlen, die $p$ sein könnten.

Wo klassische Computer jedoch Schwierigkeiten haben, ist wenn $N$ ungerade und keine Primzahlpotenz ist. Dies ist der Fall, den der Shor-Algorithmus behandelt. Der Algorithmus findet zwei Faktoren $p$ und $q$, sodass $N=pq$. Er kann rekursiv angewendet werden, bis alle Faktoren Primzahlen sind. In den nächsten Abschnitten werden wir sehen, wie dieses Problem angegangen wird.

Relevanz für die Cybersicherheit

Viele kryptografische Verfahren wurden auf der Grundlage der Tatsache entwickelt, dass die Faktorisierung großer Zahlen schwierig ist, darunter eines, das heute häufig verwendet wird, namens RSA. Bei RSA wird ein öffentlicher Schlüssel erstellt, indem zwei große Primzahlen miteinander multipliziert werden, um $N = p\cdot q$ zu erhalten. Dann kann jeder diesen öffentlichen Schlüssel verwenden, um Daten zu verschlüsseln. Aber nur jemand mit dem privaten Schlüssel, $p$ und $q$, kann diese Daten entschlüsseln.

Wenn $N$ leicht zu faktorisieren wäre, könnte jeder bestimmen, was $p$ und $q$ sind, und die Verschlüsselung brechen. Aber das ist es nicht. Dies ist ein bekanntermaßen schwieriges Problem. Tatsächlich wurden die Primfaktoren einer Zahl namens RSA1024, die 1024 Binärstellen und 309 Dezimalstellen lang ist, noch immer nicht gefunden, obwohl bereits 1991 ein Preisgeld von $100.000 für ihre Faktorisierung ausgesetzt wurde.

Shors Lösung

Im Jahr 1994 erkannte Peter Shor, dass ein Quantencomputer eine große Zahl exponentiell effizienter faktorisieren könnte als ein klassischer Computer. Seine Erkenntnis beruhte auf der Beziehung zwischen diesem Faktorisierungsproblem und der modularen Arithmetik. Wir werden eine kurze Einführung in die modulare Arithmetik geben und dann sehen, wie wir sie nutzen können, um $N$ zu faktorisieren.

Modulare Arithmetik

Modulare Arithmetik ist ein Zählsystem, das zyklisch ist, was bedeutet, dass das Zählen zwar auf die übliche Weise beginnt, mit den ganzen Zahlen 0, 1, 2, usw., aber irgendwann, nach einer Periode $N$, das Zählen von vorne beginnt. Sehen wir uns an, wie das mit einem Beispiel funktioniert. Unsere Periode sei 5. Dann beginnen wir beim Zählen dort, wo wir normalerweise 5 erreichen würden, wieder bei 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Das liegt daran, dass in der „Modulo-5"-Welt 5 äquivalent zu 0 ist. Wir sagen, dass $5\bmod 5 \ = 0$. Tatsächlich sind alle Vielfachen von 5 äquivalent zu $0\bmod 5$.

Überprüfe dein Verständnis

Verwende modulare Arithmetik, um das folgende Problem zu lösen:

Du startest eine lange, transkontinentale Zugfahrt um 8 Uhr morgens. Die Zugfahrt dauert 60 Stunden. Wie spät ist es, wenn du ankommst?

Answer

Die Periode ist 24, da ein Tag 24 Stunden hat. Dieses Problem kann also in modularer Arithmetik geschrieben werden als:

$(8+60)\text{mod}(24) = 20$

Du würdest also um 20:00 Uhr an deinem Ziel ankommen.

$\mathbb{Z}_N$ und $\mathbb{Z}_N^*$

Es ist oft nützlich, zwei Mengen einzuführen, $\mathbb{Z}_N$ und $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ ist einfach die Menge der Zahlen, die in einer „Modulo-$N$"-Welt existieren. Zum Beispiel, als wir modulo-5 gezählt haben, wäre die Menge $\mathbb{Z}_5=\{0,1,2,3,4\}$. Ein weiteres Beispiel: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Wir können Addition und Multiplikation (modulo $N$) auf den Elementen in $\mathbb{Z}_N$ durchführen, und das Ergebnis jeder dieser Operationen ist ebenfalls ein Element in $\mathbb{Z}_N$, was $\mathbb{Z}_N$ zu einem mathematischen Objekt namens Ring macht.

Es gibt eine spezielle Teilmenge von $\mathbb{Z}_N$, die für den Shor-Algorithmus von besonderem Interesse ist. Das ist die Teilmenge der Zahlen in $\mathbb{Z}_N$, bei denen der größte gemeinsame Teiler zwischen jedem Element und $N$ gleich 1 ist, jedes Element also „teilerfremd" zu $N$ ist. Wenn wir die Menge dieser Zahlen zusammen mit der modularen Multiplikationsoperation nehmen, bildet dies ein weiteres mathematisches Objekt, eine sogenannte Gruppe. Wir nennen diese Gruppe $\mathbb{Z}_N^*$. Es stellt sich heraus, dass bei $\mathbb{Z}_N^*$ (und endlichen Gruppen im Allgemeinen), wenn wir ein beliebiges Element $a \in \mathbb{Z}_N^*$ wählen und $a$ wiederholt mit sich selbst multiplizieren, wir immer irgendwann die Zahl $1$ erhalten. Die minimale Anzahl, wie oft man $a$ mit sich selbst multiplizieren muss, um $1$ zu erhalten, wird als Ordnung von $a$ bezeichnet. Diese Tatsache wird für unsere Diskussion über die Faktorisierung von Zahlen weiter unten sehr wichtig sein.

Überprüfe dein Verständnis

Was ist $\mathbb{Z}_{15}^*$?

Answer

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Wir haben die folgenden Zahlen ausgeschlossen:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Was ist die Ordnung jedes Elements in $\mathbb{Z}_{15}^*$?

Answer

Die Ordnung $r$ ist die kleinste Zahl, für die $a^r\text{mod}(15)=1$ für jedes Element $a$ gilt.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Beachte, dass wir zwar die Ordnung der Zahlen in $\mathbb{Z}_{15}^*$ finden konnten, dies aber im Allgemeinen für größere $N$ KEINE einfache Aufgabe ist. Dies ist der Kern des Faktorisierungsproblems und der Grund, warum wir einen Quantencomputer brauchen. Wir werden sehen warum, wenn wir den Rest des Notebooks durcharbeiten.

Modulare Arithmetik auf das Faktorisierungsproblem anwenden

Der Schlüssel zum Finden der Faktoren $p$ und $q$ mit $N=pq$ liegt darin, eine andere ganze Zahl $x$ zu finden, sodass

$x^2 \equiv 1 \bmod N$ und $x \not\equiv \pm 1 \bmod N.$

Wie hilft uns das Finden von $x$, die Faktoren $p$ und $q$ zu finden? Gehen wir das Argument jetzt durch. Da $x^2 \equiv 1 \bmod N$, bedeutet das, dass $x^2 - 1 \equiv 0 \bmod N$. Mit anderen Worten, $x^2 - 1$ ist ein Vielfaches von $N$. Also gilt für eine ganze Zahl $l$:

$x^2 - 1 = l N$

Wir können $x^2 - 1$ faktorisieren und erhalten:

$(x+1)(x-1) = l N$

Aus unseren anfänglichen Annahmen wissen wir, dass $x \not\equiv \pm 1 \bmod N$, also teilt $N$ weder $x+1$ noch $x-1$ ohne Rest. Die beiden Faktoren von $N$, $p$ und $q$, müssen also jeweils $x-1$ und $x+1$ teilen. Entweder ist $p$ ein Faktor von $x-1$ und $q$ ein Faktor von $x+1$, oder umgekehrt. Wenn wir also die größten gemeinsamen Teiler (GGT) zwischen $N$ und sowohl $x-1$ als auch $x+1$ berechnen, erhalten wir die Faktoren $p$ und $q$. Die Berechnung des GGT zweier Zahlen ist eine klassisch einfache Aufgabe, die zum Beispiel mit dem Euklidischen Algorithmus durchgeführt werden kann.

Überprüfe dein Verständnis

Es kann schwierig sein, jeden logischen Schritt oben zu verstehen, also versuche, es mit einem Beispiel durchzuarbeiten. Verwende $N=15$ und $x=11$. Überprüfe zunächst, dass $x^2 \equiv 1 \text{mod}(N)$ und $x \not\equiv \pm 1 \bmod N$. Überprüfe dann weiterhin jeden Schritt. Berechne schließlich $\text{GCD}(11\pm1,15)$ und überprüfe, dass es sich um die Faktoren von $15$ handelt.

Answer

$11^2 = 121$, was $15*8 + 1$ ist, also $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, was nicht äquivalent zu $0\bmod 15$ ist. $\checkmark$

$11 + 1 = 12$, was nicht äquivalent zu $0\bmod 15$ ist. $\checkmark$

Nun wissen wir, dass $(x+1)(x-1) = l N$ für eine ganze Zahl $l$. Dies wird bestätigt, wenn wir $x$ und $N$ einsetzen: $(12)(10) = l 15$ mit $l = 8$. $\checkmark$

Nun müssen wir $\text{GCD}(12,15)$ und $\text{GCD}(10,15)$ berechnen.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Wir haben also unsere Faktoren von $15$ gefunden!

Der Algorithmus

Nachdem wir gesehen haben, wie das Finden einer ganzen Zahl $x$ mit $x^2 \equiv 1\bmod N$ uns hilft, $N$ zu faktorisieren, können wir den Shor-Algorithmus durchgehen. Er läuft im Wesentlichen darauf hinaus, $x$ zu finden:

1. Wähle eine zufällige ganze Zahl Wähle eine zufällige ganze Zahl $a$ mit $1 < a < N$.

• Berechne $\text{GCD}(a, N)$ klassisch.
  • Falls $\text{GCD}(a, N) > 1$, hast du bereits einen Faktor gefunden. Stopp.
  • Andernfalls fahre fort.

2. Finde die Ordnung $r$ von $a$ modulo $N$ Finde die kleinste positive ganze Zahl $r$, die $a^r \equiv 1 \pmod N$ erfüllt.

3. Überprüfe, ob die Ordnung gerade ist

• Falls $r$ ungerade ist, gehe zurück zu Schritt 1 und wähle ein neues $a$.
• Falls $r$ gerade ist, fahre mit Schritt 4 fort.

4. Berechne $x = a^{r/2} \bmod N$

• Überprüfe, dass $x \not\equiv 1 \pmod N$ und $x \not\equiv -1 \pmod N$.
  • Falls $x \equiv \pm 1 \pmod N$, gehe zurück zu Schritt 1 und wähle ein neues $a$.
• Andernfalls berechne die GGTs, um die Faktoren zu extrahieren:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Diese werden nichttriviale Faktoren von $N$ sein.

5. Rekursiv faktorisieren, falls nötig

• Falls $p$ und/oder $q$ nicht prim sind, wende den Algorithmus rekursiv an, um sie vollständig zu faktorisieren.
• Sobald alle Faktoren Primzahlen sind, ist die Faktorisierung abgeschlossen.

Basierend auf diesem Verfahren ist es vielleicht nicht offensichtlich, warum ein Quantencomputer benötigt wird, um diese Aufgabe zu erledigen. Er ist notwendig, weil Schritt 2, das Finden der Ordnung von $a$ modulo $N$, klassisch ein sehr schwieriges Problem ist. Die Komplexität skaliert exponentiell mit der Zahl $N$. Aber mit einem Quantencomputer müssen wir nur die Quanten-Phasenschätzung verwenden, um es zu lösen. Schritt 4, das Finden des GGT zweier ganzer Zahlen, ist klassisch eigentlich recht einfach. Der einzige Schritt, der tatsächlich die Leistung eines Quantencomputers benötigt, ist der Ordnungsfindungsschritt. Wir sagen, dass sich das Faktorisierungsproblem auf das Ordnungsfindungsproblem „reduziert".

Der schwierige Teil: Ordnungsfindung

Nun gehen wir durch, wie wir einen Quantencomputer bei der Ordnungsfindung einsetzen können. Zunächst klären wir, was wir mit „Ordnung" meinen. Natürlich habe ich dir bereits erklärt, was die Ordnung mathematisch bedeutet: Es ist die erste von Null verschiedene ganze Zahl $r$, sodass $a^r = 1 \pmod N.$ Aber sehen wir, ob wir etwas mehr Intuition für dieses Konzept gewinnen können.

Für genügend kleines $N$ können wir die Ordnung einfach bestimmen, indem wir jede Potenz von $a$ berechnen, den Modulus $N$ dieser Zahl nehmen und dann aufhören, wenn wir die Potenz $r$ finden, die $a^r = 1 \text{mod}(N)$ erfüllt. Das haben wir mit unserem Beispiel $N=15$ oben gemacht. Schauen wir uns einige Graphen dieser modularen Potenzen für einige Beispielwerte von $a$ und $N$ an:

Fällt dir etwas auf? Das sind periodische Funktionen! Und die Ordnung $r$ ist gleich der Periode! Ordnungsfindung ist also äquivalent zur Periodenfindung.

Quantencomputer sind sehr gut geeignet, die Periode von Funktionen zu finden. Dafür können wir eine algorithmische Unterroutine namens Quanten-Phasenschätzung verwenden. Wir haben QPE und ihre Beziehung zur Quanten-Fourier-Transformation im vorherigen Modul besprochen. Für eine ausführliche Auffrischung besuche das QFT-Modul oder John Watrous' Lektion zur Quanten-Phasenschätzung in seinem Kurs über Quantenalgorithmen. Wir gehen nun das Wesentliche des Verfahrens durch:

Bei der Quanten-Phasenschätzung (QPE) beginnen wir mit einem Unitären $U$ und einem Eigenzustand dieses Unitären $|\psi\rangle$. Dann verwenden wir QPE, um den entsprechenden Eigenwert zu approximieren, der, da der Operator unitär ist, die Form $e^{2\pi i \theta}$ hat. Das Finden des Eigenwerts ist also äquivalent zum Finden des Werts von $\theta$ in der periodischen Funktion. Der Circuit sieht so aus:

wobei die Anzahl der Kontroll-Qubits (die oberen $m$ Qubits in der Abbildung oben) die Genauigkeit der Approximation bestimmt.

Im Shor-Algorithmus verwenden wir QPE auf den unitären Operator $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Hier bezeichnet $|y\rangle$ einen Rechenbasis-Zustand des Multi-Qubit-Registers, wobei der Binärwert der Qubits der ganzen Zahl $y$ entspricht. Zum Beispiel, wenn $N=15$ und $y = 2$, dann wird $|y\rangle$ durch den Vier-Qubit-Basiszustand $|0010\rangle$ dargestellt, da vier Qubits benötigt werden, um Zahlen bis 15 zu kodieren. (Falls dieses Konzept unbekannt ist, siehe das einführende Qiskit-in-Classrooms-Modul für eine Auffrischung zur Binärkodierung von Quantenzuständen.)

Nun müssen wir einen Eigenzustand dieses Unitären bestimmen. Wenn wir im Zustand $|1\rangle$ starten, können wir sehen, dass jede aufeinanderfolgende Anwendung von $U$ den Zustand unseres Registers mit $a \pmod N$ multipliziert, und nach $r$ Anwendungen wieder zum Zustand $|1\rangle$ zurückkehrt. Zum Beispiel mit $a = 3$ und $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Superpositionen der Zustände in diesem Zyklus ($|\psi_j\rangle$) der Form:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

sind alles Eigenzustände von $M_a$. (Es gibt mehr Eigenzustände als nur diese. Aber wir interessieren uns nur für die der obigen Form.)

Überprüfe dein Verständnis

Finde einen Eigenzustand des Unitären, der $a=2$ und $N = 15$ entspricht.

Answer

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Die Ordnung ist also $r=4$. Die Eigenzustände, die uns interessieren, sind eine gleichmäßige Superposition aller Zustände, die oben durchlaufen wurden, mit verschiedenen Phasen:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Nehmen wir an, wir wären in der Lage, unseren Qubit-Zustand in einen dieser Eigenzustände zu initialisieren (Spoiler — das können wir nicht. Oder zumindest nicht einfach. Wir werden gleich erklären warum und was wir stattdessen tun können). Dann könnten wir QPE verwenden, um den entsprechenden Eigenwert $\omega_j = e^{2 \pi i \theta_j}$ zu schätzen, wobei $\theta_j = \frac{j}{r}$. Dann können wir die Ordnung $r$ durch die einfache Gleichung bestimmen:

$r = \frac{j}{\theta_j}.$

Aber denke daran, ich habe gesagt, dass QPE $\theta_j$ schätzt — es gibt uns keinen exakten Wert. Wir brauchen eine Schätzung, die gut genug ist, um zwischen $r$ und $r+1$ zu unterscheiden. Je mehr Kontroll-Qubits $m$ wir haben, desto besser wird die Schätzung. In den Aufgaben am Ende der Lektion wirst du aufgefordert, das minimale $m$ zu bestimmen, das zum Faktorisieren einer Zahl $N$ benötigt wird.

Nun müssen wir ein Problem in Einklang bringen. Die gesamte obige Erklärung, wie man $r$ findet, beginnt mit der Vorbereitung des Eigenzustands $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Aber wir wissen nicht, wie wir das tun sollen, ohne bereits zu wissen, was $r$ ist. Die Logik ist zirkulär. Wir brauchen eine Möglichkeit, den Eigenwert zu schätzen, ohne den Eigenzustand zu initialisieren.

Anstatt mit einem Eigenzustand von $M_a$ zu beginnen, können wir den Anfangszustand in den $n$-Qubit-Zustand präparieren, der $|1\rangle$ in Binärdarstellung entspricht (also $|000...01\rangle$). Obwohl dieser Zustand offensichtlich kein Eigenzustand von $M_a$ ist, ist er eine Superposition über alle Eigenzustände $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Überprüfe dein Verständnis

Überprüfe, dass $|1\rangle$ äquivalent zur Superposition über die Eigenzustände ist, die du für $N=15$ und $a=2$ in der vorherigen Verständnisfrage gefunden hast.

Answer

Die vier Eigenzustände waren:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Also:

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Wie ermöglicht uns das, die Ordnung $r$ zu finden? Da der Ausgangszustand eine Superposition über alle Eigenzustände der oben aufgeführten Form ist, schätzt der QPE-Algorithmus gleichzeitig alle $\theta_k$, die diesen Eigenzuständen entsprechen. Die Messung der $m$ Kontroll-Qubits am Ende liefert also eine Approximation des Werts $k/r$, wobei $k \in \{0,1,2,...,r-1\}$ einer der zufällig ausgewählten Eigenwerte ist. Wenn wir diesen Circuit einige Male wiederholen und einige Stichproben mit verschiedenen Werten von $k$ erhalten, können wir schnell $r$ ableiten.

Implementierung in Qiskit

Wie bereits erwähnt, ist unsere Hardware noch nicht an dem Punkt, an dem wir riesige Zahlen wie RSA1024 faktorisieren können. Wir werden nur eine kleine Zahl faktorisieren, um die Funktionsweise des Algorithmus zu demonstrieren. Für diese Demo verwenden wir eine vereinfachte Version des Codes aus dem Shor-Algorithmus-Tutorial. Für weitere Details besuche bitte das Tutorial.

Wir werden den Algorithmus mit unserem Standardrahmenwerk zum Lösen von Quantenproblemen ausführen, dem sogenannten Qiskit-Patterns-Framework. Dieses besteht aus vier Schritten:

1. Abbildung deines Problems auf einen Quanten-Circuit
2. Optimierung des Circuits für die Ausführung auf Quantenhardware
3. Ausführung deines Circuits auf dem Quantencomputer
4. Nachbearbeitung der Messungen

1. Abbildung

Faktorisieren wir $N=15$ und wählen $a=2$ als unsere teilerfremde ganze Zahl.

Zuerst müssen wir den Circuit konstruieren, der den modularen Multiplikationsunitären $M_a$ implementiert. Das ist tatsächlich der kniffligste Teil der gesamten Implementierung und kann je nach Umsetzung sehr rechenaufwändig sein. Dafür schummeln wir ein wenig: Wir wissen, dass wir im Zustand $|1\rangle$ starten, und aus einer früheren Verständnisfrage:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Wir werden also einen Unitären konstruieren, der die korrekten Operationen auf diesen vier Zuständen durchführt, aber alle anderen Zustände unverändert lässt. Das ist Schummeln, weil wir unser Wissen über die Ordnung von $2\bmod 15$ verwenden, um den Unitären zu vereinfachen. Wenn wir tatsächlich versuchen würden, eine Zahl zu faktorisieren, deren Faktoren uns unbekannt wären, könnten wir das nicht tun.

Überprüfe dein Verständnis

Konstruiere mit deinem Wissen darüber, wie der $M_2$-Operator die obigen Zustände transformiert, den Operator aus einer Reihe von SWAP-Gates, die die Zustände zweier Qubits austauschen. (Hinweis: Es hilft, jeden Zustand $|i\rangle$ in Binärdarstellung zu schreiben.)

Answer

Schreiben wir die Wirkung von $M_2$ auf die Zustände in Binärdarstellung um:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Jede dieser Aktionen kann mit einem einfachen SWAP erreicht werden. $M_2|0001\rangle$ wird durch Vertauschen der Zustände von Qubit $0$ und $1$ erreicht. $M_2|0010\rangle$ wird durch Vertauschen der Zustände von Qubit $1$ und $2$ erreicht. Und so weiter. Wir können also die $M_2$-Matrix in die folgende Reihe von SWAP-Gates zerlegen:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Da Operatoren von rechts nach links wirken, überprüfen wir, dass dies die gewünschte Wirkung auf jeden der Zustände hat:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Wir können nun den Circuit, der diesem Operator entspricht, in Qiskit programmieren.

Zuerst importieren wir die notwendigen Pakete:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Dann erstellen wir den $M_2$-Operator:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Der QPE-Algorithmus verwendet ein kontrolliertes-$U$-Gate. Da wir nun einen $M_2$-Circuit haben, müssen wir daraus einen kontrollierten-$M_2$-Circuit machen:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Nun haben wir unser kontrolliertes-$U$-Gate. Aber um den Quanten-Phasenschätzungsalgorithmus auszuführen, benötigen wir kontrolliertes-$U^2$, kontrolliertes-$U^4$, bis zu kontrolliertes-$U^{2^{m-1}}$, wobei $m$ die Anzahl der Qubits ist, die zur Phasenschätzung verwendet werden. Je mehr Qubits, desto präziser wird die Phasenschätzung. Wir verwenden $m=8$ Kontroll-Qubits für unser Phasenschätzungsverfahren. Wir benötigen also:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

wobei der Index $k$ mit $0 \le k \le m-1 = 7$ dem Kontroll-Qubit entspricht. Berechnen wir nun $a^{2^k}\bmod N$ für jeden Wert von $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Da $a^{2^k} \bmod N = 1$ für $k \ge 2$, sind alle entsprechenden Operatoren ($M_8$ und höher) äquivalent zur Identität. Wir müssen also nur noch eine weitere Matrix konstruieren, $M_4.$

Hinweis: Diese Vereinfachung funktioniert hier nur, weil die Ordnung von $2 \bmod 15$ gleich $4$ ist. Sobald $k=2$ (also $2^k = 4$), ist jede nachfolgende Potenz des Operators die Identität. Im Allgemeinen kann man für größere Zahlen $N$ oder andere Wahlen von $a$ die Konstruktion der höheren Potenzen nicht überspringen. Dies ist einer der Gründe, warum dies als Spielzeugbeispiel betrachtet wird: Die kleinen Zahlen ermöglichen Abkürzungen, die bei größeren Fällen nicht funktionieren würden.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Und wie zuvor machen wir daraus einen kontrollierten-$M_4$-Operator:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Nun können wir alles zusammensetzen, um die Ordnung von $2\bmod 15$ mit einem Quanten-Circuit unter Verwendung der Phasenschätzung zu finden:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Optimierung

Nachdem wir unseren Circuit abgebildet haben, ist der nächste Schritt, ihn für die Ausführung auf einem bestimmten Quantencomputer zu optimieren. Zuerst müssen wir das Backend laden.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Falls du keine verfügbare Zeit auf deinem Konto hast oder aus irgendeinem Grund einen Simulator verwenden möchtest, kannst du die untenstehende Zelle ausführen, um einen Simulator einzurichten, der das oben ausgewählte Quantengerät nachahmt:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Ausführung

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Wir sehen vier deutliche Spitzen bei 00000000, 01000000, 10000000 und 11000000, mit einigen Zählungen in anderen Bitstrings aufgrund von Rauschen im Quantencomputer. Wir ignorieren diese und behalten nur die dominanten vier, indem wir einen Schwellenwert festlegen: Nur Zählungen oberhalb dieses Schwellenwerts werden als echtes Signal über dem Rauschen betrachtet.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Nachbearbeitung

Beim Shor-Algorithmus wird ein Großteil des Algorithmus klassisch durchgeführt. Wir legen also den Rest in den „Nachbearbeitungs"-Schritt, nachdem wir unsere Messungen vom Quantencomputer erhalten haben. Jede der obigen Messungen kann in ganze Zahlen umgewandelt werden, die nach Division durch $2^m$ unsere Approximationen für $\frac{k}{r}$ sind, wobei $k$ jedes Mal zufällig ist.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Fazit

Nachdem du dieses Modul durchgearbeitet hast, wirst du vielleicht eine neue Wertschätzung für die Brillanz von Peter Shor entwickelt haben, der einen so cleveren Algorithmus erdacht hat. Aber hoffentlich hast du auch ein neues Verständnisniveau für dessen trügerische Einfachheit erreicht. Obwohl der Algorithmus beeindruckend (oder einschüchternd) komplex erscheinen mag — wenn du ihn in jeden logischen Schritt zerlegst und langsam durchgehst, wirst auch du in der Lage sein, den Shor-Algorithmus auszuführen.

Wir sind zwar weit davon entfernt, diesen Algorithmus zur Faktorisierung von Zahlen wie RSA1024 zu verwenden, aber unsere Quantencomputer werden jeden Tag besser, und sobald eine Schwelle namens Fehlertoleranz erreicht ist, werden Algorithmen wie diese bald folgen. Es ist eine aufregende Zeit, um etwas über Quantencomputing zu lernen!

Aufgaben

Schlüsselkonzepte:

• Moderne kryptografische Systeme beruhen auf der klassischen Schwierigkeit, große ganze Zahlen zu faktorisieren.
• Modulare Arithmetik — einschließlich der Strukturen $\mathbb{Z}_N$ und $\mathbb{Z}_N^*$ — liefert die mathematische Grundlage für den Shor-Algorithmus.
• Das Problem der Faktorisierung einer ganzen Zahl $N$ kann auf das Problem der Ordnungsfindung einer Zahl modulo $N$ reduziert werden.
• Die quantenmechanische Ordnungsfindung nutzt Quanten-Phasenschätzungstechniken, um die Periode der Funktion $a^x \mod N$ zu bestimmen.
• Der Shor-Algorithmus besteht aus einem klassisch-quantenmechanischen hybriden Workflow, der eine Basis wählt, quantenmechanische Ordnungsfindung durchführt und dann klassisch die Faktoren aus dem Ergebnis berechnet.

Wahr/Falsch:

1. W/F Die Effizienz des Shor-Algorithmus bedroht die Sicherheit der RSA-Verschlüsselung.
2. W/F Der Shor-Algorithmus kann auf jedem modernen Quantencomputer effizient ausgeführt werden.
3. W/F Der Shor-Algorithmus verwendet die Quanten-Phasenschätzung (QPE) als zentrale Unterroutine.
4. W/F Der klassische Teil des Shor-Algorithmus beinhaltet die Berechnung des größten gemeinsamen Teilers (GGT).
5. W/F Der Shor-Algorithmus funktioniert nur für die Faktorisierung gerader Zahlen.
6. W/F Ein erfolgreicher Durchlauf des Shor-Algorithmus garantiert immer die korrekten Faktoren.

Kurzantworten:

1. Warum wird der Shor-Algorithmus als potenzielle zukünftige Bedrohung für die RSA-Verschlüsselung angesehen?
2. Warum ist das Finden der Periode oder Ordnung einer modularen Exponentialfunktion hilfreich für die Faktorisierung einer Zahl im Shor-Algorithmus?

Herausforderungsaufgaben:

1. Wie viele Kontroll-Qubits $m$ benötigen wir für eine gegebene Zahl $N$, die wir zu faktorisieren versuchen, um die nötige Genauigkeit in der QPE zu erhalten, um den korrekten Wert der Ordnung $r$ zu finden?

2. Versuche nun, dem Verfahren folgend, das wir hier zum Faktorisieren von 15 beschrieben haben, die Zahl 21 zu faktorisieren.