Shors Algorithmus

Shors Algorithmus ist ein Quantenalgorithmus zur Primfaktorzerlegung einer ganzen Zahl. Er wurde 1994 von dem amerikanischen Mathematiker Peter Shor entwickelt . ^{[ 1 ] [ 2 ]} Er ist einer der wenigen bekannten Quantenalgorithmen mit vielversprechenden Anwendungsmöglichkeiten und starken Hinweisen auf eine superpolynomielle Beschleunigung im Vergleich zu den besten bekannten klassischen (nicht-quantenmechanischen) Algorithmen. ^{[ 3 ]} Um klassische Computer zu übertreffen, könnten jedoch aufgrund des durch die Quantenfehlerkorrektur verursachten Aufwands Quantencomputer mit Millionen von Qubits erforderlich sein . ^{[ 4 ]}

Shor schlug mehrere ähnliche Algorithmen zur Lösung des Faktorisierungsproblems , des Problems des diskreten Logarithmus und des Periodenbestimmungsproblems vor. „Shors Algorithmus“ bezieht sich üblicherweise auf den Faktorisierungsalgorithmus, kann aber jeden der drei Algorithmen bezeichnen. Der Algorithmus für den diskreten Logarithmus und der Faktorisierungsalgorithmus sind Instanzen des Periodenbestimmungsalgorithmus, und alle drei sind Instanzen des Problems der verborgenen Untergruppe .

Auf einem Quantencomputer benötigt Shors Algorithmus zur Faktorisierung einer ganzen Zahl n polynomielle Zeit , d. h. die benötigte Zeit ist polynomiell in O(n²) . ^{[ 5 ]} Er benötigt Quantengatter der Ordnung O (n²) bei Verwendung schneller Multiplikation ^{[ 6 ]} oder sogar des derzeit asymptotisch schnellsten bekannten Multiplikationsalgorithmus von Harvey und van der Hoeven [ ^{7 ].} Dies zeigt, dass das ^Problem der Faktorisierung ganzer Zahlen zur Komplexitätsklasse BQP gehört . Shors Algorithmus ist asymptotisch schneller als der skalierbarste klassische Faktorisierungsalgorithmus, das allgemeine Zahlkörpersieb , das in subexponentieller Zeit arbeitet : O(n²) . ^{[ 8 ]}${\displaystyle N}$${\displaystyle \log N}$${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$

Angenommen, ein Quantencomputer mit einer ausreichenden Anzahl von Qubits könnte ohne Quantenrauschen und andere Quantendekohärenzphänomene arbeiten , dann könnte Shors Algorithmus verwendet werden, um Public-Key-Kryptographieverfahren wie beispielsweise zu knacken.

• Das RSA- Schema
• Der Diffie-Hellman -Schlüsselaustausch für endliche Körper
• Der Diffie-Hellman- Schlüsselaustausch auf elliptischen Kurven ^{[ 9 ]}

RSA kann geknackt werden, wenn die Faktorisierung großer ganzer Zahlen rechnerisch möglich ist. Soweit bekannt, ist dies mit klassischen (nicht-quantenmechanischen) Computern nicht möglich; es ist kein klassischer Algorithmus bekannt, der ganze Zahlen in Polynomialzeit faktorisieren kann. Shors Algorithmus zeigt jedoch, dass die Faktorisierung ganzer Zahlen mit einem Schaltkreis polynomieller Komplexität auf einem idealen Quantencomputer möglich ist. Daher könnte es realisierbar sein, RSA durch den Bau eines ausreichend leistungsstarken Quantencomputers zu überwinden. Dies war ein starker Anstoß für die Entwicklung und den Bau von Quantencomputern sowie für die Erforschung neuer Quantencomputer-Algorithmen. Es hat auch die Forschung an neuen Kryptosystemen, die vor Quantencomputern sicher sind – zusammengefasst als Post-Quanten-Kryptographie (PQC) –, vorangetrieben.

Aufgrund der hohen Fehlerraten von Quantencomputern und der begrenzten Anzahl physikalischer Qubits, die für die Quantenfehlerkorrektur zur Verfügung stehen , erzielen Labordemonstrationen von Shors Algorithmus ab 2026 nur in einem Bruchteil der Versuche korrekte Ergebnisse und waren bisher nur bei kleinen Semiprimzahlen erfolgreich .

Im Jahr 2001 demonstrierte eine Gruppe bei IBM Shors Algorithmus , indem sie ihn mithilfe einer NMR-Implementierung eines Quantencomputers mit sieben Qubits faktorisierte. ^{[ 10 ]} Nach der IBM-Implementierung implementierten zwei unabhängige Gruppen Shors Algorithmus mit photonischen Qubits und betonten, dass beim Ausführen von Schaltkreisen des Algorithmus Mehrqubit- Verschränkung beobachtet wurde. ^{[ 11 ] [ 12 ]} Im Jahr 2012 wurde die Faktorisierung von mit Festkörper-Qubits durchgeführt. ^{[ 13 ]} Später, ebenfalls im Jahr 2012, wurde die Faktorisierung von erreicht. ^{[ 14 ]} Im Jahr 2016 wurde die Faktorisierung von erneut mit gefangenen Ionen-Qubits durchgeführt. ^{[ 15 ]} Allerdings erfüllt keine dieser Demonstrationen die Anforderungen von Shors Algorithmus: Sie kompilieren den Schaltkreis unter Verwendung von Vorwissen über die Lösung, und einige haben den Algorithmus sogar so stark vereinfacht, dass er einem Münzwurf gleichkommt. ^{[ 16 ]}${\displaystyle 15}$${\displaystyle 3\times 5}$${\displaystyle 15}$${\displaystyle 21}$${\displaystyle 15}$

Das Problem, das wir zu lösen versuchen, lautet: Gegeben sei eine ungerade zusammengesetzte Zahl . Finde ihre ganzzahligen Faktoren${\displaystyle N}$ .

Um dies zu erreichen, besteht Shors Algorithmus aus zwei Teilen:

1. Eine klassische Reduktion des Faktorisierungsproblems auf das Problem der Ordnungsbestimmung . Diese Reduktion ähnelt derjenigen, die für andere Faktorisierungsalgorithmen , wie beispielsweise das quadratische Sieb , verwendet wird .
2. Ein Quantenalgorithmus zur Lösung des Ordnungsfindungsproblems.

Ein vollständiger Faktorisierungsalgorithmus ist möglich, wenn wir in der Lage sind, eine beliebige Zahl effizient in nur zwei ganze Zahlen größer als 1 zu faktorisieren, denn wenn entweder oder keine Primzahl ist, kann der Faktorisierungsalgorithmus wiederum auf diese beiden Zahlen angewendet werden, bis nur noch Primzahlen übrig bleiben. ${\displaystyle N}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle q}$

Eine grundlegende Beobachtung ist, dass wir mithilfe des euklidischen Algorithmus den größten gemeinsamen Teiler (ggT) zweier ganzer Zahlen stets effizient berechnen können . Dies bedeutet insbesondere, dass wir effizient überprüfen können, ob n gerade ist, in welchem ​​Fall 2 trivialerweise ein Faktor ist. Nehmen wir daher für den Rest dieser Diskussion an, dass n ungerade ist. Anschließend können wir effiziente klassische Algorithmen verwenden, um zu überprüfen, ob n eine Primzahlpotenz ist . ^{[ 17 ]} Für Primzahlpotenzen existieren effiziente klassische Faktorisierungsalgorithmen, ^{[ 18 ]} daher kann der Rest des Quantenalgorithmus davon ausgehen, dass n keine Primzahlpotenz ist. ${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$

Falls diese einfachen Fälle keinen nichttrivialen Faktor von ergeben , fährt der Algorithmus mit dem verbleibenden Fall fort. Wir wählen eine zufällige ganze Zahl. Ein möglicher nichttrivialer Teiler von kann durch die Berechnung von gefunden werden , was klassisch und effizient mit dem euklidischen Algorithmus erfolgen kann . Falls dies einen nichttrivialen Faktor ergibt (d. h. ), ist der Algorithmus beendet, und der andere nichttriviale Faktor ist . Falls kein nichttrivialer Faktor gefunden wurde, bedeutet dies, dass und die Wahl von teilerfremd sind , sodass in der multiplikativen Gruppe der ganzen Zahlen modulo enthalten ist und ein multiplikatives Inverses modulo besitzt . Somit hat die multiplikative Ordnung modulo , was bedeutet ${\displaystyle N}$${\displaystyle 2\leq a<N{.}}$${\displaystyle N}$${\displaystyle \gcd(a,N)}$${\displaystyle \gcd(a,N)\neq 1}$${\displaystyle N/\gcd(a,N)}$${\displaystyle N}$${\displaystyle a}$${\displaystyle a}$${\displaystyle N}$${\displaystyle N}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N}$

${\displaystyle a^{r}\equiv 1{\bmod {N}},}$

und ist die kleinste positive ganze Zahl, die diese Kongruenz erfüllt. ${\displaystyle r}$

Die Quanten-Subroutine findet . Aus der Kongruenz lässt sich erkennen, dass teilt , geschrieben . Dies lässt sich mithilfe der Differenz von Quadraten faktorisieren : Da wir den Ausdruck auf diese Weise faktorisiert haben, funktioniert der Algorithmus nicht für ungerade (da eine ganze Zahl sein muss), was bedeutet, dass der Algorithmus mit einem neuen neu starten müsste . Im Folgenden können wir daher annehmen, dass gerade ist. Es kann nicht der Fall sein, dass , da dies implizieren würde , was wiederum widersprüchlich wäre, dass die Ordnung von wäre , was bereits war . An diesem Punkt kann es der Fall sein oder auch nicht, dass . Wenn nicht teilt , bedeutet dies, dass wir einen nichttrivialen Faktor von finden können . Wir berechnen . Wenn , dann war wahr, und ein nichttrivialer Faktor von kann nicht aus erreicht werden , und der Algorithmus muss mit einem neuen neu starten . Andernfalls haben wir einen nichttrivialen Faktor von gefunden , wobei der andere ist , und der Algorithmus ist beendet. Für diesen Schritt ist es auch äquivalent, zu berechnen ; Es wird einen nichttrivialen Faktor erzeugen, wenn nichttrivial ist, und keinen, wenn es trivial ist (wobei ). ${\displaystyle r}$${\displaystyle N}$${\displaystyle a^{r}-1}$${\displaystyle N\mid a^{r}-1}$$${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1).}$$${\displaystyle r}$${\displaystyle a^{r/2}}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N\mid a^{r/2}-1}$${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$${\displaystyle r/2}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N\mid a^{r/2}+1}$${\displaystyle N}$${\displaystyle a^{r/2}+1}$${\displaystyle N}$$${\displaystyle d=\gcd(N,a^{r/2}-1).}$$${\displaystyle d=1}$${\displaystyle N\mid a^{r/2}+1}$${\displaystyle N}$${\displaystyle a}$${\displaystyle a}$${\displaystyle N}$${\displaystyle N/d}$${\displaystyle \gcd(N,a^{r/2}+1)}$${\displaystyle \gcd(N,a^{r/2}-1)}$${\displaystyle N\mid a^{r/2}+1}$

Der Algorithmus lautet in Kürze wie folgt: Sei ungerade und keine Primzahlpotenz. Wir wollen zwei nichttriviale Faktoren von ausgeben . ${\displaystyle N}$${\displaystyle N}$

1. Wähle eine Zufallszahl .${\displaystyle 1<a<N}$
2. Berechne , den größten gemeinsamen Teiler von und .${\displaystyle K=\gcd(a,N)}$${\displaystyle a}$${\displaystyle N}$
3. Wenn , dann ist ein nichttrivialer Faktor von , wobei der andere Faktor ist , und wir sind fertig.${\displaystyle K\neq 1}$${\displaystyle K}$${\displaystyle N}$${\displaystyle N/K}$
4. Andernfalls verwenden Sie die Quanten-Subroutine, um die Ordnung von zu bestimmen .${\displaystyle r}$${\displaystyle a}$
5. Falls das Ergebnis ungerade ist, gehe zurück zu Schritt 1.${\displaystyle r}$
6. Berechne . Falls nichttrivial ist, ist der andere Faktor , und wir sind fertig. Andernfalls gehe zurück zu Schritt 1.${\displaystyle g=\gcd(N,a^{r/2}+1)}$${\displaystyle g}$${\displaystyle N/g}$

Es hat sich gezeigt, dass dies nach wenigen Durchläufen wahrscheinlich gelingt. ^{[ 2 ]} In der Praxis genügt ein einziger Aufruf der Quantenordnungsfindungsroutine, um mit sehr hoher Erfolgswahrscheinlichkeit vollständig zu faktorisieren, wenn man eine fortgeschrittenere Reduktion verwendet. ^{[ 19 ]}${\displaystyle N}$

Das Ziel der Quanten-Subroutine des Shors-Algorithmus ist es, für teilerfremde ganze Zahlen und die Ordnung von modulo zu finden , wobei die kleinste positive ganze Zahl ist, für die gilt . Dazu verwendet der Shors-Algorithmus einen Quantenschaltkreis mit zwei Registern. Das zweite Register verwendet Qubits, wobei die kleinste ganze Zahl ist, für die gilt , d. h . . Die Größe des ersten Registers bestimmt die Genauigkeit der Approximation des Schaltkreises. Es lässt sich zeigen, dass die Verwendung von Qubits eine ausreichende Genauigkeit für die Bestimmung von liefert . Der exakte Quantenschaltkreis hängt von den Parametern und ab , welche das Problem definieren. Die folgende Beschreibung des Algorithmus verwendet die Bra-Ket-Notation für Quantenzustände und für das Tensorprodukt . ${\displaystyle N}$${\displaystyle 1<a<N}$${\displaystyle r}$${\displaystyle a}$${\displaystyle N}$${\displaystyle r}$${\displaystyle a^{r}\equiv 1{\pmod {N}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle N\leq 2^{n}}$${\displaystyle n=\left\lceil {\log _{2}N}\right\rceil }$${\displaystyle 2n}$${\displaystyle r}$${\displaystyle a}$${\displaystyle N}$${\displaystyle \otimes }$

Der Algorithmus besteht aus zwei Hauptschritten:

1. Die Quantenphasenschätzung erfolgt mit einer unitären Matrix, die die Multiplikation mit (modulo ) darstellt, und dem Eingangszustand (wobei das zweite Register aus Qubits besteht). Die Eigenwerte dieser Matrix kodieren Informationen über die Periode und lassen sich als Summe ihrer Eigenvektoren darstellen. Dank dieser Eigenschaften liefert die Quantenphasenschätzung als Ausgabe eine zufällige ganze Zahl der Form für zufällige Werte von .${\displaystyle U}$${\displaystyle a}$${\displaystyle N}$${\displaystyle |0\rangle ^{\otimes 2n}\otimes |1\rangle }$${\displaystyle |1\rangle }$${\displaystyle n}$${\displaystyle U}$${\displaystyle |1\rangle }$${\displaystyle {\frac {j}{r}}2^{2n}}$${\displaystyle j=0,1,...,r-1}$
2. Verwenden Sie den Kettenbruchalgorithmus, um die Periode aus den im vorherigen Schritt gewonnenen Messergebnissen zu extrahieren. Dies ist ein Verfahren zur Nachbearbeitung (mit einem klassischen Computer) der Messdaten, die durch die Messung der Ausgabequantenzustände gewonnen wurden, und zur Bestimmung der Periode.${\displaystyle r}$

Der Zusammenhang mit der Quantenphasenschätzung wurde in der ursprünglichen Formulierung von Shors Algorithmus ^{[ 2 ]} nicht diskutiert, sondern erst später von Alexei Kitaev vorgeschlagen . ^{[ 20 ]}

Im Allgemeinen bildet der Quantenphasenschätzungsalgorithmus für jede unitäre Transformation und jeden Eigenzustand mit Eingabezustände auf Ausgabezustände nahe ab , wobei eine Superposition von ganzen Zahlen nahe ist . Anders ausgedrückt: Er bildet jeden Eigenzustand von auf einen Zustand ab, der Informationen nahe dem zugehörigen Eigenwert enthält. Für die Quantenordnungsbestimmung verwenden wir diese Strategie mit der durch die Wirkung definierten unitären Transformation. Die Wirkung von auf Zustände mit ist für die Funktion des Algorithmus nicht entscheidend, muss aber berücksichtigt werden, um sicherzustellen, dass die Gesamttransformation ein wohldefiniertes Quantengatter ist. Die Implementierung des Schaltkreises für die Quantenphasenschätzung mit erfordert die effiziente Implementierung der Gatter . Dies kann durch modulare Exponentiation erreicht werden , die den langsamsten Teil des Algorithmus darstellt. ${\displaystyle U}$${\displaystyle |\psi \rangle }$${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$${\displaystyle |0\rangle |\psi \rangle }$${\displaystyle |\phi \rangle |\psi \rangle }$${\displaystyle \phi }$${\displaystyle 2^{2n}\theta }$${\displaystyle |\psi _{j}\rangle }$${\displaystyle U}$$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$${\displaystyle U}$${\displaystyle |k\rangle }$${\displaystyle N\leq k<2^{n}}$${\displaystyle U}$${\displaystyle U^{2^{j}}}$

Das so definierte Gatter erfüllt , woraus unmittelbar folgt, dass seine Eigenwerte die -ten Einheitswurzeln sind . Weiterhin besitzt jeder Eigenwert einen Eigenvektor der Form , und diese Eigenvektoren sind so beschaffen, dass , wobei die letzte Identität aus der Formel für geometrische Reihen folgt , woraus folgt . ${\displaystyle U^{r}=I}$${\displaystyle r}$${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$${\displaystyle \omega _{r}^{j}}$${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$

Die Anwendung der Quantenphasenschätzung auf einen Eingangszustand liefert dann mit hoher Wahrscheinlichkeit die ganze Zahl . Genauer gesagt, sendet die Quantenphasenschätzungsschaltung einen Wert an , sodass die resultierende Wahrscheinlichkeitsverteilung ein Maximum um aufweist , wobei . Diese Wahrscheinlichkeit kann mithilfe zusätzlicher Qubits beliebig nahe an 1 gebracht werden. ${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$${\displaystyle k=2^{2n}j/r}$${\displaystyle p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053}$

Wendet man die obige Argumentation auf die Eingabe an , so ergibt sich aus der Quantenphasenschätzung die folgende Entwicklung: Durch Messung des ersten Registers erhalten wir nun eine ausgeglichene Wahrscheinlichkeit, jedes zu finden , wobei jedes eine ganzzahlige Näherung für liefert , die durch geteilt werden kann, um eine Dezimalapproximation für zu erhalten . ${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle }$$${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$${\displaystyle 1/r}$${\displaystyle |\phi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle 2^{2n}}$${\displaystyle j/r}$

Anschließend wenden wir den Kettenbruchalgorithmus an, um ganze Zahlen und zu finden , wobei die beste Bruchnäherung für die vom Schaltkreis gemessene Näherung angibt, für und teilerfremd und . Die Anzahl der Qubits im ersten Register, , die die Genauigkeit der Näherung bestimmt, garantiert, dass die beste Näherung aus der Superposition von gemessen wurde ^{[ 2 ]} (was durch zusätzliche Bits und Abschneiden der Ausgabe beliebig wahrscheinlich gemacht werden kann). Obwohl und teilerfremd sind, kann es jedoch sein, dass und nicht teilerfremd sind. Daher können und Faktoren verloren haben, die in und enthalten waren . Dies lässt sich beheben, indem die Subroutine zur Bestimmung der Quantenordnung beliebig oft wiederholt wird, um eine Liste von Bruchnäherungen zu erzeugen, wobei die Anzahl der Ausführungen der Subroutine ist. Jede Näherung enthält unterschiedliche Faktoren, da der Schaltkreis (wahrscheinlich) mehrere verschiedene mögliche Werte von gemessen hat . Um den tatsächlichen Wert wiederherzustellen , können wir das kleinste gemeinsame Vielfache jedes Wertes bilden : Das kleinste gemeinsame Vielfache entspricht mit hoher Wahrscheinlichkeit der Ordnung der ursprünglichen ganzen Zahl . In der Praxis genügt im Allgemeinen ein einziger Durchlauf der Quantenordnungsbestimmungsroutine, sofern eine fortgeschrittenere Nachbearbeitung verwendet wird. ^{[ 21 ]}${\displaystyle b}$${\displaystyle c}$${\displaystyle b/c}$${\displaystyle b,c<N}$${\displaystyle b}$${\displaystyle c}$${\displaystyle 2n}$$${\displaystyle {\frac {b}{c}}={\frac {j}{r}},}$$${\displaystyle |\phi _{j}\rangle }$${\displaystyle b}$${\displaystyle c}$${\displaystyle j}$${\displaystyle r}$${\displaystyle b}$${\displaystyle c}$${\displaystyle j}$${\displaystyle r}$$${\displaystyle {\frac {b_{1}}{c_{1}}},{\frac {b_{2}}{c_{2}}},\ldots ,{\frac {b_{s}}{c_{s}}},}$$${\displaystyle s}$${\displaystyle c_{k}}$${\displaystyle j}$${\displaystyle r}$${\displaystyle c_{k}}$$${\displaystyle \operatorname {lcm} (c_{1},c_{2},\ldots ,c_{s}).}$$${\displaystyle r}$${\displaystyle a}$

Für die Phasenschätzung muss die Größe des ersten Registers so gewählt werden, dass die Genauigkeit des Algorithmus bestimmt wird. Für die Quanten-Subroutine des Shors-Algorithmus reichen Qubits aus, um zu gewährleisten, dass die optimale Bitfolge, die aus der Phasenschätzung ermittelt wird (d. h. diejenige, bei der die genaueste Annäherung an die Phase aus der Phasenschätzung ist), die Wiederherstellung des tatsächlichen Wertes von ermöglicht. ${\displaystyle 2n}$${\displaystyle |k\rangle }$${\textstyle k/2^{2n}}$${\displaystyle r}$

Jedes Vormessungselement in Shors Algorithmus stellt eine Superposition von ganzen Zahlen dar, die approximieren . Sei die optimale ganze Zahl in . Der folgende Satz garantiert, dass der Kettenbruchalgorithmus aus rekonstruiert : ${\displaystyle |\phi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle |k\rangle }$${\displaystyle |\phi _{j}\rangle }$${\displaystyle j/r}$${\displaystyle k/2^{2{n}}}$

^{[ 3 ]} Daes sich um die optimale Bitfolge aus der Phasenschätzung handelt,Bitsgenau. Darausfolgt, dass der Kettenbruchalgorithmusund(oder ohne ihren größten gemeinsamen Teiler) rekonstruiert. ${\displaystyle k}$${\displaystyle k/2^{2{n}}}$${\displaystyle j/r}$${\displaystyle 2n}$$${\displaystyle \left\vert {\frac {j}{r}}-{\frac {k}{2^{2n}}}\right\vert \leq {\frac {1}{2^{2{n}+1}}}\leq {\frac {1}{2N^{2}}}\leq {\frac {1}{2r^{2}}}}$$${\displaystyle j}$${\displaystyle r}$

Der Laufzeitengpass von Shors Algorithmus ist die Quantenmodulo -Exponentiation , die weitaus langsamer ist als die Quanten-Fourier-Transformation und die klassische Vor- und Nachbearbeitung. Es gibt verschiedene Ansätze zum Aufbau und zur Optimierung von Schaltungen für die Modulo-Exponentiation. Der einfachste und (derzeit) praktischste Ansatz besteht darin, konventionelle arithmetische Schaltungen mit reversiblen Gattern nachzubilden , beginnend mit Ripple-Carry-Addierern . Die Kenntnis der Basis und des Modulus der Exponentiation erleichtert weitere Optimierungen. ^{[ 22 ] [ 23 ]} Reversible Schaltungen verwenden typischerweise etwa 10⁶ Gatter pro Qubit. Alternative Techniken verbessern die Gatteranzahl asymptotisch durch die Verwendung von Quanten-Fourier-Transformationen , sind aber aufgrund hoher Konstanten bei weniger als 600 Qubits nicht konkurrenzfähig. ${\displaystyle n^{3}}$${\displaystyle n}$

Shors Algorithmen für das diskrete Logarithmusproblem und das Ordnungsproblem sind Beispiele für einen Algorithmus zur Lösung des Periodenproblems. Alle drei sind Beispiele für das Problem der verborgenen Untergruppe .

Gegeben sei eine Gruppe der Ordnung und des Erzeugers . Angenommen, wir wissen , dass für ein gilt , und wir möchten den diskreten Logarithmus berechnen : . Betrachten wir die abelsche Gruppe , wobei jeder Faktor der modularen Addition von Werten entspricht. Betrachten wir nun die Funktion ${\displaystyle G}$${\displaystyle p}$${\displaystyle g\in G}$${\displaystyle x=g^{r}\in G}$${\displaystyle r\in \mathbb {Z} _{p}}$${\displaystyle r}$${\displaystyle r={\log _{g}}(x)}$${\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}}$

${\displaystyle f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.}$

Dies führt zu einem abelschen Problem der verborgenen Untergruppe , wobei einem Gruppenhomomorphismus entspricht . Der Kern entspricht den Vielfachen von . Wenn wir also den Kern finden können, können wir auch finden . Es existiert ein Quantenalgorithmus zur Lösung dieses Problems. Dieser Algorithmus stammt, wie der Faktorisierungsalgorithmus, von Peter Shor und beide werden implementiert, indem eine Superposition mithilfe von Hadamard-Gattern erzeugt, gefolgt von einer Quantentransformation und schließlich einer Quanten-Fourier-Transformation. ^{[ 3 ]} Daher wird der Quantenalgorithmus zur Berechnung des diskreten Logarithmus gelegentlich auch als „Shor-Algorithmus“ bezeichnet. ${\displaystyle f}$${\displaystyle (r,1)}$${\displaystyle r}$${\displaystyle f}$

Das Problem der Ordnungsfindung kann auch als Problem einer verborgenen Untergruppe betrachtet werden. ^{[ 3 ]} Um dies zu sehen, betrachten wir die Gruppe der ganzen Zahlen bezüglich der Addition und für ein gegebenes , sodass: , die Funktion ${\displaystyle a\in \mathbb {Z} }$${\displaystyle a^{r}=1}$

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).}$

Für jede endliche abelsche Gruppe existiert ein Quantenalgorithmus zur Lösung der verborgenen Untergruppe in Polynomialzeit. ^{[ 3 ]}${\displaystyle G}$${\displaystyle G}$

• GEECM , ein Faktorisierungsalgorithmus, der angeblich „oft viel schneller als der von Shor“ ist ^{[ 24 ].}
• Grovers Algorithmus

• Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantencomputer und Quanteninformation: Jubiläumsausgabe zum 10-jährigen Bestehen . Cambridge University Press. ISBN 978-1-107-00217-3Die
• Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2006). Einführung in das Quantencomputing . doi : 10.1093/oso/9780198570004.001.0001 . ISBN 978-0-19-857000-4Die
• „Erklärung für Laien“ von Scott Aaronson , „ genehmigt “ von Peter Shor. (Shor schrieb: „Großartiger Artikel, Scott! Das ist die beste Erklärung von Quantencomputing für Laien, die ich je gesehen habe.“). In einem der Kommentare wurde eine alternative Metapher für die QFT vorgestellt . Scott Aaronson empfiehlt die folgenden 12 Referenzen als weiterführende Lektüre (aus den „10^{¹⁰ 5000} Tutorials zu Quantenalgorithmen, die bereits im Internet verfügbar sind“):
• Shor, Peter W. (1997), „Polynomialzeit-Algorithmen für Primfaktorzerlegung und diskrete Logarithmen auf einem Quantencomputer“, SIAM J. Comput. , 26 (5): 1484–1509 , arXiv : quant-ph/9508027v2 , Bibcode : 1999SIAMR..41..303S , doi : 10.1137/S0036144598347011. Überarbeitete Fassung des Originalbeitrags von Peter Shor („28 Seiten, LaTeX. Dies ist eine erweiterte Fassung eines Beitrags, der in den Proceedings des 35. jährlichen Symposiums über Grundlagen der Informatik, Santa Fe, New Mexico, 20.–22. November 1994, erschienen ist. Kleinere Überarbeitungen wurden im Januar 1996 vorgenommen.“)
• Quantencomputing und Shors Algorithmus , Matthew Haywards Seite über Quantenalgorithmen , 17.02.2005, imsa.edu, LaTeX2HTML-Version des ursprünglichen LaTeX-Dokuments , auch als PDF- oder PostScript- Dokument verfügbar .
• Quantenberechnung und Shors Faktorisierungsalgorithmus , Ronald de Wolf, CWI und Universität Amsterdam, 12. Januar 1999, 9-seitiges Postscript-Dokument.
• Shors Faktorisierungsalgorithmus , Notizen aus der Vorlesung 9 von Berkeley CS 294–2, datiert 4. Oktober 2004, 7-seitiges Postscript-Dokument.
• Kapitel 6 Quantenberechnungen, archiviert am 30.04.2020 in der Wayback Machine , 91-seitiges PostScript-Dokument, Caltech, Preskill, PH229.
• Quantencomputing: Ein Tutorial von Samuel L. Braunstein .
• Die Quantenzustände des Shors Algorithmus , von Neal Young, zuletzt geändert: Di., 21. Mai 1996, 11:47:38 Uhr.
• III. RSA-Verschlüsselung mit einem Quantencomputer knacken: Shors Faktorisierungsalgorithmus , Vorlesungsskript zur Quantenberechnung, Cornell University, Physik 481–681, CS 483; Frühjahr 2006 von N. David Mermin. Letzte Überarbeitung: 28.03.2006, 30-seitiges PDF-Dokument.
• Lavor, C.; Manssur, LRU; Portugal, R. (2003). „Shor's Algorithm for Factoring Large Integers“. arXiv : quant-ph/0303175 .
• Lomonaco, Jr (2000). „Shor's Quantum Factoring Algorithm“. arXiv : quant-ph/0010034 .Diese Arbeit ist die schriftliche Fassung eines einstündigen Vortrags über Peter Shors Quantenfaktorisierungsalgorithmus. 22 Seiten.
• Kapitel 20 Quantenberechnung , aus „Computational Complexity: A Modern Approach“ , Buchentwurf, datiert Januar 2007, Sanjeev Arora und Boaz Barak, Princeton University. Veröffentlicht als Kapitel 10 Quantenberechnung in „Computational Complexity: A Modern Approach“, Cambridge University Press, 2009, ISBN 978-0-521-42426-4
• Ein Schritt in Richtung Quantencomputing: Die Verschränkung von 10 Milliarden Teilchen . Archiviert am 20.01.2011 in der Wayback Machine , aus dem „Discover Magazine“, datiert vom 19. Januar 2011.
• Josef Gruska – Herausforderungen des Quantencomputings auch in Mathematics Unlimited: 2001 und darüber hinaus , herausgegeben von Björn Engquist und Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5

• Version 1.0.0 von libquantum : enthält eine C-Sprachimplementierung des Shors-Algorithmus mit der zugehörigen Bibliothek für simulierte Quantencomputer. Um die Laufzeitkomplexität zu verbessern, sollte jedoch die Variable width in shor.c auf 1 gesetzt werden.
• PBS Infinite Series hat zwei Videos erstellt, die die Mathematik hinter Shors Algorithmus erklären: „ How to Break Cryptography “ und „ Hacking at Quantum Speed ​​with Shor's Algorithm “.
• Vollständige Implementierung des Shors-Algorithmus mit Classiq