Der Algorithmus von Shor, genannt nach dem Mathematiker Peter Shor, ist ein Quant-Algorithmus (ein Algorithmus, der auf einem Quant-Computer läuft) für die ganze Zahl factorization formuliert 1994. Informell behebt es das folgende Problem: In Anbetracht einer ganzen Zahl N, finden Sie seine Hauptfaktoren.

Auf einem Quant-Computer, zum Faktor eine ganze Zahl N, die Algorithmus-Läufe von Shor in der polynomischen Zeit (ist die genommene Zeit Polynom im Klotz N, der die Größe des Eingangs ist). Spezifisch nimmt es Zeit in Anspruch, demonstrierend, dass die ganze Zahl factorization Problem auf einem Quant-Computer effizient gelöst werden kann und so in der Kompliziertheitsklasse BQP ist. Das ist exponential schneller als der effizienteste bekannte klassische Factoring-Algorithmus, das allgemeine Sieb des numerischen Feldes, das in der Subexponentialzeit — darüber arbeitet. Die Leistungsfähigkeit ist wegen der Leistungsfähigkeit des Quants, das Fourier, und modularer exponentiation durch squarings umgestaltet.

In Anbetracht eines Quant-Computers mit einer ausreichenden Anzahl von qubits kann der Algorithmus von Shor verwendet werden, um Geheimschrift-Schemas des öffentlichen Schlüssels wie das weit verwendete RSA Schema zu brechen. RSA basiert in der Annahme, dass große Factoring-Anzahl rechenbetont unausführbar ist. So weit bekannt ist, ist diese Annahme für den klassischen (Nichtquant) Computer gültig; kein klassischer Algorithmus ist bekannt, der Faktor in der polynomischen Zeit kann. Jedoch zeigt der Algorithmus von Shor, dass Factoring auf einem Quant-Computer effizient ist, so kann ein genug großer Quant-Computer RSA brechen. Es war auch ein starker motivator für das Design und den Aufbau von Quant-Computern und für die Studie von neuen Quant-Computeralgorithmen. Es hat auch Forschung über neue cryptosystems erleichtert, die von Quant-Computern, insgesamt genannter Postquant-Geheimschrift sicher sind.

2001 wurde der Algorithmus von Shor von einer Gruppe an IBM, wer factored 15 in 3 × 5, mit einer NMR Durchführung eines Quant-Computers mit 7 qubits demonstriert.

Jedoch sind einige Zweifel betreffs erhoben worden, ob das Experiment von IBM eine wahre Demonstration der Quant-Berechnung war, seitdem keine Verwicklung beobachtet wurde.

Seit der Durchführung von IBM haben mehrere andere Gruppen den Algorithmus von Shor mit photonic qubits durchgeführt, betonend, dass Verwicklung beobachtet wurde.

Verfahren

Das Problem, das wir versuchen zu beheben, ist: In Anbetracht einer sonderbaren zerlegbaren Zahl, finden Sie eine ganze Zahl, ausschließlich zwischen 1 und, der sich teilt. Wir interessieren uns für sonderbare Werte dessen, weil irgendwelcher sogar Wert dessen trivial die Nummer 2 als ein Hauptfaktor hat. Wir können einen primality Prüfung des Algorithmus verwenden, um sicherzustellen, dass das tatsächlich zerlegbar ist.

Außerdem, für den Algorithmus, um zu arbeiten, brauchen wir nicht die Macht einer Blüte zu sein. Das kann durch die Einnahme quadratisch, kubisch..., - Wurzeln dessen geprüft werden, weil und überprüfend, dass keiner von diesen eine ganze Zahl ist. (Das schließt wirklich das für eine ganze Zahl aus und.)

Seitdem ist nicht eine Macht einer Blüte, es ist das Produkt von zwei coprime Zahlen, die größer sind als 1. Demzufolge des chinesischen Rest-Lehrsatzes hat man mindestens vier verschiedene Wurzeln modulo, zwei von ihnen, 1 seiend, und. Das Ziel des Algorithmus ist, eine Quadratwurzel von einer, anders zu finden, als 1 und; solch ein wird zu einem factorization, als in anderen Factoring-Algorithmen wie das quadratische Sieb führen.

Der Reihe nach wird Entdeckung solch ein auf die Entdeckung eines Elements sogar der Periode mit einem bestimmten zusätzlichen Eigentum reduziert (wie erklärt, unten, es ist erforderlich, dass die Bedingung des Schritts 6 des klassischen Teils nicht hält). Der Quant-Algorithmus wird verwendet, für die Periode zufällig gewählter Elemente zu finden, weil Ordnungsentdeckung ein hartes Problem auf einem klassischen Computer ist.

Der Algorithmus von Shor besteht aus zwei Teilen:

1. Die Verminderung, die auf einem klassischen Computer vom Factoring-Problem zum Problem der Ordnungsentdeckung getan werden kann.
2. Ein Quant-Algorithmus, um das Ordnung findende Problem zu beheben.

Klassischer Teil

:

d. h. die Ordnung darin, der die kleinste positive ganze Zahl r für der ist

oder

</li>

</ol>

Quant-Teil: Periode findendes Unterprogramm

Die für diesen Algorithmus verwendeten Quant-Stromkreise sind entworfen für jede Wahl von N und dem zufälligen ein verwendeter in f (x) = ein mod N kundenspezifisch. Gegebener N, finden Sie Q = 2 solche dass

Gehen Sie wie folgt weiter:

:

wohin x von 0 bis Q  1 läuft. Dieser anfängliche Staat ist eine Überlagerung von Q-Staaten. </li>

:

Das ist noch eine Überlagerung von Q-Staaten.

</li>

verwendet eine Q Wurzel der Einheit, zum Beispiel, den Umfang jedes gegebenen Staates ebenso unter dem ganzen Q der Staaten zu verteilen, und so auf eine verschiedene Weise für jeden verschiedenen x zu tun:

:

Q^ {-1/2} \sum_y \omega^ {x y} \lefty\right\rangle. </math>

Das führt zum Endstaat

:

Das ist eine Überlagerung von noch vielen als Q-Staaten, aber viele weniger als Q-Staaten. Obwohl es Q-Begriffe in der Summe gibt, kann der Staat ausgeklammert werden, wann auch immer x und x denselben Wert erzeugen. Lassen Sie

: seien Sie eine Q Wurzel der Einheit,

:r, die Periode von f, sein

:x seien Sie von einer Reihe von x am kleinsten, die dasselbe gegeben f (x) nachgeben (wir haben x so dass

Dann ist ein Einheitsvektor im komplizierten Flugzeug (ist eine Wurzel der Einheit und r, und y sind ganze Zahlen), und der Koeffizient im Endstaat ist

:

Jeder Begriff in dieser Summe vertritt einen verschiedenen Pfad zu demselben Ergebnis, und Quant-Einmischung kommt — konstruktiv vor, wenn die Einheitsvektoren in fast derselben Richtung im komplizierten Flugzeug hinweisen, das dass Punkt entlang der positiven echten Achse verlangt.

</li>

Wir erhalten ein Ergebnis y im Eingangsregister und im Produktionsregister.

Da f, die Wahrscheinlichkeit periodisch ist, ein Paar y zu messen, und durch gegeben wird

:

Q^ {-2} \left \sum_ {b} \omega^ {(x_0 + r b) y} \right^2

Q^ {-2} \left | \sum_ {b} \omega^ {b r y} \right |^2.

</Mathematik>

Analyse zeigt jetzt, dass diese Wahrscheinlichkeit höher ist, ist der nähere Einheitsvektor zur positiven echten Achse, oder der nähere yr/Q ist zu einer ganzen Zahl. Wenn r keine Macht 2 ist, wird es kein Faktor von Q. </li> sein

:A: r 

</ol>

Erklärung des Algorithmus

Der Algorithmus wird aus zwei Teilen zusammengesetzt. Der erste Teil des Algorithmus verwandelt das Factoring-Problem ins Problem, die Periode einer Funktion zu finden, und kann klassisch durchgeführt werden. Der zweite Teil findet die Periode mit dem Quant, das Fourier umgestaltet, und für die Quant-Beschleunigung verantwortlich ist.

Das Erreichen von Faktoren von der Periode

Die ganzen Zahlen weniger als N und coprime mit N bilden eine begrenzte Gruppe von Abelian unter der Multiplikation modulo N. Die Größe wird durch die Totient-Funktion von Euler gegeben.

Am Ende des Schritts 3 haben wir eine ganze Zahl in dieser Gruppe. Da die Gruppe begrenzt ist, ein Müssen haben einen begrenzten Auftrag r, die kleinste positive solche ganze Zahl dass

:

Deshalb teilt N (auch schriftlich |) einen  1. Nehmen Sie an, dass wir im Stande sind, r zu erhalten, und es gleich ist. (Wenn r seltsam ist, sieh Schritt 5.) Jetzt ist eine Quadratwurzel von 1 modulo, der von 1 verschieden ist. Das ist, weil die Ordnung von modulo, so ist. Wenn durch den Schritt 6 wir den Algorithmus mit einer verschiedenen Zufallszahl wiederanfangen müssen.

Schließlich müssen wir, von der Ordnung in, solch dass schlagen. Das ist, weil solch ein eine Quadratwurzel von 1 modulo, außer 1 ist und, dessen Existenz durch den chinesischen Rest-Lehrsatz versichert wird, da nicht eine Hauptmacht ist.

Wir behaupten, dass das ein richtiger Faktor ist, d. h. Tatsächlich, wenn sich dann, so dass, gegen den Aufbau dessen teilt. Wenn andererseits, dann durch die Identität von Bézout gibt es solche ganze Zahlen dass

:.Wenn wir

beide Seiten damit multiplizieren, erhalten uns

:.

Seitdem teilt sich, wir herrschen vor, der sich so dass teilt, wieder dem Aufbau dessen widersprechend.

So ist der erforderliche richtige Faktor dessen.

Entdeckung der Periode

Der Periode findende Algorithmus von Shor verlässt sich schwer auf die Fähigkeit eines Quant-Computers, in vielen Staaten gleichzeitig zu sein.

Physiker nennen dieses Verhalten eine "Überlagerung" von Staaten. Um die Periode einer Funktion f zu schätzen, bewerten wir die Funktion an allen Punkten gleichzeitig.

Quant-Physik erlaubt uns nicht, auf diese ganze Information direkt zuzugreifen, dennoch. Ein Maß wird nur einen aller möglichen Werte nachgeben, alles andere zerstörend. Wenn nicht für keinen Klonen-Lehrsatz konnten wir zuerst f (x) messen, ohne x zu messen, und dann einige Kopien des resultierenden Staates machen (der eine Überlagerung von Staaten alle ist, denselben f (x) habend). Das Messen x auf diesen Staaten würde verschiedene X-Werte zur Verfügung stellen, die denselben f (x) geben, zur Periode führend. Weil wir genaue Kopien eines Quant-Staates nicht machen können, arbeitet diese Methode nicht. Deshalb müssen wir die Überlagerung in einen anderen Staat sorgfältig umgestalten, der die richtige Antwort mit der hohen Wahrscheinlichkeit zurückgeben wird. Das wird durch das Quant erreicht, das Fourier umgestaltet.

Shor musste so drei "Durchführungs"-Probleme beheben. Sie alle mussten "schnell" durchgeführt werden, was bedeutet, dass sie mit mehreren Quant-Toren durchgeführt werden können, der Polynom darin ist.

Das kann durch die Verwendung von Toren von Hadamard auf den ganzen qubits im Eingangsregister getan werden. Eine andere Annäherung würde das Quant verwenden sollen, das Fourier (sieh unten) umgestaltet.

Um das zu erreichen, hat Shor wiederholtes Quadrieren für seine exponentiation Modultransformation verwendet. Es ist wichtig zu bemerken, dass dieser Schritt schwieriger ist durchzuführen als das Quant, das Fourier umgestaltet, in dem es verlangt, dass untergeordneter qubits und wesentlich mehr Tore vollbringt.

Indem

er kontrollierte Folge-Tore und Tore von Hadamard verwendet hat, hat Shor einen Stromkreis für das Quant entworfen, das Fourier umgestaltet (mit Q = 2), der gerade Tore verwendet.

</ol>

Nach allen diesen Transformationen wird ein Maß eine Annäherung an die Periode r nachgeben.

Weil Einfachheit annimmt, dass es einen solchen y gibt, dass yr/Q eine ganze Zahl ist.

Dann ist die Wahrscheinlichkeit, um y zu messen, 1.

Zu sehen, dass wir das dann bemerken

:

für alle ganzen Zahlen b. Deshalb wird die Summe, deren Quadrat uns die Wahrscheinlichkeit gibt, um y zu messen, Q/r sein, da b grob Q/r Werte nimmt und so die Wahrscheinlichkeit ist. Es gibt r y solch, dass yr/Q eine ganze Zahl und auch r Möglichkeiten für, so die Wahrscheinlichkeitssumme zu 1 ist.

Zeichen: Eine andere Weise, den Algorithmus von Shor zu erklären, ist durch die Anmerkung, dass es gerade der verkleidete Quant-Phase-Bewertungsalgorithmus ist.

Der Engpass

Der Laufzeitengpass des Algorithmus von Shor ist Quant modularer exponentiation, der bei weitem langsamer ist als das Quant, das Fourier umgestaltet und klassisch prä-/postbearbeitend. Es gibt mehrere Annäherungen an das Konstruieren und die Optimierung von Stromkreisen für modularen exponentiation. Die einfachste und (zurzeit) praktischste Annäherung soll mimische herkömmliche arithmetische Stromkreise mit umkehrbaren Toren verwenden, mit der Kräuselung anfangend - tragen Vipern. Das Wissen der Basis und des Moduls von exponentiation erleichtert weitere Optimierungen. Umkehrbare Stromkreise verwenden normalerweise auf der Ordnung von Toren für qubits. Alternative Techniken verbessern asymptotisch Tor-Zählungen durch das Verwenden des Quants, das Fourier umgestaltet, aber mit weniger als 600 qubits wegen hoher Konstanten nicht konkurrenzfähig ist.

Getrennte Logarithmen

Nehmen Sie an, dass wir wissen, dass für einen r, und wir r schätzen möchten, der der getrennte Logarithmus ist:. Denken Sie die Gruppe von Abelian, wo jeder Faktor Modulmultiplikation von Nichtnullwerten entspricht, ist das Annehmen p erst. Denken Sie jetzt die Funktion

:

Das gibt uns Abelian verborgenes Untergruppe-Problem, weil f einem Gruppenhomomorphismus entspricht. Der Kern entspricht Modulvielfachen (r, 1). Also, wenn wir den Kern finden können, können wir r finden

In der populären Kultur

Auf der TV-Show Stargate Universe hat der Leitungswissenschaftler, Dr Nicholas Rush, gehofft, den Algorithmus von Shor zu verwenden, um den Master-Code des Schicksals zu knacken. Er hat eine Quant-Geheimschrift-Klasse an der Universität Kaliforniens, Berkeley unterrichtet, in dem der Algorithmus von Shor studiert wurde.

Der Algorithmus von Shor war auch eine richtige Antwort auf eine Frage in einer Physik-Schüssel-Konkurrenz auf der TV-Show Die Urknall-Theorie.

Weiterführende Literatur

.

• Phillip Kaye, Raymond Laflamme, Michele Mosca, Eine Einführung in die Quant-Computerwissenschaft, Presse der Universität Oxford, 2007, internationale Standardbuchnummer 0 19 857049 X
• "Erklärung für den Mann auf der Straße" durch Scott Aaronson, der von Peter Shor "genehmigt" ist". (Shor hat "Großen Artikel, Scott geschrieben! Es ist der beste Job, Quant zu erklären, das dem Mann auf der Straße rechnet, die ich gesehen habe."). Scott Aaronson schlägt die folgenden 12 Verweisungen als weiterführende Literatur vor (aus "den 10 Quant-Algorithmus-Tutorenkursen, die bereits im Web sind."):
• . Revidierte Version des ursprünglichen Vortrages von Peter Shor ("28 Seiten, LATEX. Das ist eine ausgebreitete Version einer Zeitung, die in den Verhandlungen des 35. Jährlichen Symposiums auf Fundamenten der Informatik, Santa Fes, New Mexico am 20. - 22. November 1994 erschienen ist. Geringe Revisionen haben Januar 1996" gemacht).
• Quant-Computerwissenschaft und der Algorithmus von Shor, Matthew Hayward, am 2005-02-17, imsa.edu, LaTeX2HTML Version des ursprünglichen 2750 Linien-LATEX-Dokumentes, auch verfügbar als ein 61-Seite-PDF oder Nachschrift-Dokument.
• Quant-Berechnung und der Factoring-Algorithmus von Shor, Ronald de Wolf, CWI und Universität Amsterdams, am 12. Januar 1999, 9-Seite-Nachschrift-Dokumentes.
• Der Factoring-Algorithmus von Shor, Zeichen vom Vortrag 9 von Berkeley CS 294-2, hat am 4. Okt 2004, 7-Seite-Nachschrift-Dokument datiert.
• Quant-Berechnung des Kapitels 6, 91-Seite-Nachschrift-Dokument, Caltech, Vorsachkenntnis, PH229.
• Quant-Berechnung: ein Tutorenkurs durch Samuel L. Braunstein.
• Die Quant-Staaten des Algorithmus von Shor, durch Neal Young, Letzt modifiziert: Dienstag, der 21. Mai 11:47:38 Uhr 1996.
• Ein Jetzt-Zirkelbezug über die Kopie dieses Artikels; klar hat die Verbindung von Aaronson ursprünglich die Version am 20. Februar 2007 erreicht.
• III. Das Brechen RSA Verschlüsselung mit einem Quant-Computer: Der Factoring-Algorithmus von Shor, Vortrag bemerkt auf der Quant-Berechnung, Universität von Cornell, Physik 481-681, CS 483; Frühling, 2006 durch N. David Mermin. Letzt revidiert am 2006-03-28, PDF 30-Seite-Dokument.
• arXiv quant-ph/0303175 der Algorithmus von Shor für das Factoring Große Ganze Zahlen. C. Lavor, L.R.U. Manssur, R. Portugal. Vorgelegt am 29. Mrz 2003. Diese Arbeit ist ein Tutorenkurs auf dem Factoring-Algorithmus von Shor mittels eines ausgearbeiteten Beispiels. Einige grundlegende Konzepte der Quant-Mechanik und Quant-Stromkreise werden nachgeprüft. Es ist für Nichtfachmänner beabsichtigt, die Grundkenntnisse auf der Geradlinigen Studentenalgebra haben. 25 Seiten, 14 Zahlen, einleitende Rezension.
• arXiv quant-ph/0010034 der Quant-Factoring-Algorithmus von Shor, Samuel J. Lomonaco der Jüngere, Vorgelegt am 9. Oktober 2000, ist Dieses Papier eine schriftliche Version eines auf dem Quant-Factoring-Algorithmus von Peter Shor gegebenen Stunde-Vortrags. 22 Seiten.
• Quant-Berechnung des Kapitels 20, von der Rechenbetonten Kompliziertheit: Eine Moderne Annäherung, Entwurf eines Buches: Datiert Januar 2007, Anmerkungen Willkommen!, Sanjeev Arora und Boaz Barak, Universität von Princeton.
• Ein Schritt zur Quant-Computerwissenschaft: Das Verfangen von 10 Milliarden Partikeln, von "Entdecken Zeitschrift", Datiert am 19. Januar 2011.