imported>Aka: /* Fehlende praktische Anwendbarkeit */ Tippfehler entfernt

2025-12-22T23:21:10Z

Fehlende praktische Anwendbarkeit: Tippfehler entfernt

Neue Seite

Der '''Shor-Algorithmus''' ist ein [[Algorithmus]] aus dem [[Teilgebiete der Mathematik|mathematischen Teilgebiet]] der [[Restklassenring]]e innerhalb der [[Zahlentheorie]], der Mittel der [[Quanteninformatik]] benutzt. Er berechnet einen [[Nichttrivialer Teiler|nichttrivialen Teiler]] einer [[Zusammengesetzte Zahl|zusammengesetzten Zahl]] und zählt somit zur Klasse der [[Faktorisierungsverfahren]]. Er ist einer der wichtigsten [[Quantenalgorithmus|Quantenalgorithmen]].

Der Algorithmus wurde 1994 von [[Peter Shor]] veröffentlicht, der damals bei den [[Bell Laboratories|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''.<ref name="SHOR">Peter W. Shor: ''Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.'' In: ''SIAM Journal on Computing.'' 26/1997, S. 1484–1509, {{arXiv|quant-ph/9508027}}</ref> Darin wird auch noch ein zweiter Algorithmus zur Berechnung des [[Diskreter Logarithmus|diskreten Logarithmus]] beschrieben, der ebenfalls als Shor-Algorithmus bezeichnet wird. Im Allgemeinen wird diese Bezeichnung jedoch für das Faktorisierungsverfahren verwendet.

== Fehlende praktische Anwendbarkeit ==
Für praktisch relevante Aufgabenstellungen ist der Shor-Algorithmus mit Stand 2020 nicht anwendbar, da keine hinreichend großen und fehlerarmen [[Quantencomputer]] zur Verfügung stehen. Um eine Zahl <math>n</math> mit <math>N</math> [[Dualsystem|Binärstellen]] (d. h., <math>n<2^N</math>) zu faktorisieren, benötigt ein Quantencomputer ein [[Quantencomputer#Quantenregister, Verschränkung|Quantenregister]], dessen Größe mindestens linear mit der Zahl der Binärstellen wächst. Der ursprüngliche Algorithmus von Shor benötigt ''3N'' [[Qubit]]s, die beste bekannte Variante kommt mit ''2N+3'' Qubits aus.<ref name="GiEk2019">{{Literatur |Autor=Craig Gidney, Martin Ekerå |Titel=How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits |Sammelwerk=Quantum |Band=5 |Datum=2019-05-23 |Seiten=433 |Fundstelle=Tabellen 1 und 2 |Sprache=en |arXiv=1905.09749 |DOI=10.22331/q-2021-04-15-433}}</ref> Diese Zahlen gelten für einen idealen (fehlerfreien) Quantencomputer. In der Praxis ist es nötig, [[Quantenfehlerkorrektur]]verfahren 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. Schätzungen gehen davon aus, dass für eine 2048-bit-Zahl 10 bis 100 Millionen Qubits benötigt werden<ref name="GiEk2019" /> (im fehlerfreien Fall wären es nur einige tausend). Eine Forschungsgruppe des [[Vereinigte Staaten|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.<ref name="VANDER">[[Lieven Vandersypen]], Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood und [[Isaac Chuang|Isaac L. Chuang]]: ''Experimental realization of an order-finding algorithm with an NMR quantum computer.'' In: ''[[Nature]].'' 414/2001, S. 883–887, [[doi:10.1038/414883a]]</ref>

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

== 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-Algorithmus|Monte-Carlo-Algorithmen]].
* Eingabe: Eine zusammengesetzte Zahl <math>n</math>.
* Ausgabe: Ein nichttrivialer Faktor von <math>n</math>.
* Laufzeit: <math>O\left( (\log\, n)^3 \right)</math> Gatteroperationen.

== Zahlentheoretischer Hintergrund ==
Der Algorithmus von Shor ist eine für Quantencomputer angepasste Version eines Algorithmus für [[Primzahltest]]s von [[Michael O. Rabin|M. O. Rabin]] (1976), bei der die Faktorisierung einer Zahl auf die Bestimmung der Ordnung in <math>\Z_n</math> zurückgeführt wird (siehe [[Miller-Rabin-Test]]).

== Ablauf ==
Die grundlegende Idee ist, dass man die [[Faktorisierung]] auf die Bestimmung der [[Ordnung eines Gruppenelementes|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 ===
# Wähle eine Zahl <math>x</math> mit <math>1<x<n</math>.
# Bestimme den <math>\textrm{ggT}(x,n)</math> (ggT bezeichnet den [[Größter gemeinsamer Teiler|größten gemeinsamen Teiler]], der z. B. mittels des [[Euklidischer Algorithmus|Euklidischen Algorithmus]] berechnet werden kann). Falls das Ergebnis ungleich 1 ist, gib dies als Lösung zurück und terminiere. Sonst fahre mit dem nächsten Schritt fort.
# Bestimme mit Hilfe des Quantenteils (s. u.) die Ordnung <math>r</math> von <math>x</math> in der [[Prime Restklassengruppe|primen Restklassengruppe]] <math>(\mathbb Z/n\mathbb Z)^\times</math>, d. h. das kleinste <math>r\in\mathbb{N}</math>, so dass <math>x^r\equiv 1 \pmod n</math>. Schritt 2 stellte sicher, dass ein solches <math>r</math> existiert.
# Beginne erneut bei 1, falls:
## <math>r</math> ungerade ist, oder
## <math>x^{r/2}\equiv -1 \pmod n</math>.
# Gib <math>\textrm{ggT}(x^{r/2} + 1, n)</math> als Lösung zurück.

==== Lösung im letzten Schritt ====
Betrachte das Produkt (<math>x^{r/2}-1</math>) · (<math>x^{r/2} +1</math>) = <math>x^r -1</math>. Wir wissen:
* <math>x^r -1 \equiv 0 \pmod n</math>,     wegen Schritt 3,
* <math>x^{r/2}+1 \not\equiv 0 \pmod n</math>,     wegen Schritt 4, und
* <math>x^{r/2}-1 \not\equiv 0 \pmod n</math>,     wegen Schritt 3, da <math>r</math> die kleinste Zahl mit <math>x^r -1\equiv 0 \pmod n</math> ist und <math>{r/2} < r</math> gilt.
Aus alldem zusammen folgt, dass <math>x^{r/2} -1</math> nichttriviale Teiler von <math>n</math> enthält; der [[Euklidischer Algorithmus|euklidische Algorithmus]] zur Berechnung des <math>\textrm{ggT}</math> liefert diese Teiler in Polynomialzeit.

==== Anzahl Iterationen für die Teilerfindung ====
Die Wahrscheinlichkeit, bei zufälliger Wahl von <math>x</math> keinen Teiler zu erhalten, beträgt maximal <math>\tfrac{1}{2^{k-1}}</math>, wobei <math>k</math> die Anzahl voneinander verschiedener Primfaktoren von <math>n</math> (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 <math>t</math> Durchgängen immer noch keinen Erfolg zu haben, hat die Wahrscheinlichkeit <math>\tfrac{1}{2^t}</math>.

=== Quantenteil ===
# Bestimme <math>q</math> als Potenz von 2 mit <math>n^2 \le q < 2n^2</math>.
# Initialisiere das erste Quantenregister (Eingaberegister) mit der [[Superposition (Physik)|Superposition]] (siehe [[Qubit]]) aller Zustände <math>a \bmod q</math> (<math>a</math> ist eine Zahl kleiner als <math>q</math>). Dies führt in den Zustand: <math>\frac {1}{q^{1\;\!\!/2}} \sum_{a=0}^{q-1} | a \rangle \ | 0 \rangle</math>.
# Initialisiere das zweite Register (Ausgaberegister) mit der Superposition der Zustände <math>x^a \bmod n</math>. Das Ergebnis ist der Zustand: <math>\frac {1}{q^{1\;\!\!/2}} \sum_{a=0}^{q-1} | a \rangle \ | x^a \bmod n \rangle</math>.
# Führe auf dem ersten Register die [[Quanten-Fouriertransformation]] durch, wobei <math>\mathrm{QFT} \left( | a \rangle \right) = \frac {1}{q^{1\;\!\!/2}} \sum_{c=0}^{q-1} e^{2\pi i\;\! ac/q} \ | c \rangle</math>, so dass sich ergibt: <math>\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</math>.
# Führe eine Messung durch (entnimm den Inhalt der Register). Die Wahrscheinlichkeit für den Zustand <math>\left| c, x^k \bmod n\right\rangle</math> mit <math>0 < k < r</math> ergibt sich zu: <math>\Biggl| \frac {1}{q}\!\! \ \sum_{a: x^a \equiv x^k}\!\!\! e^{2\pi i\;\! ac/q} \Biggr|_{}^{\,2}</math>. Hierfür gilt die Beziehung <math>a\equiv k\!\!\!\! \mod r</math> bzw. <math>a=br+k</math>, sodass wir schreiben können: <math>\Biggl| \frac {1}{q} \ \sum_{b} e^{2\pi i \left(br + k\right)c/q} \Biggr|^{\,2}</math>. Diese diskrete Funktion verfügt durch Amplifikation über charakteristische Maxima für Werte einer Variablen <math>d \in \mathbb{Z}</math>, die die Beziehung <math>\left| \frac {c}{q} - \frac {d}{r} \right| \le \frac {1}{2q}</math> erfüllen. Es lässt sich zeigen, dass es für die angegebenen Beziehungen von <math>q,r</math> und <math>n</math> höchstens einen solchen Wert bei festem <math>c</math> gibt. Damit lässt sich <math>r</math> berechnen, falls <math>d</math> und <math>r</math> [[Teilerfremdheit|teilerfremd]] sind. Die Wahrscheinlichkeit für diesen Fall beträgt mindestens <math>\tfrac {\phi (r)}{3r}</math> oder <math>\Omega\!\left(\tfrac {1}{\log \log r}\right)</math>, das heißt, wir erhalten <math>r</math> mit hoher Wahrscheinlichkeit nach <math>O (\log \log r)</math> Wiederholungen.
# Gib den berechneten Wert <math>r^\prime</math> zurück, wenn er tatsächlich die Ordnung von <math>x</math> ist, ansonsten wiederhole das Experiment.

== Literatur ==
* {{Literatur |Autor=M. Homeister |Titel=Quantum Computing verstehen |Auflage=5 |Verlag=Springer Vieweg |Ort=Wiesbaden |Datum=2018 |ISBN=978-3-658-22883-5 |Seiten=223 ff.}}
* {{Literatur |Autor=B. Lenze |Titel=Mathematik und Quantum Computing |Auflage=2 |Verlag=Logos Verlag |Ort=Berlin |Datum=2020 |ISBN=978-3-8325-4716-5 |Seiten=89 ff.}}
* {{Literatur |Autor=R. J. Lipton, K. W. Regan |Titel=Quantum Algorithms via Linear Algebra: A Primer |Verlag=MIT Press |Ort=[[Cambridge]] |Datum=2014 |ISBN=978-0-262-02839-4 |Seiten=97 ff. |Sprache=en|Online = {{Google Buch| BuchID= ajPBBQAAQBAJ}} }}
* {{Literatur |Autor=[[Michael Nielsen|M. A. Nielsen]], [[Isaac Chuang|I. L. Chuang]] |Titel=Quantum Computation and Quantum Information |Verlag=Cambridge University Press |Ort=Cambridge |Datum=2010 |ISBN=978-1-107-00217-3 |Seiten=234 ff. |Sprache=en|Online=https://profmcruz.files.wordpress.com/2017/08/quantum-computation-and-quantum-information-nielsen-chuang.pdf}}
* {{Literatur |Autor=W. Scherer |Titel=Mathematik der Quanteninformatik |Verlag=Springer-Verlag |Ort=Berlin / Heidelberg |Datum=2016 |ISBN=978-3-662-49079-2 |Seiten=206 ff.}}
* {{Literatur |Autor=C. P. Williams |Titel=Explorations in Quantum Computing |Auflage=2 |Verlag=Springer-Verlag |Ort=London |Datum=2011 |ISBN=978-1-84628-886-9 |Seiten=272 ff. |Sprache=en}}
* {{Literatur |Autor=IBM Research Division |Titel=IBM’s Test-Tube Quantum Computer Makes History; First Demonstration Of Shor’s Historic Factoring Algorithm |Verlag=ScienceDaily |Datum=2001-12-20 |Sprache=en |Online=https://www.sciencedaily.com/releases/2001/12/011220081620.htm |Abruf=2021-07-08}}

== Weblinks ==
* Burkhard Lenze: ''Mathematik und Quantum Computing'' [https://gatekeeper-ng.informatik.fh-dortmund.de/personen/professoren/lenze/mqc-www.pdf ''Ergänzungsmaterial zum gleichnamigen Buch''] Abschnitt ''Shor-Algorithmus''
* Burak Aktas: ''Quantum Computing und Shor-Algorithmus'' [https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/26053/quantum_computing.pdf Online] [[Universität Ulm]] 2019

== Einzelnachweise ==
<references />

[[Kategorie:Faktorisierungsverfahren]]
[[Kategorie:Quanteninformatik]]

Shor-Algorithmus - Versionsgeschichte

imported>Aka: /* Fehlende praktische Anwendbarkeit */ Tippfehler entfernt