Besuchen Sie Classiqs Bibliothek für eine Implementierung des Algorithmus von Shor
‍

Wer sich für das Quantencomputing interessiert, kommt nicht umhin, vom Shor-Faktorisierungsalgorithmus zu hören. Er ist einer der wenigen Quantenalgorithmen aus dem Lehrbuch, was bedeutet, dass er eines der seltenen Beispiele für einen Quantenberechnungsvorteil bleibt. Mit anderen Worten: Der Algorithmus kann etwas auf Quantenbasis berechnen, was auf klassischem Wege schwieriger und langsamer zu berechnen ist. In der Tat kann dieser spezielle Algorithmus etwas berechnen, was nach allem, was wir wissen, auf klassischem Wege in einem sinnvollen Maßstab unmöglich ist.

Unter den oben erwähnten Lehrbuchalgorithmen sticht der Shor-Faktorisierungsalgorithmus aus der Masse hervor. Hierfür gibt es zwei hervorragende Gründe. Erstens kann er Zahlen exponentiell schneller faktorisieren als jeder bekannte klassische Algorithmus. Während alle Quantenalgorithmen aus dem Lehrbuch rechnerische Vorteile bieten, ist der Shor-Algorithmus einer der wenigen mit einer exponentiellen Beschleunigung und einer der wenigen mit einer praktischen Anwendung. Vor allem aber bedroht sein Potenzial, Zahlen in vernünftigen Zeiträumen zu faktorisieren, die weltweit beliebtesten Kryptosysteme direkt.  

Die Bedeutung dieser Tatsache kann gar nicht hoch genug eingeschätzt werden. Die RSA-Verschlüsselung, die Finanztransaktionen weltweit schützt, funktioniert durch die Multiplikation zweier großer Primzahlen. Primzahlen können nicht in andere ganze Zahlen als sich selbst und die Zahl Eins zerlegt werden. Ihre Produkte sind so groß, dass es keinen bekannten Weg gibt, sie auf klassische Weise effizient zu faktorisieren. Stellen Sie sich das Factoring als umgekehrte Multiplikation vor, bei der die verwendeten Primzahlen ermittelt werden, was die Entschlüsselung der Internetkommunikation durch Unbefugte ermöglicht.

In diesem Blog-Artikel wird der besprochene Algorithmus gelegentlich als Shors Faktorisierungsalgorithmus und nicht einfach als Shors Algorithmus bezeichnet, da es auch einen Quantenfehlerkorrekturcode mit dem Namen Shor gibt, der denselben Namensgeber hat und der als Folge der Veröffentlichung des Faktorisierungsalgorithmus entdeckt wurde. Um Unklarheiten von vornherein zu vermeiden, wird in diesem Artikel darauf hingewiesen, dass sich Shors Algorithmus und Shors Faktorisierungsalgorithmus auf denselben Algorithmus beziehen.

Was ist der Shor-Algorithmus in der Quanteninformatik?             

Shors Faktorisierungsalgorithmus brachte das Quantencomputing auf die sprichwörtliche Landkarte. Durch die Drohung mit einer animierten Version wurden nationale Regierungen, ganze Industriezweige und die breite Öffentlichkeit gezwungen, von dieser relativ neuen Technologie Kenntnis zu nehmen. Auch Jahrzehnte später ist dieser Algorithmus noch immer das Maß aller Dinge im Bereich der Quantenalgorithmen. Seit langem werden erhebliche Anstrengungen unternommen, um die globalen Finanzsysteme, die nationale Sicherheit und alle anderen Anwendungen der Kryptografie zu schützen. Die geopolitische Gefahr besteht eindeutig darin, dass irgendjemand, insbesondere ein staatlicher Akteur, genügend Quantencomputerleistung entwickelt, um den Shor-Algorithmus einzusetzen, bevor quantensichere Kryptosysteme allgemein eingesetzt werden können.

Fast ebenso wichtig ist, dass Shors Algorithmus dazu geführt hat, dass heute Milliarden von Dollar in Quantentechnologien, einschließlich Quantencomputer, investiert werden. Drei Jahrzehnte nach der Entdeckung des Algorithmus geht die Suche nach weiteren praktischen Anwendungen weiter, bei denen sich exponentielle Beschleunigungen erzielen lassen. Wenn zumindest ein Algorithmus dies erreichen kann, so die Überlegung, muss es auch andere geben. Nach all diesen Jahren sind die wahrscheinlichsten Kandidaten dem Shor-Algorithmus entlehnt.

Die vollständige Geschichte der Entdeckung des Shor-Faktorisierungsalgorithmus, erzählt von Professor Peter Shor selbst, finden Sie hier auf Qiskit's YouTube, eine kürzere, animierte Version dieser Geschichte hier.

Wie funktioniert der Algorithmus von Shor?

Die Faktorisierung von Zahlen mit dem Shor-Algorithmus beginnt mit der Auswahl einer Zufallszahl, die kleiner ist als die zu faktorisierende Zahl. Der klassisch berechnete größte gemeinsame Teiler (GCD) dieser beiden Zahlen, der Zufallszahl und der Zielzahl, wird dann verwendet, um festzustellen, ob die Zielzahl bereits zufällig faktorisiert wurde. Bei kleineren Zahlen ist das eine Möglichkeit. Für größere Zahlen könnte ein Supercomputer benötigt werden. Und für Zahlen, die als kryptografisch sicher gelten, wird ein Quantencomputer benötigt.

Die Aufgabe des Quantencomputers besteht darin, die Periode der zu faktorisierenden Zahl zu bestimmen. Die Berechnungsergebnisse bestimmen, ob eine neue Zufallszahl getestet werden muss oder ob die gesuchten Faktoren gefunden wurden. Sobald die Zielzahl faktorisiert wurde, ist die Aufgabe des Shor-Algorithmus abgeschlossen

Auf den ersten Blick mag dieser ganze Prozess recht einfach erscheinen. Und auf hohem Niveau ist er das auch. Allerdings kann jeder Schritt im Detail in einer Reihe von Vorlesungen erklärt werden. Die Implementierung des Algorithmus kann nach einem kurzen Tutorium durchgeführt werden, aber das vollständige Verständnis des Algorithmus kann viele Stunden Studium in Anspruch nehmen. 

Eine mathematische Erklärung des Shor's Factoring Algorithmus finden Sie hier. Ansonsten ist der Shor-Algorithmus kurz und bündig erklärt.

Wie wird der Algorithmus von Shor umgesetzt?                                   

Der Faktorisierungsalgorithmus von Shor ist nicht einfach zu implementieren. Zunächst einmal hat der Algorithmus drei Hauptkomponenten: eine mit klassischer Berechnung, eine mit Quantenberechnung und eine weitere mit klassischer Berechnung. Insgesamt umfasst der Algorithmus sechs wichtige Schritte, die oben zusammengefasst sind.

Zu dieser Komplexität kommt noch hinzu, dass die Quantenkomponente des Shor-Faktorisierungsalgorithmus aus vier Unterkomponenten besteht, von denen jede für sich einen ganzen Artikel zur Erklärung füllen könnte. Und während zwei dieser Quantenunterkomponenten relativ einfach zu erklären sind, handelt es sich bei den anderen beiden um unglaublich wichtige Quantenunterprogramme. Tatsächlich sind sie wohl die beiden wichtigsten Quanten-Subroutinen.

Eine der entscheidenden Quanten-Subkomponenten ist die Quantenphasenschätzung (QPE). Das Wichtigste dabei ist, dass sie die modulare Arithmetik durchführt, die erforderlich ist, um die Periode der zu faktorisierenden Zahl zu finden. Mit anderen Worten: Hier liegt die Stärke des Shor'schen Algorithmus beim Faktorisieren. 

Die andere wichtige Quantenunterkomponente ist die inverse Quanten-Fourier-Transformation (iQFT). Einfach ausgedrückt, wird bei der iQFT das Quantenergebnis der unmittelbar vorangehenden modularen Arithmetik in eine klassische Information umgewandelt, die durch einen als Messung bezeichneten Prozess aus dem Quantenschaltkreis abgerufen werden kann.

Alles in allem beginnt der Shor-Faktorisierungsalgorithmus mit ein paar klassischen Schritten. Die Quantenkomponente findet dann die Periode der zu faktorisierenden Zahl. Dies geschieht durch modulare Quantenarithmetik, deren Ergebnis von Quanteninformation in klassische Information umgewandelt wird, so dass es verwendbar ist. Und schließlich gibt es noch ein paar klassische Schritte. Wenn die Antwort nicht gefunden wird und die Zahl folglich nicht faktorisiert werden kann, wird der Algorithmus in seiner Gesamtheit angepasst und wiederholt.

‍

Wie viele Qubits werden für den Shor-Algorithmus benötigt? 

Um diese Frage zu beantworten, muss zunächst zwischen physikalischen und logischen Qubits unterschieden werden. Alle heutigen Qubits sind physikalische Qubits. Sie sind extrem "verrauscht", das heißt, sie sind fehleranfällig. Die Ergebnisse von Quantenberechnungen jeglicher Bedeutung machen es unmöglich, richtige von falschen Antworten zu unterscheiden. Jede mögliche Lösung hat die gleiche Wahrscheinlichkeit, richtig zu sein, was dasselbe ist, wie überhaupt keine Antworten zu haben.

Hier kommen die logischen Qubits ins Spiel. Physikalische Qubits müssen so miteinander verbunden und strukturiert werden, dass sie gemeinsam eine ausreichende Fehlerkorrektur bieten, um gemeinsam als "fehlertolerant" zu gelten. An diesem Punkt werden diese Qubit-Kollektive als "logische Qubits" oder manchmal als "perfekte Qubits" bezeichnet.

Diese logischen Qubits sind Abstraktionen. Ein heutiger Quantenschaltkreis mit fünf Qubits repräsentiert fünf stark verrauschte, fehleranfällige physikalische Qubits. Die Entwickler von Quantenalgorithmen der nahen Zukunft werden wollen, dass diese fünf Qubits logische, fehlertolerante und fehlerfreie Qubits darstellen. Die Schätzungen darüber, wie viele physische Qubits benötigt werden, um ein logisches Qubit zu repräsentieren, variieren, aber eine vernünftige Zahl, mit der man arbeiten kann, ist 1.000. Die meisten Schätzungen gehen davon aus, dass ein Quantencomputer etwa 1.000 physische Qubits benötigt, um ein einziges logisches Qubit zu repräsentieren.

Um zu verdeutlichen, wie schwierig das ist, hat der größte Quantencomputer heute nur 127 physische Qubits. Und obwohl IBM das Ziel hat, bis zum nächsten Jahr ein Gerät mit 1.000 Qubits vorzustellen, sind das immer noch nur 1.000 physische Qubits. Es bleibt noch viel zu tun, um das erste logische Qubit zu entwickeln.

Die Schätzungen für die Anzahl der Qubits, die Shors Faktorisierungsalgorithmus benötigt, variieren erheblich. Zunächst muss, wie bereits erwähnt, zwischen Schätzungen für logische Qubits und Schätzungen für physikalische Qubits unterschieden werden. Je nach Zielsetzung des Forschers kann die Anzahl der benötigten Qubits reduziert werden, was zu Lasten der Ausführungszeit und der Schaltungstiefe geht. Andererseits kann die Anzahl der Qubits deutlich erhöht werden, was die Ausführungszeit verkürzt und die Schaltungstiefe verringert. Die Unterschiede bestehen darin, dass niedrigere Qubit-Zahlen früher zur Verfügung stehen, während die kürzesten Laufzeiten am vorteilhaftesten sind. Es folgt eine Auswahl von Schätzungen.

In einem Papier vom 1. August 1996 mit dem Titel "Efficient networks for quantum factoring" (Effiziente Netzwerke für Quantenfactoring) von David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni und John Preskill schätzten die Autoren, dass das Factoring einer K-Bit-Zahl ^K3 Zeit in Anspruch nehmen und 5K+1 logische Qubits erfordern würde. Die Faktorisierung einer 2.048-Bit-Zahl, die sich auf das Brechen der RSA-Verschlüsselung bezieht, würde also 8,6 Milliarden Zeit in Anspruch nehmen und 10.241 logische Qubits oder etwa 10 Millionen physikalische Qubits erfordern. Leider ist nicht klar, wie lange 8,6 Milliarden Zeit benötigen würden, da verschiedene Qubit-Technologien mit unterschiedlichen Geschwindigkeiten arbeiten.

In einer Veröffentlichung vom 21. Februar 2003 mit dem Titel "Circuit for Shor's algorithm using 2n+3 qubits" von St'ephane Beauregard schätzten die Autoren, dass die Faktorisierung einer K-Bit-Zahl 2n+3 logische Qubits erfordern würde. Die Faktorisierung einer 2.048-Bit-Zahl würde also nur 4.099 logische Qubits oder etwa 4 Millionen physikalische Qubits erfordern. Auch hier gilt, dass es heute keine logischen Qubits gibt. Dennoch brachte diese Arbeit den Shor-Faktorisierungsalgorithmus der Umsetzung näher. 

In einem Buch vom Mai 2014 mit dem Titel "Fast quantum modular exponentiation architecture for Shor's factoring algorithm" (S. 0649-0682) von Archimedes Pavlidis und Dimitris Gizopoulos schlugen die Autoren eine 9n+2-Implementierung vor, bei der eine beträchtliche Anzahl von Qubits hinzugefügt wurde, um die Schaltungstiefe zu verringern. Um eine 2.048-Bit-RSA-Verschlüsselung zu knacken, wären 18.434 logische Qubits oder etwa 18 Millionen physikalische Qubits erforderlich. Ein Grund für die Minimierung der Schaltungstiefe ist, dass Qubits mit der Zeit an "Kohärenz" verlieren. Je länger die Ausführung einer Schaltung dauert, was zum Teil durch die Schaltungstiefe bestimmt wird, desto mehr Rauschen kann in das System eindringen und desto mehr Fehler können in den Ergebnissen auftauchen. Auch heute noch besteht eine Möglichkeit, Fehler zu reduzieren, darin, die Schaltungstiefe zu minimieren.

In einer Veröffentlichung vom 13. April 2021 mit dem Titel "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" (Wie man 2048 Bit RSA-Ganzzahlen in 8 Stunden mit 20 Millionen verrauschten Qubits faktorisiert) von Craig Gidney und Martin Eker schätzen die Autoren, dass zum Brechen der RSA-Verschlüsselung etwa 20.000 logische Qubits oder etwa 20 Millionen physikalische Qubits erforderlich wären. Die Autoren gehen noch einen Schritt weiter und beziffern die Laufzeit für ihre Konfiguration auf nur acht Stunden. Vergleicht man dies mit der Schätzung, die die leistungsfähigsten Supercomputer der Welt benötigen, um die RSA-Verschlüsselung zu knacken, was weit über ein Menschenleben hinausgeht, wird die Leistungsfähigkeit von Shors Faktorisierungsalgorithmus deutlich. Weitere Schätzungen über die Anzahl der Qubits für Shors Algorithmus finden Sie in den Referenzen zu diesem Artikel.

Auch hier gilt, dass die Laufzeit des Shor-Algorithmus umgekehrt proportional zur Anzahl der verfügbaren logischen Qubits ist. Sie hängt auch von der verwendeten Qubit-Technologie ab, da verschiedene Quantencomputer Operationen mit sehr unterschiedlicher Geschwindigkeit ausführen. Je weniger Qubits benötigt werden, desto länger dauert die Ausführung des Algorithmus, aber desto eher werden moderne Kryptosysteme veraltet sein. Umgekehrt gilt: Je mehr Qubits zur Verfügung stehen, desto schneller können moderne Kryptosysteme geknackt werden. Aber glücklicherweise sind diese Tage noch weiter entfernt.

Wie wird der Shor-Algorithmus ausgeführt?

Das können Sie nicht. 

Die größte Zahl, die bisher mit dem Shor-Algorithmus faktorisiert wurde, ist 21. Und die kleinstmögliche Zahl, die mit dem Algorithmus faktorisiert werden kann, ist 15. Das ist ein sehr enger Bereich, und zwar aus zwei Gründen. Erstens erfordert der Shor-Faktorisierungsalgorithmus, wie bereits erwähnt, eine große Anzahl von Qubits, und eine große Anzahl von Qubits gibt es nicht. Zweitens sind die heutigen Qubits "verrauscht", was bedeutet, dass sie bemerkenswert fehleranfällig sind. Die für den Algorithmus erforderliche Schaltungstiefe führt zu Ergebnissen mit so vielen Fehlern, dass es unmöglich ist, richtige Lösungen von falschen zu unterscheiden.

Mit anderen Worten: RSA und andere potenziell angreifbare Kryptosysteme sind sicher. Für den Moment. Das NIST arbeitet weiterhin an der Auswahl eines Post-Quantum-Standards, auch bekannt als "quantensicherer" Standard, der hoffentlich weit verbreitet implementiert wird, lange bevor genügend fehlertolerante Qubits zur Verfügung stehen, um diese drohende Gefahr zu realisieren.

Trotz des langen Zeitrahmens und der Anstrengungen zur Risikominderung ist der Shor-Faktor-Algorithmus heute noch genauso gut geeignet, das Bewusstsein für das Quantencomputing zu schärfen wie bei seiner ersten Entdeckung. Führungskräfte in allen Branchen müssen sich mit potenziellen Risiken für sensible Kommunikation und Daten befassen, und dieses Risiko ist echt. Dabei werden sie hoffentlich mit den Dutzenden anderer potenzieller Anwendungsfälle des Quantencomputings vertraut gemacht, von denen ihre jeweiligen Unternehmen eines Tages erheblich profitieren könnten.

Besuchen Sie Classiqs Bibliothek für eine Implementierung des Algorithmus von Shor‍