Shor-Algorithmus

Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, der Mittel der Quanteninformatik benutzt. Er berechnet auf einem Quantencomputer einen nichttrivialen Teiler einer zusammengesetzten Zahl und zählt somit zur Klasse der Faktorisierungsverfahren.

Für praktisch relevante Aufgabenstellungen ist der Shor-Algorithmus noch nicht anwendbar, da bisher (Stand 2020) keine hinreichend großen und fehlerarmen Quantencomputer zur Verfügung stehen. Um eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} Binärstellen (d. h., Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n<2^N} ) zu faktorisieren, benötigt ein Quantencomputer ein Quantenregister, dessen Größe mindestens linear mit der Zahl der Binärstellen wächst. Der ursprüngliche Algorithmus von Shor benötigt 3N Qubits, die beste bekannte Variante kommt mit 2N+3 Qubits aus. Diese Zahlen gelten für einen idealen (fehlerfreien) Quantencomputer. In der Praxis ist es nötig, Quantenfehlerkorrekturverfahren zu verwenden. Dann werden um einen (großen, aber in N konstanten) Faktor M mehr physische Qubits benötigt, wobei M sehr stark von der Fehlerrate und dem verwendeten Fehlerkorrekturcode abhängt. Man schätzt, dass für eine 2048-bit-Zahl 10 bis 100 Millionen Qubits benötigt werden (im fehlerfreien Fall wären es nur einige tausend). Eine Forschungsgruppe des US-amerikanischen Unternehmens IBM hat beispielsweise im Jahr 2001 einen Quantencomputer mit sieben Qubits eingesetzt, um die Zahl 15 in die Faktoren 5 und 3 zu zerlegen.

Der Shor-Algorithmus ist für die Kryptographie sehr bedeutend, weil er einen nichttrivialen Teiler essenziell schneller findet als klassische Algorithmen: Während diese subexponentielle, jedoch deutlich höher als polynomielle Laufzeit benötigen, hat der Shor-Algorithmus nur polynomielle Laufzeit. Dies stellt beispielsweise eine Gefahr für die häufig zur verschlüsselten Datenübertragung verwendeten RSA-Kryptosysteme dar, deren Sicherheit gerade auf der Annahme beruht, dass kein Faktorisierungsverfahren mit polynomieller Laufzeit existiert.

Der Algorithmus wurde 1994 von Peter Shor veröffentlicht, der damals bei den AT&T Bell Laboratories beschäftigt war. Die Arbeit trägt den Titel Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Darin wird auch noch ein zweiter Algorithmus zur Berechnung des diskreten Logarithmus beschrieben, der ebenfalls als Shor-Algorithmus bezeichnet wird. Im Allgemeinen wird diese Bezeichnung jedoch für das Faktorisierungsverfahren verwendet.

Eigenschaften

Der Shor-Algorithmus ist ein probabilistischer Algorithmus. In einigen, je nach Anzahl der Wiederholungen beliebig wenigen, Fällen führt er zu keinem Ergebnis; der Algorithmus zählt somit zur Klasse der Monte-Carlo-Algorithmen.

• Eingabe: Eine zusammengesetzte Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} .
• Ausgabe: Ein nichttrivialer Faktor von $n$.
• Laufzeit: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left( (\log\, n)^3 \right)} Gatteroperationen.

Ablauf

Die grundlegende Idee ist, dass man die Faktorisierung auf die Bestimmung der Ordnung zurückführen kann. Diese Bestimmung lässt sich mit Hilfe der Quanten-Fouriertransformation effektiv durchführen. Man teilt den Algorithmus deshalb häufig in einen klassischen Teil zur Reduzierung des Problems und einen Quantenteil, der das Restproblem effizient löst.

Klassischer Teil

1. Wähle eine Zahl $x$ mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1<x<n} .
2. Bestimme den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ggT} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x} ,$n)$ (z. B. mittels des Euklidischen Algorithmus). Falls das Ergebnis ungleich 1 ist, gib dies als Lösung zurück und terminiere. Sonst fahre mit dem nächsten Schritt fort.
3. Bestimme mit Hilfe des Quantenteils (s. u.) die Ordnung $r$ von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} in der primen Restklassengruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\mathbb Z/n\mathbb Z)^\times} , d. h. das kleinste $r\in \mathbb {N}$, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^r\equiv 1 \pmod n} . Schritt 2 stellte sicher, dass ein solches Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} existiert.
4. Beginne erneut bei 1, falls:
   1. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} ungerade ist, oder
   2. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^{r/2}\equiv -1 \pmod n} .
5. Gib Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{ggT}(x^{r/2} - 1, n)} als Lösung zurück.

Lösung im letzten Schritt

Betrachte das Produkt (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^{r/2}-1} ) · ($x^{r/2}+1$) = $x^{r}-1$. Wir wissen:

• $x^{r}-1\equiv 0{\pmod {n}}$,     wegen Schritt 3,
• $x^{r/2}+1\not \equiv 0{\pmod {n}}$,     wegen Schritt 4, und
• $x^{r/2}-1\not \equiv 0{\pmod {n}}$,     wegen Schritt 3, da $r$ die kleinste Zahl mit $x^{r}-1\equiv 0{\pmod {n}}$ ist und ${r/2}<r$ gilt.

Aus alldem zusammen folgt, dass $x^{r/2}-1$ nichttriviale Teiler von $n$ enthält; der euklidische Algorithmus zur Berechnung des $ggT$ liefert diese Teiler in Polynomialzeit.

Anzahl Iterationen für die Teilerfindung

Die Wahrscheinlichkeit, bei zufälliger Wahl von $x$ keinen Teiler zu erhalten, beträgt maximal ${\tfrac {1}{2^{k-1}}}$, wobei $k$ die Anzahl voneinander verschiedener Primfaktoren von $n$ (außer 2) ist. Bei einer aus nur zwei Primfaktoren zusammengesetzten Zahl (worst case) erhält man pro Durchgang mit einer Wahrscheinlichkeit von 1/2 eine Lösung, nach $t$ Durchgängen immer noch keinen Erfolg zu haben, hat die Wahrscheinlichkeit ${\tfrac {1}{2^{t}}}$.

Quantenteil

1. Bestimme Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} als Potenz von 2 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^2 \le q < 2n^2} .
2. Initialisiere das erste Quantenregister (Eingaberegister) mit der Superposition (siehe Qubit) aller Zustände Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \bmod q} ($a$ ist eine Zahl kleiner als $q$).
   Dies führt in den Zustand:
   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac {1}{q^{1\;\!\!/2}} \sum_{a=0}^{q-1} | a \rangle \ | 0 \rangle} .
3. Initialisiere das zweite Register (Ausgaberegister) mit der Superposition der Zustände Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^a \bmod n} .
   Das Ergebnis ist der Zustand:
   ${\frac {1}{q^{1\;\!\!/2}}}\sum _{a=0}^{q-1}|a\rangle \ |x^{a}{\bmod {n}}\rangle$.
4. Führe auf dem ersten Register die Quanten-Fouriertransformation durch, wobei
   $\mathrm {QFT} \left(|a\rangle \right)={\frac {1}{q^{1\;\!\!/2}}}\sum _{c=0}^{q-1}e^{2\pi i\;\!ac/q}\ |c\rangle$,
   so dass sich ergibt:
   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac {1}{q} \ \sum_{a=0}^{q-1} \ \sum_{c=0}^{q-1} e^{2\pi i\;\! ac/q} \ | c \rangle \ | x^a \bmod n \rangle} .
5. Führe eine Messung durch (entnimm den Inhalt der Register). Die Wahrscheinlichkeit für den Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left| c, x^k \bmod n\right\rangle} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 < k < r} ergibt sich zu:
   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Biggl| \frac {1}{q}\!\! \ \sum_{a: x^a \equiv x^k}\!\!\! e^{2\pi i\;\! ac/q} \Biggr|_{}^{\,2}} .
   Hierfür gilt die Beziehung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\equiv k\!\!\!\! \mod r} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a=br+k} , sodass wir schreiben können:
   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Biggl| \frac {1}{q} \ \sum_{b} e^{2\pi i \left(br + k\right)c/q} \Biggr|^{\,2}} .
   Diese diskrete Funktion verfügt durch Amplifikation über charakteristische Maxima für Werte einer Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d \in \mathbb{Z}} , die die Beziehung
   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left| \frac {c}{q} - \frac {d}{r} \right| \le \frac {1}{2q}}
   erfüllen. Es lässt sich zeigen, dass es für die angegebenen Beziehungen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q,r} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} höchstens einen solchen Wert bei festem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} gibt.
   Damit lässt sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} berechnen, falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} teilerfremd sind.
   Die Wahrscheinlichkeit für diesen Fall beträgt mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac {\phi (r)}{3r}} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega\!\left(\tfrac {1}{\log \log r}\right)} , das heißt, wir erhalten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} mit hoher Wahrscheinlichkeit nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O (\log \log r)} Wiederholungen.
6. Gib den berechneten Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r^\prime} zurück, wenn er tatsächlich die Ordnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} ist, ansonsten wiederhole das Experiment.

Literatur

• M. Homeister: Quantum Computing verstehen. 5. Auflage. Springer Vieweg, Wiesbaden 2018, ISBN 978-3-658-22883-5, S. 223 ff. 
• B. Lenze: Mathematik und Quantum Computing. 2. Auflage. Logos Verlag, Berlin 2020, ISBN 978-3-8325-4716-5, S. 89 ff. 
• R. J. Lipton, K. W. Regan: Quantum Algorithms via Linear Algebra: A Primer. MIT Press, Cambridge 2014, ISBN 978-0-262-02839-4, S. 97 ff. (englisch). 
• M. A. Nielsen, I. L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge 2010, ISBN 978-1-107-00217-3, S. 234 ff. (englisch). 
• W. Scherer: Mathematik der Quanteninformatik. Springer-Verlag, Berlin / Heidelberg 2016, ISBN 978-3-662-49079-2, S. 206 ff. 
• C. P. Williams: Explorations in Quantum Computing. 2. Auflage. Springer-Verlag, London 2011, ISBN 978-1-84628-886-9, S. 272 ff. (englisch). 
• IBM Research Division: IBM’s Test-Tube Quantum Computer Makes History; First Demonstration Of Shor’s Historic Factoring Algorithm. ScienceDaily, 20. Dezember 2001 (englisch, sciencedaily.com [abgerufen am 8. Juli 2021]).