Ende Dezember 2022 veröffentlichte ein chinesisches Forschungsteam einen Fachartikel, in dem die Wissenschaftler behaupteten, dass sie einen Algorithmus entwickelt hätten, der – theoretisch – bereits heute mit einem rudimentären Quantencomputer die derzeit gängigsten Methoden zum Schutz der digitalen Privatsphäre überwinden könnte. Die Technik funktioniere in einer kleinen Demonstration, schreiben die Forscher in der noch ungeprüften Vorveröffentlichung.

Quantencomputer sind als potenzielle Bedrohung für derzeitige Verschlüsselungssysteme bekannt, aber die Technologie steckt noch in den Kinderschuhen. Forscher schätzen, dass es noch viele Jahre dauern wird, bis Quantencomputer tatsächlich kryptografische Schlüssel – die Zeichenfolgen, die in einem Verschlüsselungsalgorithmus zum Schutz von Daten verwendet werden – schneller knacken können als gewöhnliche Computer. Dazu gehört beispielsweise die in den 1970er Jahren entwickelte RSA-Verschlüsselung, die nach den Namen ihrer drei Erfinder Rivest, Shamir und Adleman benannt wurde, sowie einige andere populäre Kryptografietechniken, die derzeit eingesetzt werden, um die Privatsphäre und Sicherheit im Internet schützen.

Quantencomputer und Quanten-Bits

In den 1990er Jahren erkannten Forscher, dass Quantencomputer die Besonderheiten der Quantenphysik ausnutzen können, um Aufgaben zu erfüllen, die für »klassische« Computer unerreichbar scheinen. Während die uns bekannten Rechner mit Bits und den Zuständen von Eins oder Null rechnen, nutzen Quantencomputer so genannte Quanten-Bits. Weil sich die Zustände von Quanten-Bits überlagern (Superposition), können sie gleichzeitig im Zustand eins oder null sein und auch in theoretisch unendlich vielen Zuständen dazwischen. Weil sich zudem mehrere Quanten-Bits miteinander verschränken lassen, kann ein Quantencomputer unzählige Rechenschritte parallel ausführen. Ein Pionier auf diesem Gebiet war Peter Shor, ein Mathematiker, der heute am Massachusetts Institute of Technology (MIT) in Cambridge arbeitet: Er zeigte, wie man die Phänomene der Quantensuperposition (die Fähigkeit von Objekten in der Größe von Atomen, in mehreren Zuständen gleichzeitig zu existieren) sowie der Quanteninterferenz (die analog dazu ist, wie sich Wellen auf einem Teich addieren oder auslöschen können) anwenden kann, um ganze Zahlen in Primzahlen zu faktorisieren, also in Zahlen zu zerlegen, die nicht weiter geteilt werden können.

Peter Shors Algorithmus würde einen Quantencomputer befähigen, exponentiell schneller zu rechnen als ein klassischer Computer, wenn es darum ginge, ein auf Primzahlen basierendes Verschlüsselungssystem wie RSA zu knacken. Um Peter Shors Ansatz umzusetzen, bräuchte es jedoch einen Quantencomputer, der viel größer ist als die zurzeit verfügbaren Prototypen. Nach Angaben von Forschern benötigte man eine Million oder mehr Qubits, um RSA-Verschlüsselungen zu überwinden. Der größte heute verfügbare Quantenchip namens Osprey, der im November 2022 von IBM vorgestellt wurde, hat 433 Qubits.

Ein neuer Ansatz

Shijie Wei von der Beijing Academy of Quantum Information Sciences und seine Mitarbeiter gingen einen anderen Weg, um die RSA-Kryptografie zu schlagen. Sie stützten sich dabei nicht auf den Algorithmus von Peter Shor, sondern auf einen Algorithmus des Mathematikers Claus-Peter Schnorr, der ihn in den 1990er Jahren an der Goethe-Universität in Frankfurt am Main entwickelte. Claus-Peter Schnorrs Algorithmus wurde für den Einsatz auf einem klassischen Computer entwickelt; das Team von Shijie Wei implementierte einen Teil davon jedoch auf einem Quantencomputer und nutzte dafür ein Verfahren namens QAOA (quantum approximate optimization algorithm).

»Einfach die Anzahl der Qubits zu erhöhen, ohne die Fehlerrate zu verringern, hilft nicht«Guilu Long, Physiker an der Tsinghua University in China

In der Veröffentlichung geben die Autoren an, dass ihr Algorithmus selbst starke RSA-Schlüssel mit Zahlen von mehr als 600 Dezimalziffern knacken könnte – mit nur 372 Qubits. In einer E-Mail an »Nature« im Namen aller Autoren wies Guilu Long, Physiker an der Tsinghua University in China, darauf hin, dass es nicht ausreiche, bloß viele Qubits zu haben, und dass die aktuellen Quantencomputer noch zu fehleranfällig seien, um eine so große Berechnung erfolgreich durchzuführen. »Einfach die Anzahl der Qubits zu erhöhen, ohne die Fehlerrate zu verringern, hilft nicht.«

Laut Chao-Yang Lu, einem Physiker, der an der University of Science and Technology of China in Hefei Quantencomputer baut und nicht an dem Projekt beteiligt war, muss für die Ausführung des QAOA-Algorithmus auf einem so kleinen Quantencomputer jedes der 372 Qubits in 99,9999 Prozent der Zeit fehlerfrei arbeiten; modernste Qubits erreichen derzeit allerdings kaum 99,9 Prozent Genauigkeit.

Das Team um Wei demonstrierte die Technik auf einem 10-Qubit-Quantencomputer, mit dem es die 15-stellige Zahl 261 980 999 226 229 in zwei Primzahlfaktoren aufteilte, nämlich 15 538 213 und 16 860 433. Die Forscher sagen, dass dies die größte Zahl ist, die bisher mit Hilfe eines Quantencomputers faktorisiert wurde. Sie ist allerdings viel kleiner als die von modernen Webbrowsern verwendeten kryptografischen Schlüssel.

Umstrittene Veröffentlichung

Das eigentliche Dilemma dabei ist: Niemand weiß, ob der QAOA-Algorithmus das Zerlegen großer Zahlen mit Hilfe eines Quantencomputers tatsächlich schneller ermöglicht als die Ausführung von Schnorrs klassischem Algorithmus auf einem Laptop. »Es muss darauf hingewiesen werden, dass unklar ist, ob die Nutzung von Qubits den Algorithmus beschleunigt«, schreiben die Autoren. Mit anderen Worten: Auch wenn Peter Shors Algorithmus die RSA-Verschlüsselung eines Tages garantiert knacken kann, falls ein ausreichend großer Quantencomputer zur Verfügung steht, könnte die auf Optimierung basierende Technik auch auf einer viel kleineren Maschine laufen – wird die Aufgabe aber womöglich nie beenden.

Michele Mosca, ein Mathematiker an der University of Waterloo in Kanada, weist außerdem darauf hin, dass QAOA nicht der erste bekannte Quantenalgorithmus ist, der ganze Zahlen mit einer kleinen Anzahl von Qubits zerlegen kann. Das hätten er und seine Mitarbeiter bereits im Jahr 2017 gezeigt. Die Fachwelt weiß also bereits, dass Quantencomputer im Grunde nicht sehr groß sein müssen, um Zahlen zu faktorisieren.

»Alles in allem ist dies eine der irreführendsten Arbeiten über Quantencomputer, die ich in den letzten 25 Jahren gesehen habe«Scott Aaronson, Quantencomputer-Theoretiker an der University of Texas

Andere Forscher äußerten sich kritisch dazu, dass die Ergebnisse der chinesischen Forscher zwar richtig sein könnten, der Vorbehalt bezüglich der Geschwindigkeit aber erst ganz am Ende komme. »Alles in allem ist dies eine der irreführendsten Arbeiten über Quantencomputer, die ich in den letzten 25 Jahren gesehen habe«, schreibt der Quantencomputer-Theoretiker Scott Aaronson von der University of Texas in Austin in einem Blogbeitrag.

In seiner E-Mail an »Nature« erklärt Guilu Long, dass er und seine Mitarbeiter planen, den einschränkenden Satz weiter nach oben zu verschieben. »Wir freuen uns auf das Peer-Review und schätzen die Kommunikation mit Wissenschaftlern aus der ganzen Welt«, heißt es in der Erklärung weiter.

Auch wenn die auf Claus-Peter Schnorr basierende Technik die Web-Verschlüsselungen nicht knacken wird, könnten Quantencomputer dies irgendwann schaffen – wenn sie Peter Shors Algorithmus ausführen. Sicherheitsforscher haben bereits eine Reihe alternativer kryptografischer Systeme entwickelt, die als weniger anfällig für Angriffe von Quantencomputern gelten und als »post-quantum« oder »quantum-safe« bezeichnet werden. Aber Forscher könnten in Zukunft noch bessere Quantenalgorithmen entwickeln, die auch diese Systeme wieder schlagen könnten – mit möglicherweise katastrophalen Folgen.

»Das Vertrauen in digitale Infrastrukturen würde zusammenbrechen«, sagt Michele Mosca. »Wir würden plötzlich von einem schrittweisen, an die jeweilige Technologie angepassten Umgang mit Quantenalgorithmen zum Krisenmanagement übergehen«, fügt er hinzu. »Das wäre in jedem Fall nicht schön.«