Shor-Algorithmus

Für dieses Qiskit in Classrooms-Modul müssen die Schüler über eine funktionierende Python Umgebung verfügen, in der die folgenden Pakete installiert sind:

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

Informationen zum Einrichten und Installieren der oben genannten Pakete finden Sie im Leitfaden zur Installation von Qiskit. Um Jobs auf echten Quantencomputern auszuführen, müssen die Studierenden ein Konto einrichten, IBM Quantum® indem sie die Schritte in der Anleitung zum Einrichten Ihres IBM Cloud Kontos befolgen.

Dieses Modul wurde getestet und benötigte drei Sekunden QPU-Zeit. Dies ist nur eine Schätzung. Ihre tatsächliche Nutzung kann davon abweichen.

# 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 1990s Jahren wuchs die Begeisterung für 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 bestimmte Nischenprobleme demonstrierten, aber niemand hatte eine einzige „Killer-App” für das Quantencomputing gefunden, die dieses Gebiet revolutionieren würde. Das war bis 1994, als Peter Shor den heute als Shor-Algorithmus bekannten Algorithmus zur Faktorisierung großer Zahlen entwickelte.

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

In diesem Modul werden wir den Shor-Algorithmus untersuchen. Zunächst werden wir etwas mehr Kontext zum Algorithmus liefern, indem wir das Problem, das er löst, formalisieren und die Relevanz für die Cybersicherheit erläutern. Als Nächstes geben wir eine Einführung in die modulare Mathematik und ihre Anwendung auf das Faktorisierungsproblem und zeigen, wie sich die Faktorisierung auf ein anderes Problem namens „Ordnungsfindung” reduzieren lässt Wir zeigen, wie die Quanten-Fourier-Transformation und die Quantenphasenabschätzung, die wir im vorherigen Modul kennengelernt haben, zum Einsatz kommen und wie man sie zur Lösung des Ordnungsfindungsproblems verwendet.

Endlich werden wir Shors Algorithmus auf einem echten Quantencomputer ausführen! Beachten Sie jedoch, dass dieser Algorithmus wirklich nur dann nützlich sein wird, wenn wir über einen großen, fehlertoleranten Quantencomputer verfügen, was noch einige Jahre dauern wird. Also werden wir nur eine kleine Zahl faktorisieren, um zu zeigen, wie der Algorithmus funktioniert.

Das Factoring-Problem

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

Klassische Computer haben jedoch Schwierigkeiten, wenn ungerade und $N$* keine* Primzahlpotenz ist. Dies ist der Fall, mit dem sich der Shor-Algorithmus befasst. Der Algorithmus findet zwei Faktoren $p$ und $q$ derart, dass $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 basieren auf der Tatsache, dass die Faktorisierung großer Zahlen schwierig ist, darunter auch ein heute häufig verwendetes Verfahren namens RSA. Bei RSA wird ein öffentlicher Schlüssel erstellt, indem zwei große Primzahlen miteinander multipliziert werden, um zu erhalten $N = p\cdot q$. Dann kann jeder diesen öffentlichen Schlüssel zum Verschlüsseln von Daten verwenden. Aber nur jemand, der über den privaten Schlüssel verfügt, $p$ und $q$, kann diese Daten entschlüsseln.

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

Shores Lösung

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

Modulare Arithmetik

Modulare Arithmetik ist ein zyklisches Zählsystem, was bedeutet, dass das Zählen zwar wie gewohnt mit den ganzen Zahlen 0, 1, 2 usw. beginnt, Nach einer gewissen Zeit beginnt die $N$ Zählung von vorne. Schauen wir uns anhand eines Beispiels an, wie das funktioniert. Angenommen, unsere Periode beträgt 5. Dann, während wir zählen, beginnen wir anstelle von 5 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 gleich 0 ist. Wir sagen, dass $5\bmod 5 \ = 0$. Tatsächlich sind alle Vielfachen von 5 gleich $0\bmod 5$.

Überprüfen Sie Ihr Verständnis

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

Sie brechen um 8 Uhr morgens zu einer langen transkontinentalen Zugfahrt auf. Die Zugfahrt dauert 60 Stunden. Wie spät ist es, wenn Sie ankommen?

• Antwort

  Der Zeitraum beträgt 24, da ein Tag 24 Stunden hat. Dieses Problem lässt sich also in modularer Arithmetik wie folgt schreiben:

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

  Sie würden also um 20:00 Uhr, also um 8 Uhr abends, an Ihrem Ziel ankommen.

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

Es ist oft sinnvoll, zwei Mengen einzuführen: $\mathbb{Z}_N$ und $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ ist einfach die Menge der Zahlen, die in einer $N$ „Modulo-Welt” existieren. Wenn wir beispielsweise zählen modulo-5, 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$ ) mit den Elementen in durchführen, und das Ergebnis jeder $\mathbb{Z}_N$ dieser Operationen ist ebenfalls ein Element in $\mathbb{Z}_N$, wodurch $\mathbb{Z}_N$ zu einem mathematischen Objekt wird, das als Ring bezeichnet wird.

Es gibt eine spezielle Untergruppe von $\mathbb{Z}_N$, die für Shors Algorithmus für uns von besonderem Interesse ist. Das ist die Teilmenge der Zahlen in $\mathbb{Z}_N$, sodass der größte gemeinsame Teiler zwischen jedem Element und 1 $N$ ist, sodass jedes Element zu „relativ $N$ prim“ ist. Wenn wir die Menge dieser Zahlen zusammen mit der modularen Multiplikationsoperation nehmen, bildet dies ein weiteres mathematisches Objekt, das als Gruppe bezeichnet wird. Wir nennen diese Gruppe $\mathbb{Z}_N^*$. Es stellt sich heraus, dass wir bei $\mathbb{Z}_N^*$ (und endlichen Gruppen im Allgemeinen), wenn wir ein beliebiges Element auswählen $a \in \mathbb{Z}_N^*$ und wiederholt mit sich $a$ selbst multiplizieren, immer irgendwann die Zahl erhalten $1$. Die minimale Anzahl von Multiplikationen $a$ mit sich selbst, die erforderlich ist, um zu erhalten, wird $1$ als $a$** Ordnung** von bezeichnet. Diese Tatsache ist für unsere nachfolgende Erörterung der Faktorisierung von Zahlen von großer Bedeutung.

Überprüfen Sie Ihr Verständnis

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

• Antwort

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

  Wir haben die folgenden Nummern 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}$$

Wie lautet die Reihenfolge der einzelnen Elemente in $\mathbb{Z}_{15}^*$?

• Antwort

  Die Ordnung $r$ ist die kleinste Zahl, sodass $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}$$

  Beachten Sie, dass wir zwar die Reihenfolge der Zahlen in finden $\mathbb{Z}_{15}^*$ konnten, dies jedoch im Allgemeinen für größere Zahlen KEINE leichte Aufgabe ist. Dies ist der Kern des $N$ Faktorisierungsproblems und der Grund, warum wir einen Quantencomputer benötigen. Wir werden sehen, warum, wenn wir den Rest des Notizbuchs durcharbeiten.

Wende die modulare Arithmetik auf das Faktorisierungsproblem an

Der Schlüssel zum Finden von Faktoren $p$ und $q$ derart, dass $N=pq$ ist, einen anderen ganzzahligen Wert zu $x$ finden, sodass

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

Wie hilft uns $x$ die Ermittlung von dabei, die Faktoren $p$ und zu finden $q$? Lassen Sie uns nun die Argumentation durchgehen. Da $x^2 \equiv 1 \bmod N$ gilt, bedeutet dies, dass $x^2 - 1 \equiv 0 \bmod N$. Mit anderen Worten: $x^2 - 1$ ist ein Vielfaches von $N$. Für eine ganze Zahl $l$ gilt also

$x^2 - 1 = l N$

Wir können faktorisieren, $x^2 - 1$ um zu erhalten:

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

Aus unseren anfänglichen Annahmen wissen wir, $x \not\equiv \pm 1 \bmod N$ dass $N$ nicht gleichmäßig durch oder $x+1$ teilbar ist. Daher müssen die beiden $x-1$ Faktoren von $N$, $p$ und, jeweils $q$ $x+1$ durch $x-1$ und teilbar sein. Entweder $p$ ist ein $q$ Faktor von $x-1$ und ein Faktor von $x+1$, oder umgekehrt. Wenn wir also die größten gemeinsamen Teiler (GCDs) zwischen $N$ und sowohl $x-1$ als auch $x+1$ berechnen, erhalten wir die Faktoren $p$ und $q$. Die Berechnung des GCD zwischen zwei Zahlen ist eine klassisch einfache Aufgabe, die beispielsweise mit Hilfe des Euklidischen Algorithmus gelöst werden kann.

Überprüfen Sie Ihr Verständnis

Es könnte schwierig sein, jeden Schritt der oben genannten Logik zu verstehen, daher versuchen Sie es anhand eines Beispiels. Verwenden Sie $N=15$ und $x=11$. Überprüfen Sie zunächst, ob $x^2 \equiv 1 \text{mod}(N)$ und $x \not\equiv \pm 1 \bmod N$. Fahren Sie dann fort, jeden Schritt zu überprüfen. Berechnen Sie schließlich $\text{GCD}(11\pm1,15)$ und überprüfen Sie, ob dies die Faktoren von sind $15$.

• Antwort

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

  $11 - 1 = 10$, was nicht gleichbedeutend mit ist $0\bmod 15$. $\checkmark$

  $11 + 1 = 12$, was nicht gleichbedeutend mit ist $0\bmod 15$. $\checkmark$

  Nun wissen wir, dass $(x+1)(x-1) = l N$ für eine ganze Zahl gilt $l$. Dies lässt sich überprüfen, indem wir und $x$ $N$ einsetzen: $(12)(10) = l 15$ wenn $l = 8$. $\checkmark$

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

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

  Also, wir haben unsere Faktoren von gefunden $15$!

Der Algorithmus

Nachdem wir nun gesehen haben, wie uns das Finden einer ganzen $N$ Zahl $x$ so, dass uns beim $x^2 \equiv 1\bmod N$ Faktorisieren hilft, können wir Shors Algorithmus durchgehen. Im Wesentlichen läuft es darauf hinaus, Folgendes zu finden $x$ :

1. Wähle eine zufällige ganze Zahl Wähle eine zufällige ganze Zahl $a$ so, dass $1 < a < N$.

• Klassisch $\text{GCD}(a, N)$ berechnen.
  • Wenn $\text{GCD}(a, N) > 1$, haben Sie bereits einen Faktor gefunden. Halt.
  • Andernfalls fahren Sie fort.

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

3. Überprüfen Sie, ob die Bestellung gerade ist.

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

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

• Überprüfen Sie, ob $x \not\equiv 1 \pmod N$ und $x \not\equiv -1 \pmod N$.
  • Wenn $x \equiv \pm 1 \pmod N$, gehen Sie zurück zu Schritt 1 und wählen Sie einen neuen $a$.
• Andernfalls berechnen Sie die gcds, um die Faktoren zu extrahieren:

Dies sind nicht triviale Faktoren von $N$.

5. Bei Bedarf rekursiv faktorisieren

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

Aufgrund dieses Verfahrens ist möglicherweise nicht ersichtlich, warum für die Ausführung dieser Aufgabe ein Quantencomputer erforderlich ist. Dies ist notwendig, da Schritt 2, das Ermitteln der Ordnung von $a$ modulo $N$, klassischerweise ein sehr schwieriges Problem darstellt. Die Komplexität steigt exponentiell mit der Anzahl $N$. Mit einem Quantencomputer müssen wir jedoch nur die Quantenphasenabschätzung nutzen, um das Problem zu lösen. Schritt 4, das Ermitteln des GGD zweier ganzer Zahlen, ist klassischerweise eigentlich ziemlich einfach. Der einzige Schritt, für den tatsächlich die Leistung eines Quantencomputers erforderlich ist, ist also der Schritt der Ordnungsfindung. Wir sagen, dass sich das Factoring-Problem auf das Ordnungsfindungsproblem „reduzieren“ lässt.

Der schwierige Teil: die Auftragssuche

Nun werden wir uns damit befassen, wie wir einen Quantencomputer für die Suche einsetzen können. Lassen Sie uns zunächst klären, was wir unter „Reihenfolge“ verstehen Natürlich habe ich euch bereits erklärt, was die Ordnung mathematisch bedeutet: Es ist die erste von Null verschiedene ganze Zahl $r$, für die gilt: $a^r = 1 \pmod N$. Aber lasst uns mal schauen, ob wir ein wenig mehr Intuition für dieses Konzept entwickeln können.

Für ausreichend kleine können wir die Ordnung $N$ einfach bestimmen, indem wir jede $a$ Potenz von berechnen, den Modulus $N$ dieser Zahl nehmen und dann aufhören, wenn wir die Potenz finden $r$, die erfüllt $a^r = 1 \text{mod}(N)$. Das haben wir in $N=15$ unserem obigen Beispiel getan. Sehen wir uns einige Grafiken dieser modularen Potenzen für einige Beispielwerte von $a$ und an $N$ :

Fällt Ihnen etwas auf? Das sind periodische Funktionen! Und die Reihenfolge $r$ ist dieselbe wie die Periode! Die Ordnungsfindung entspricht also der Periodenfindung.

Quantencomputer eignen sich sehr gut zum Ermitteln der Periode von Funktionen. Hierfür können wir eine algorithmische Subroutine namens „Quantum Phase Estimation” (Quantenphasenabschätzung) verwenden. Im vorherigen Modul haben wir QPE und dessen Zusammenhang mit der Quanten-Fourier-Transformation behandelt. Eine ausführliche Auffrischung finden Sie im QFT-Modul oder in John Watrous' Lektion zur Quantenphasenabschätzung in seinem Kurs „Quantenalgorithmen”. Wir werden nun die wichtigsten Punkte des Verfahrens durchgehen:

Bei der Quantenphasenabschätzung (QPE) beginnen wir mit einer unitären $U$ und einem Eigenzustand dieser unitären $|\psi\rangle$. Dann verwenden wir QPE, um den entsprechenden Eigenwert zu approximieren, der, da der Operator unitär ist, die Form hat. Das Finden des Eigenwerts entspricht also dem $e^{2\pi i \theta}$ Finden des Werts $\theta$ in der periodischen Funktion. Der Schaltkreis sieht wie folgt aus:

wobei die Anzahl der Steuerqubits (die oberen $m$ Qubits in der Abbildung oben) die Genauigkeit der Annäherung bestimmt.

Im Shor-Algorithmus verwenden wir QPE für den unitären Operator $M_a$ :

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

Hier bezeichnet einen Rechenbasis-Zustand $|y\rangle$ des Multi-Qubit-Registers, wobei der Binärwert der Qubits der ganzen Zahl entspricht $y$. Wenn beispielsweise $N=15$ und $y = 2$, dann $|y\rangle$ wird durch den Vier-Qubit-Basis-Zustand dargestellt, da vier $|0010\rangle$ Qubits erforderlich sind, um Zahlen bis zu 15 zu codieren. (Wenn Ihnen dieses Konzept unbekannt ist, finden Sie im Einführungsmodul „Qiskit im Unterricht“ eine Auffrischung zum Thema binäre Kodierung von Quantenzuständen.)

Nun müssen wir einen Eigenzustand dieser Unitarität herausfinden. Wenn wir im Zustand $|1\rangle$ begonnen haben, können wir sehen, dass jede aufeinanderfolgende $a \pmod N$ Anwendung von den Zustand $U$ unseres Registers mit multipliziert und wir nach $r$ Anwendungen wieder im $|1\rangle$ Zustand ankommen. Zum Beispiel mit $a = 3$ und $N = 35$ :

Also Überlagerungen 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 alle Eigenzustände von $M_a$. (Es gibt noch weitere Eigenzustände außer diesen. Aber uns interessieren nur diejenigen der oben genannten Form.)

Überprüfen Sie Ihr Verständnis

Finden Sie einen Eigenzustand der Unitarität, der $a=2$ und entspricht $N = 15$.

• Antwort
  $$\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}$$

  Also, die Reihenfolge $r=4$. Die Eigenzustände, die uns interessieren, sind eine gleichmäßige Überlagerung aller oben durchlaufenen Zustände 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 könnten unseren Qubit-Zustand in einen dieser Eigenzustände initialisieren (Spoiler: Das können wir nicht). Oder zumindest nicht ohne Weiteres. Wir werden in Kürze erklären, warum und was wir stattdessen tun können. Dann könnten wir QPE verwenden, um den entsprechenden Eigenwert zu schätzen, $\omega_j = e^{2 \pi i \theta_j}$ wobei $\theta_j = \frac{j}{r}$. Dann können wir die Ordnung $r$ mit der folgenden einfachen Gleichung bestimmen:

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

Aber denken Sie daran, ich habe gesagt, dass es sich um QPE -Schätzungen $\theta_j$ handelt – sie liefern uns keinen genauen Wert. Die Schätzung muss gut genug sein, um zwischen $r$ und unterscheiden $r+1$ zu können. Je mehr $m$ Kontrollqubits wir haben, desto besser wird die Schätzung sein. In den Aufgaben am Ende der Lektion werden Sie gebeten, das Minimum zu bestimmen $m$, das erforderlich ist, um eine Zahl zu $N$ faktorisieren.

Jetzt müssen wir ein Problem lösen. Alle oben genannten Erklärungen dazu, wie man findet, $r$ beginnen 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 machen 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 vorbereiten, der $|1\rangle$ in Binärform entspricht (wie in ) $|000...01\rangle$. Obwohl dieser Zustand selbst offensichtlich kein Eigenzustand von ist $M_a$, handelt es sich um eine Überlagerung aller Eigenzustände $|\psi_k\rangle$ :

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

Überprüfen Sie Ihr Verständnis

Überprüfen Sie, ob der Superposition über $|1\rangle$ den Eigenzuständen entspricht, die Sie für $N=15$ und $a=2$ in der vorherigen Kontrollfrage gefunden haben.

• Antwort

  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 können wir damit die Reihenfolge ermitteln $r$? Da der Ausgangszustand eine Überlagerung aller Eigenzustände der oben aufgeführten Form ist, schätzt der QPE-Algorithmus gleichzeitig jeden der, die $\theta_k$ diesen Eigenzuständen entsprechen. Die Messung der $m$ Kontrollqubits am Ende ergibt also eine Annäherung an den Wert $k/r$, wobei einer der zufällig ausgewählten $k \in \{0,1,2,...,r-1\}$ Eigenwerte ist. Wenn wir diesen Kreislauf einige Male wiederholen und einige Proben mit unterschiedlichen Werten von erhalten $k$, können wir schnell ableiten $r$.

Implementierung in Qiskit

Wie bereits erwähnt, ist unsere Hardware noch nicht so weit, dass wir riesige Zahlen wie RSA1024. Wir werden nur eine kleine Zahl faktorisieren, um zu zeigen, wie der Algorithmus funktioniert. Für diese Demo verwenden wir eine vereinfachte Version des Codes, der im Tutorial zum Shor-Algorithmus vorgestellt wurde. Wenn Sie weitere Informationen wünschen, besuchen Sie bitte das Tutorial.

Wir werden den Algorithmus unter Verwendung unseres Standard-Frameworks zur Lösung von Quantenproblemen ausführen, das als Qiskit-Patterns-Framework bezeichnet wird. Dies umfasst vier Schritte:

1. Ihr Problem auf einen Quantenschaltkreis abbilden
2. Optimieren Sie den Schaltkreis für den Betrieb auf Quantenhardware
3. Führen Sie Ihren Schaltkreis auf dem Quantencomputer aus
4. Die Messungen nachbearbeiten

1. Karte

Lassen Sie uns faktorisieren $N=15$ und als unsere $a=2$ teilerfremde ganze Zahl wählen.

Zunächst müssen wir die Schaltung konstruieren, die die modulare Multiplikations-Unität implementiert. Dies ist tatsächlich der schwierigste Teil der gesamten $M_a$ Implementierung und kann je nach Vorgehensweise sehr rechenintensiv sein. Dazu schummeln wir ein wenig: Wir wissen, dass wir $|1\rangle$ im Zustand beginnen, und aus einer früheren Check-in-Frage wissen wir, dass

Wir werden also eine Einheit konstruieren, die die richtigen Operationen auf diesen vier Zuständen ausführt, alle anderen Zustände jedoch unverändert lässt. Das ist Betrug, weil wir unser Wissen über die Reihenfolge von nutzen, um die $2\bmod 15$ Unitarität zu vereinfachen. Wenn wir tatsächlich versuchen würden, eine Zahl zu faktorisieren, deren Faktoren uns unbekannt sind, wäre uns dies nicht möglich.

Überprüfen Sie Ihr Verständnis

Konstruieren Sie anhand Ihres Wissens darüber, wie der $M_2$ Operator die oben genannten Zustände transformiert, den Operator aus einer Reihe von SWAP-Gattern, die die Zustände zweier Qubits austauschen. (Hinweis: Es ist hilfreich, jeden Zustand $|i\rangle$ in Binärform zu schreiben.)

• Antwort

  Schreiben wir die Aktion von $M_2$ auf die Zustände in Binärform 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 durchgeführt werden. $M_2|0001\rangle$ wird durch Vertauschen $1$ der Zustände von Qubit $0$ und erreicht. $M_2|0010\rangle$ wird durch Vertauschen der Zustände von Qubit $1$ und erreicht. Und $2$ so weiter. Wir können also die $M_2$ Matrix in die folgende Reihe von SWAP-Gattern zerlegen:

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

  Da wir uns daran erinnern, dass Operatoren von rechts nach links wirken, überprüfen wir, ob dies auf jeden der Zustände die gewünschte Wirkung 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 die Schaltung codieren, die diesem Operator in Qiskit entspricht.

Zunächst importieren wir die erforderlichen 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)

Output:

Der QPE-Algorithmus verwendet ein gesteuertes $U$ Gate. Nun, da wir einen $M_2$ Schaltkreis haben, müssen wir ihn zu einem geregelten$M_2$ Schaltkreis 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)

Output:

Jetzt haben wir unser gesteuertes $U$ Gate. Um jedoch den Quantenphasen-Schätzungsalgorithmus auszuführen, benötigen wir kontrollierte $U^2$, kontrollierte $U^4$, bis zu kontrollierte $U^{2^{m-1}}$, wobei die Anzahl $m$ der Qubits ist, die zur Schätzung der Phase verwendet werden. Je mehr Qubits, desto präziser wird die Phasenschätzung sein. Wir verwenden $m=8$ Kontroll-Qubits für unser Phasenschätzungsverfahren. Also brauchen wir:

wobei der Index $k$ mit dem $0 \le k \le m-1 = 7$ Steuerqubit 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)

Output:

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

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

Hinweis: Diese Vereinfachung funktioniert hier nur, weil die Reihenfolge von $2 \bmod 15$ ist $4$. Sobald $k=2$ (also $2^k = 4$ ), ist jede nachfolgende Potenz des Operators die Identität. Im Allgemeinen kann man bei größeren Zahlen $N$ oder anderen Werten für die Bildung der höheren $a$ Potenzen nicht überspringen. Dies ist ein Grund, warum dies als Spiel zeugbeispiel 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)

Output:

Und wie zuvor machen wir es zu einem 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)

Output:

Nun können wir alles zusammenfügen, um die Ordnung von $2\bmod 15$ mit einem Quantenschaltkreis unter Verwendung der Phasenschätzung zu ermitteln:

# 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)

Output:

2. Optimieren

Nachdem wir nun unseren Schaltkreis abgebildet haben, besteht der nächste Schritt darin, ihn für den Betrieb auf einem bestimmten Quantencomputer zu optimieren. Zuerst müssen wir das Backend laden.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Wenn Sie keine Zeit auf Ihrem Konto haben oder aus irgendeinem Grund einen Simulator verwenden möchten, können Sie die folgende Zelle ausführen, um einen Simulator einzurichten, der das oben ausgewählte Quanten-Gerä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)

Output:

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

3. Ausführen

# 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))

Output:

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 vier dominanten, indem wir einen Schwellenwert festlegen: Nur Werte oberhalb dieses Schwellenwerts werden als echtes Signal oberhalb des Rauschens 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

Bei Shors Algorithmus wird ein Großteil des Algorithmus klassisch ausgeführt. Also werden wir den Rest in den Schritt „Nachbearbeitung“ einfügen, nachdem wir unsere Messungen vom Quantencomputer erhalten haben. Jede der oben genannten Messungen kann in ganze Zahlen umgewandelt werden, die nach der Division durch unsere Annäherungswerte für sind $2^m$ $\frac{k}{r}$, wobei jedes Mal $k$ 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} ***")

Output:

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 Sie das Modul durchgearbeitet haben, werden Sie vielleicht eine neue Wertschätzung für die Genialität von Peter Shor entwickeln, der einen so cleveren Algorithmus entwickelt hat. Aber hoffentlich haben Sie auch ein neues Verständnis für seine trügerische Einfachheit gewonnen. Auch wenn der Algorithmus beeindruckend (oder einschüchternd) komplex erscheint, können Sie Shors Algorithmus ausführen, wenn Sie ihn in einzelne logische Schritte unterteilen und diese langsam durchgehen.

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

Fehler

Wichtige Konzepte:

• Moderne kryptografische Systeme basieren auf der klassischen Schwierigkeit, große ganze Zahlen zu faktorisieren.
• Die modulare Arithmetik – einschließlich der Strukturen $\mathbb{Z}_N$ und $\mathbb{Z}_N^*$ – bildet die mathematische Grundlage für Shors Algorithmus.
• Das Problem der Faktorisierung einer ganzen Zahl $N$ kann auf das Problem der Bestimmung der Ordnung einer Zahl modulo reduziert $N$ werden.
• Die Quantumsuchfunktion verwendet Techniken zur Quantumsphasenabschätzung, um die Periode der Funktion zu bestimmen $a^x \mod N$.
• Der Shor-Algorithmus besteht aus einem hybriden klassisch-quantenmechanischen Arbeitsablauf, bei dem eine Basis ausgewählt, die Quantenreihenfolge ermittelt und anschließend die Faktoren aus dem Ergebnis klassisch berechnet werden.

Richtig/Falsch:

1. Richtig oder falsch: Die Effizienz von Shors Algorithmus gefährdet die Sicherheit der RSA-Verschlüsselung.
2. Richtig oder falsch: Der Shor-Algorithmus kann auf jedem modernen Quantencomputer effizient ausgeführt werden.
3. T/F Der Shor-Algorithmus verwendet die Quantenphasenschätzung (QPE) als wichtige Unterroutine.
4. Richtig oder falsch? Der klassische Teil von Shors Algorithmus umfasst die Berechnung des größten gemeinsamen Teilers (GCD).
5. Richtig oder falsch: Der Shor-Algorithmus funktioniert nur für die Faktorisierung gerader Zahlen.
6. Richtig oder falsch? Eine erfolgreiche Ausführung des Shor-Algorithmus garantiert immer die korrekten Faktoren.

Kurze Antwort:

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

Herausfordernde Probleme:

1. Wie viele Kontrollqubits $m$ benötigen wir für eine bestimmte Zahl $N$, die wir faktorisieren möchten, um die erforderliche Genauigkeit im QPE zu erzielen, um den korrekten Wert der Ordnung zu finden $r$?

2. Befolgen Sie die hier beschriebene Vorgehensweise, um 15 zu faktorisieren, und versuchen Sie nun, 21 zu faktorisieren.