Peter Schor Ich hatte nicht vor, das Internet zu zerstören. Doch ein Algorithmus, den er Mitte der 1990er Jahre entwickelte, drohte genau das zu bewirken. In einem wegweisendes Papier, Shor zeigte, wie ein hypothetischer Computer, der die Eigenheiten der Quantenphysik ausnutzt, große Zahlen viel schneller in ihre Primfaktoren zerlegen kann als jede gewöhnliche klassische Maschine.

Das Ergebnis hatte Auswirkungen weit über die Mathematik hinaus. Damals ein wichtiger Bestandteil der Internetsicherheit genannt Kryptographie mit öffentlichem Schlüssel beruhte auf der Annahme, dass die Faktorisierung großer Zahlen so rechnerisch schwierig ist, dass sie praktisch unmöglich ist. Diese Annahme liegt auch heute noch einigen wichtigen Protokollen zugrunde. Shors Algorithmus zeigte, dass er in einer Welt voller Mächtiger spektakulär versagen würde Quantencomputer.

In den letzten 30 Jahren haben Informatiker Shors Algorithmus optimiert, um ihn auf den Tag vorzubereiten, an dem die Quantentechnologie ausgereift genug ist, um ihn auszuführen. Aber eine neue Variante, vom Informatiker der New York University Oded Regev, ist schneller in einem grundlegend neuen Sinne. Es ist das erste, das die Beziehung zwischen der Größe der zu faktorisierenden Zahl und der Anzahl der zu ihrer Faktorisierung erforderlichen Quantenoperationen verbessert.

„Es ist wirklich bemerkenswert, dass es offenbar jemandem gelungen ist, die Komplexität dieses Ergebnisses viele, viele Jahre später zu verbessern“, sagte er Ashley Montanaro, ein Quantencomputerforscher an der Universität Bristol. „Das ist wirklich aufregend.“

Martin Ekerå, ein Kryptograf bei der schwedischen Nationalen Kommunikationssicherheitsbehörde, stimmte zu, dass Regevs Artikel interessant sei, warnte jedoch davor, dass es einer weiteren Optimierung bedarf, um den Stand der Technik in der Praxis zu übertreffen. „Shors ursprüngliche Algorithmen sind bereits überraschend effizient, daher ist es nicht trivial, größere Verbesserungen vorzunehmen“, schrieb er in einer E-Mail.

Regev entwickelte seinen neuen Algorithmus, indem er Shors Algorithmus um Techniken aus einem Zweig der Kryptographie erweiterte, der sich mit hochdimensionaler Geometrie befasst.

„Ich hätte gedacht, dass jeder Algorithmus, der mit diesem Grundprinzip funktioniert, zum Scheitern verurteilt wäre“, sagte Shor, ein angewandter Mathematiker, der jetzt am Massachusetts Institute of Technology arbeitet. "Aber ich habe mich getäuscht."

Faktoren finden

Quantencomputer beziehen ihre Leistung aus der besonderen Art und Weise, wie sie Informationen verarbeiten. Klassische Computer verwenden Bits, von denen sich jedes immer in einem von zwei Zuständen befinden muss, die mit 0 und 1 gekennzeichnet sind. Quantenbits oder „Qubits“ können sich zusätzlich in Kombinationen ihrer Zustände 0 und 1 befinden – ein Phänomen, das als Superposition bezeichnet wird. Es ist auch möglich, mehrere Qubits in einen kollektiven Überlagerungszustand zu überführen: Eine Zwei-Qubit-Überlagerung besteht aus vier Komponenten, die gleichzeitig unterschiedliche Berechnungen durchführen können, und die Anzahl dieser Komponenten wächst exponentiell mit zunehmender Anzahl von Qubits. Dadurch können Quantencomputer effektiv exponentiell viele verschiedene Berechnungen parallel durchführen.

Jedoch müssen auch Es gibt einen Haken: Das Lesen des Ergebnisses einer in Superposition durchgeführten Berechnung zeigt nur die Antwort auf den von einer Zufallskomponente berechneten Teil. Um die Vorteile der Überlagerungsberechnung nutzen zu können, müssen Sie das Endergebnis irgendwie einem einfacheren Zustand zuordnen, in dem das Ergebnis sicher gelesen werden kann. Das ist in den meisten Fällen nicht möglich, und zunächst wusste niemand, wie man es bei irgendeinem Problem umsetzen kann. „Es gab nur sehr wenige Menschen, die überhaupt den Mut hatten, über Quantenberechnungen nachzudenken“, sagte Regev.

Dann, im Jahr 1994, las Shor ein Papier vom Informatiker Daniel Simon, der zeigte, wie man Quantenüberlagerung zur Lösung eines erfundenen Problems nutzen kann. Shor fand heraus, wie er Simons Ergebnis auf ein allgemeineres und praktischeres Problem namens Periodenfindung erweitern konnte. Eine mathematische Funktion wird als periodisch bezeichnet, wenn ihre Ausgabe wiederholt dieselben Werte durchläuft, während die Eingabe zunimmt; Die Länge eines einzelnen Zyklus wird als Periode der Funktion bezeichnet.

Um die Periode einer bestimmten Funktion mithilfe eines Quantencomputers zu ermitteln, erstellen Sie zunächst eine sehr große Überlagerung, bei der jede Komponente die Ausgabe der Funktion für eine andere Eingabe berechnet. Verwenden Sie dann die Methode von Shor, um diese große Überlagerung in einen einfacheren Zustand umzuwandeln, und lesen Sie das Ergebnis ab. An diesem Punkt kann ein klassischer Computer übernehmen und die Berechnung schnell abschließen. Insgesamt läuft Shors Periodenfindungsalgorithmus exponentiell schneller als jede klassische Alternative, da er mithilfe von Superposition gleichzeitig verschiedene Ausgaben der periodischen Funktion berechnet.

Als Shor nach Anwendungen für seinen Quantenperiodenfindungsalgorithmus suchte, entdeckte er einen zuvor bekannten, aber unklaren mathematischen Satz wieder: Für jede Zahl gibt es eine periodische Funktion, deren Perioden mit den Primfaktoren der Zahl zusammenhängen. Wenn Sie also eine Zahl faktorisieren möchten, können Sie die entsprechende Funktion berechnen und dann das Problem mithilfe der Periodenfindung lösen – „genau das, was Quantencomputer so gut können“, sagte Regev.

Auf einem klassischen Computer wäre dies eine quälend langsame Methode, eine große Zahl zu faktorisieren – sogar langsamer, als jeden möglichen Faktor auszuprobieren. Aber Shors Methode beschleunigt den Prozess exponentiell und macht die Periodenfindung zu einem idealen Weg, um einen schnellen Quantenfaktorisierungsalgorithmus zu konstruieren.

Shors Algorithmus war eines der wenigen wichtigen frühen Ergebnisse, die das Quantencomputing von einem obskuren Teilgebiet der theoretischen Informatik zu dem Moloch machten, das es heute ist. Doch die Umsetzung des Algorithmus in die Praxis ist eine gewaltige Aufgabe, denn Quantencomputer sind bekanntermaßen fehleranfällig: Zusätzlich zu den Qubits, die für ihre Berechnungen erforderlich sind, benötigen sie noch viele andere Extra Arbeit um zu verhindern, dass sie scheitern. A jüngsten Papier von Ekerå und dem Google-Forscher Craig Gidney schätzt, dass die Verwendung des Shor-Algorithmus zur Faktorisierung einer sicherheitsstandardmäßigen 2,048-Bit-Zahl (ungefähr 600 Ziffern lang) einen Quantencomputer mit 20 Millionen Qubits erfordern würde. Heutige, hochmoderne Maschinen haben höchstens ein paar Hundert.

Aus diesem Grund verlassen sich einige kritische Internetprotokolle immer noch darauf, wie schwierig es ist, große Zahlen zu faktorisieren, aber Forscher wollen nicht zu selbstgefällig werden. theoretisch und technologische Innovationen könnten die erforderliche Qubit-Anzahl weiter senken, und es gibt keinen Beweis dafür, dass Shors Algorithmus optimal ist – es könnte einen besseren Quantenfaktorisierungsalgorithmus geben, den noch niemand entdeckt hat.

Wenn ja, sagte Regev, „sollten wir es so früh wie möglich wissen, bevor es zu spät ist.“

Verloren in den Bäumen

Regev begann seine akademische Karriere Ende der 1990er Jahre, als Kryptographen nach einer neuen Form der Public-Key-Kryptographie suchten, die nicht anfällig für Shors Algorithmus war. Der vielversprechendste Ansatz heißt Gitterbasierte Kryptographieberuht auf der offensichtlichen Schwierigkeit von Rechenproblemen, die hochdimensionale Punktanordnungen oder Gitter betreffen. Ein solches Problem ähnelt der Aufgabe, den Baum zu lokalisieren, der einem zufälligen Punkt in einem Wald am nächsten liegt.

„Wenn es sich um einen hundertdimensionalen Wald handelt, ist das viel komplizierter als wenn es sich um einen zweidimensionalen Wald handelt“, sagte er Greg Küperberg, ein Mathematiker an der University of California, Davis.

Regev begann als Postdoktorand mit dem Studium der gitterbasierten Kryptographie, zunächst als Angreifer – er wollte den neuen Ansatz einem Stresstest unterziehen, indem er Schwachstellen fand, die ein Quantencomputer ausnutzen könnte. Aber er kam nicht voran und fragte sich bald, ob es dafür einen tieferen Grund gab. Im Jahr 2005 fand er einen Weg, diese gescheiterten Angriffe in eine zu verwandeln Form der gitterbasierten Kryptographie allen anderen Varianten überlegen.

„Oded ist absolut brillant im Umgang mit Gittern“, sagte Kuperberg.

Als Regev im Laufe der Jahre nachfolgenden Generationen von Schülern Shors Algorithmus beibrachte, fragte er sich, ob sich die Techniken, die er zum Angriff auf die gitterbasierte Kryptographie verwendet hatte, bei der Faktorisierung von Algorithmen tatsächlich als nützlich erweisen könnten. Das liegt daran, dass ein Schritt in der letzten, klassischen Phase von Shors Algorithmus darauf hinausläuft, den nächstgelegenen Punkt in einem eindimensionalen Gitter zu finden. Dieses eindimensionale Problem ist trivial einfach, aber die Ähnlichkeit mit dem analogen Problem in Hunderten von Dimensionen, dessen Härte der gitterbasierten Kryptographie zugrunde liegt, war unverkennbar.

„Wenn man wie ich jemand ist, der Lattices macht, denkt man: ‚Okay, da ist irgendein Lattice im Gange‘“, sagte Regev. „Aber mir war nicht klar, wie ich das nutzen sollte.“ Jahrelang spielte er mit anderen Ideen für neue Quantenfaktorisierungsalgorithmen, kam aber nie weiter. Letzten Winter wandte er sich dann wieder dem Problem zu und beschloss, den verlockenden Zusammenhang zwischen Faktorisierung und gitterbasierter Kryptographie herauszufinden. Dieses Mal hatte er Erfolg.

Zusätzliche Abmessungen

Regev wusste, dass er damit beginnen musste, die periodische Funktion im Herzen von Shors Algorithmus von einer Dimension auf viele Dimensionen zu verallgemeinern. In Shors Algorithmus beinhaltet diese Funktion das wiederholte Multiplizieren einer Zufallszahl, genannt g, mit sich selbst. Aber die Periode dieser Funktion – die Häufigkeit, mit der Sie multiplizieren müssen g bevor sich die Ausgabe der Funktion zu wiederholen beginnt – kann sehr groß sein, und das bedeutet, dass ein Quantencomputer große Zahlen in einigen Komponenten der Überlagerung multiplizieren muss, die er zur Berechnung der periodischen Funktion verwendet. Diese großen Multiplikationen sind der rechenintensivste Teil von Shors Algorithmus.

Die analoge zweidimensionale Funktion verwendet stattdessen ein Zahlenpaar, g₁ und g₂. Es geht um Multiplikation g₁ mit sich selbst viele Male und dann wiederholt mit multiplizieren g₂. Die Periode dieser Funktion ist ebenfalls zweidimensional – sie wird durch die Anzahl definiert g₁ Multiplikationen und g₂ Multiplikationen, die zusammen dazu führen, dass sich die Ausgabe der Funktion wiederholt. Es gibt viele verschiedene Kombinationen von g₁ und g₂ Multiplikationen, die den Zweck erfüllen.

Regev arbeitete die technischen Details durch, um den Algorithmus auf eine beliebige Anzahl von Dimensionen zu verallgemeinern, nicht nur auf zwei, aber seine ersten Ergebnisse waren nicht ermutigend. Um die periodische Funktion in vielen Dimensionen zu berechnen, müsste der Quantencomputer noch viele Zahlen miteinander multiplizieren. Jede Zahl müsste nicht so oft multipliziert werden wie im eindimensionalen Fall, aber es gab mehr unterschiedliche Zahlen, die multipliziert werden mussten. Das Ganze schien eine Wäsche zu sein.

„Man denkt: ‚Großartig, ich habe einfach alles in hohen Dimensionen gemacht und es ist genau die gleiche Laufzeit wie bei Shor‘“, sagte Regev. „Daran habe ich eine Zeit lang festgehalten.“ Dann erkannte er, dass er das Problem umgehen konnte, indem er die Reihenfolge der Multiplikationen änderte. Anstatt immer wieder Zahlen an ein einzelnes Produkt anzuhängen, das im Laufe der Quantenberechnung immer größer wird, begann er mit Paaren kleiner Zahlen, multiplizierte die resultierenden Produkte miteinander und ging dann nach oben. An der Gesamtzahl der Multiplikationen hat sich nicht viel geändert, aber jetzt handelt es sich bei fast allen um relativ kleine Zahlen, was die Berechnung beschleunigt.

„Das macht den Unterschied in der Welt“, sagte er Vinod Vaikuntanathan, ein Kryptograf am MIT.

Zunächst sah es so aus, als hätte Regev gerade ein Problem durch ein anderes ersetzt. Er hatte die Quantenberechnung der periodischen Funktion beschleunigt, indem er die Anzahl der Dimensionen erhöht hatte, aber die anschließende klassische Berechnung, die zum Extrahieren der Periode erforderlich war, ähnelte nun der Lokalisierung des nächstgelegenen Gitterpunkts in einem hochdimensionalen Raum – eine Aufgabe, die allgemein angenommen wird hart sein. Die Analogie zur gitterbasierten Kryptographie, die seinen neuen Ansatz motivierte, schien ihn zum Scheitern zu bringen.

An einem kalten Morgen im März vor einer Reise zu einem Seminar an der Princeton University wartete Regev auf den Kollegen, mit dem er eine Fahrgemeinschaft bildete. „Ich kam früh an und er kam zu spät, um das Auto abzuholen“, sagte er. Während er dort saß und wartete, fiel ihm plötzlich das letzte Puzzleteil ein. „Das war der Moment, in dem die Dinge zusammenpassten, aber es dauerte eine Weile.“

Es kam alles auf die richtige Anzahl an Dimensionen an. Wenn die Gitterdimension zu niedrig war, konnte sein Algorithmus die Beschleunigung durch die Multiplikation kleinerer Zahlen nicht voll ausnutzen. Wenn es zu hoch war, war die Quantenberechnung schnell, aber der klassische Teil erforderte die Lösung eines unerschwinglich harten Gitterproblems. Regev hatte von Anfang an gewusst, dass er irgendwo dazwischen arbeiten musste, um Erfolg zu haben, aber es war nicht klar, ob es eine optimale Lösung dafür gab. An diesem Morgen im März wurde ihm klar, wie er die Details des Algorithmus optimieren konnte, damit er in einigen Dutzend Dimensionen schnell ausgeführt werden konnte.

In den Sand schreiben

Die Verbesserung war tiefgreifend. Die Anzahl der elementaren logischen Schritte im Quantenteil des Regev-Algorithmus ist proportional zu n^1.5 bei der Faktorisierung an n-Bit-Zahl, statt n² wie in Shors Algorithmus. Der Algorithmus wiederholt diesen Quantenteil ein paar Dutzend Mal und kombiniert die Ergebnisse, um ein hochdimensionales Gitter abzubilden, aus dem er die Periode ableiten und die Zahl faktorisieren kann. Der Algorithmus als Ganzes läuft also möglicherweise nicht schneller, aber die Beschleunigung des Quantenteils durch die Reduzierung der Anzahl der erforderlichen Schritte könnte die Umsetzung in die Praxis erleichtern.

Natürlich ist die Zeit, die zum Ausführen eines Quantenalgorithmus benötigt wird, nur eine von mehreren Überlegungen. Ebenso wichtig ist die Anzahl der erforderlichen Qubits, die dem Speicher entspricht, der zum Speichern von Zwischenwerten während einer gewöhnlichen klassischen Berechnung erforderlich ist. Die Anzahl der Qubits, die Shors Algorithmus benötigt, um an zu faktorisieren n-Bit-Zahl ist proportional zu n, während der Regev-Algorithmus in seiner ursprünglichen Form eine Anzahl von Qubits proportional zu erfordert n^1.5 – ein großer Unterschied für 2,048-Bit-Zahlen.

Beim klassischen Rechnen ist die Geschwindigkeit normalerweise ein wichtigerer Gesichtspunkt als der Speicher, da klassische Bits äußerst robust sind: Sie können eine Datei auf Ihrem Computer speichern und müssen sich keine Sorgen machen, dass sie sich zufällig ändert, wenn Sie sie später erneut öffnen. Quantencomputing-Forscher haben nicht immer so viel Glück.

„Unsere Qubits versuchen ständig auseinanderzufallen, und wir versuchen, sie daran zu hindern, auseinanderzufallen“, sagte Gidney. „Es ist, als würde man versuchen, in den Sand zu schreiben, und der Wind bläst es weg.“ Das bedeutet, dass die zusätzlichen Qubits, die der Regev-Algorithmus benötigt, ein großer Nachteil sein könnten.

Aber Regevs Artikel ist nicht das Ende der Geschichte. Vor zwei Wochen fanden Vaikuntanathan und sein Doktorand Seyoon Ragavan einen Weg, den Speicherverbrauch des Algorithmus zu reduzieren. Ihre Variante des Regev-Algorithmus erfordert wie der ursprüngliche Algorithmus von Shor eine Anzahl von Qubits proportional zu n statt n^1.5. Ekerå schrieb in einer E-Mail, dass die Arbeit „uns einer Umsetzung viel näher bringt, die in der Praxis effizienter wäre.“

Die umfassendere Lehre aus Regevs neuem Algorithmus, die über die Auswirkungen auf die Faktorisierung hinausgeht, besteht darin, dass Quantencomputing-Forscher immer offen für Überraschungen sein sollten, selbst bei Problemen, die seit Jahrzehnten untersucht werden.

„Diese Variante meines Algorithmus blieb 30 Jahre lang unentdeckt und kam aus heiterem Himmel“, sagte Shor. „Es gibt wahrscheinlich noch viele andere Quantenalgorithmen.“

Anmerkung des Herausgebers: Oded Regev erhält Fördermittel von der Simons Foundation, die auch dieses redaktionell unabhängige Magazin finanziert. Finanzierungsentscheidungen der Simons Foundation haben keinen Einfluss auf unsere Berichterstattung. Weitere Details sind finden Sie hier.

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Informatik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Merch.