Problem gelöst – in rund drei Minuten statt 10.000 Jahren – Seite 1

Es klingt wie Science-Fiction: Der Internetkonzern Google will die Quantum Supremacy erreicht haben, zu Deutsch "Quantenüberlegenheit". Man habe eine Maschine entwickelt, die Probleme lösen kann, an denen selbst die bisher leistungsfähigsten Supercomputer gescheitert wären, hieß es in einem geleakten Papier vergangene Woche. Das klingt ein wenig nach Weltherrschaft und Zeitenwende. Übernehmen die Quantencomputer nun die Macht? Haben herkömmliche Rechner bald ausgedient? Und lassen sich Passwörter also jetzt in Millisekunden knacken? Ganz so weit ist es noch nicht.

Zunächst einmal handelt es sich bei dem Papier, von dem mittlerweile Versionen im Netz kursieren, um eine Art Nichtpapier. Irgendjemand bei der amerikanischen Weltraumbehörde Nasa, die mit Google zusammenarbeitet, hat es versehentlich online gestellt. Zwar verschwand das Dokument rasch wieder, aber aufmerksame Leser hatten da längst eine Sicherungskopie erstellt. Die Financial Times brachte die Nachricht in Umlauf und die Fachwelt tauscht sich seitdem darüber aus. Google aber schweigt, weshalb Quantenforscher auf eine reguläre Veröffentlichung hoffen, um sich mit den Details auseinandersetzen zu können.

Sollte stimmen, was in dem geleakten Paper steht – und daran zweifelt eigentlich kein Experte –, dann hat Google noch keinen wirklichen Quantencomputer vorgestellt, mit dem man allgemeine Probleme lösen kann. Stattdessen haben die Forscher einen Chip namens Sycamore entwickelt, auf dem 53 Qubits arbeiten, das ist das Quantenäquivalent zu den herkömmlichen Bits. Während Letztere immer den Wert 1 oder 0 annehmen, kann ein Qubit aufgrund seiner Quanteneigenschaften in einem Überlagerungszustand verharren und erst am Ende der Rechnung einen der beiden Werte annehmen. Dadurch lassen sich theoretisch eine Reihe von mathematischen Problemen viel schneller lösen als auf herkömmlichen Computern.

Googles Chip ist wie der Flieger der Brüder Wright

Wie das Problem, für das der Sycamore-Chip optimiert war: Es handelt sich um eine komplexe Berechnung von Zufallszahlen, für die heutige Rechner schätzungsweise 10.000 Jahre brauchen würden – der Quantenchip benötigte laut dem Papier nur drei Minuten und 20 Sekunden. Und damit erfüllte er das Kriterium der Quantenüberlegenheit, wie sie der Physiker John Preskill 2012 definierte: nämlich dass ein Quantencomputer eine Aufgabe bewältigt, die selbst für die größten herkömmlichen Supercomputer praktisch unlösbar ist.

Die Google-Ingenieure haben das Problem so ausgewählt, dass Sycamore einen gewaltigen Heimvorteil hatte. Trotzdem ist das eine bravouröse Pionierleistung. Experten wie der Informatiker Scott Aaronson von der University of Texas in Austin vergleichen sie mit dem ersten Flug der Brüder Wright im Jahr 1903 – deren Flieger war auch kein praktisches Transportmittel, sondern eine Art Machbarkeitsstudie. Doch nur 16 Jahre später überquerten John Alcock und Arthur Whitten Brown per Flugzeug zum ersten Mal den Atlantik. Entsprechend erwarten die Experten nach Googles Experiment eine rasante Weiterentwicklung der Quantenrechner. Neben Google steckt das amerikanische IT-Unternehmen IBM viel Geld in entsprechende Projekte. In rund zehn Jahren könnte die Technik praxisreif sein.

Nicht bei jeder Rechnung können Quantencomputer ihre Überlegenheit ausspielen. Aber auf einem Gebiet könnten sie die Welt erschüttern, zumindest die digitale: Mit einer großen Zahl von Qubits könnten sie nämlich fast alle Verschlüsselungsalgorithmen knacken, die heute die sichere Kommunikation im Internet garantieren.

Verschlüsselung sollte schon jetzt quantensicher sein

Auch wenn nur wenige Internetnutzer bewusst solche Verfahren einsetzen, so läuft doch ein Großteil der Kommunikation im Netz heute verschlüsselt ab. Immer wenn in der Adresszeile des Browsers "https" steht und nicht nur "http", wandern die Daten nicht im Klartext hin und her, sondern als unleserlicher Code. Auch viele Mail-Provider, etwa Googles Gmail, verschlüsseln die Botschaften. Und bei Messaging-Diensten wie Apples iMessage oder WhatsApp ist die Verschlüsselung so stark, dass nicht einmal der Dienstleister lesen kann, was die Menschen so hin und her schicken.

Es herrscht ein ständiges Wettrüsten zwischen Verschlüsselern und Codeknackern. Schon weil die Computer immer leistungsfähiger werden, ist es heute möglich, viele schwächere Codes von früher durch das Ausprobieren sämtlicher heute zur Verfügung stehender Schlüssel brutal zu knacken. Die Kryptoverfahren, die das Netz sicher machen, werden im Hintergrund routinemäßig verstärkt, etwa indem immer längere Schlüsselcodes verwendet werden.

Diese schrittweise Verbesserung wird allerdings nichts mehr nützen, wenn leistungsfähige Quantencomputer einsatzbereit sind. Die Nachricht über Googles Erfolg zeigt: "Leistungsfähige Quantencomputer rücken näher. Darum müssen wir jetzt handeln", sagt Johannes Buchmann von der Technischen Universität Darmstadt. Buchmann gehört zur kleinen Gemeinde der Forscher, die an quantensicheren Verschlüsselungsalgorithmen arbeiten, die Disziplin nennt sich auch Post-Quanten-Kryptografie.

Alle üblichen Verfahren sind gefährdet

Die Aussage "Quantencomputer können alle Verschlüsselungsverfahren knacken" ist nämlich verkürzt. Anfällig sind alle heute üblichen Verfahren. Die beruhen auf zwei unterschiedlichen asymmetrischen Rechenoperationen, die in der einen Richtung einfach auszuführen sind, in der anderen aber sehr schwer. Die eine ist die Zerlegung großer Zahlen in ihre Primfaktoren. Dass zum Beispiel 54.789.727 das Produkt der Primzahlen 8.737 und 6.271 ist, bekommt man nur durch mühseliges Probieren heraus, und an größeren Zahlen scheitern selbst die besten Supercomputer. Die umgekehrte Rechnung dagegen – die Erzeugung einer Zahl, wenn die Primfaktoren bekannt sind – ist eine simple Multiplikation. Die zweite Operation, die zur Verschlüsselung eingesetzt wird, ist die Berechnung des sogenannten diskreten Logarithmus einer ganzen Zahl. 

Beide eignen sich für die Public-Key-Verschlüsselung, weil man die codierten Nachrichten nur lesen kann, wenn man die – öffentlich sichtbare – Zahl entsprechend zerlegen kann. Dies können nur die Kommunikationspartner, die über den privaten Schlüssel verfügen. Aber für beide Operationen wies der Mathematiker Peter Shor schon 1994 nach: Während wir auf herkömmlichen Computern kein schnelles Verfahren für die schwierige Richtung kennen, können Quantencomputer mit ausreichend Qubits diese Aufgaben in überschaubarer Zeit lösen.

Der Informatiker Michele Mosca von der kanadischen University of Waterloo hat die befürchtete Quantenapokalypse 2015 in eine Formel gekleidet: Wenn D plus T größer ist als Qc, haben wir ein Problem. T ist dabei die Zeit, die wir brauchen, um alle Systeme auf quantensichere Verschlüsselung umzustellen. D ist die (gewünschte) Zeit, die unsere Daten sicher sein sollen, auch diejenigen, die wir während des Zeitraums T noch erzeugen. Wenn vor Ablauf von T+D ein leistungsfähiger Quantencomputer gebaut wird (Qc), dann ist ein Teil der Daten, die wir bis dahin produziert haben, nicht mehr sicher.*

Mosca hat auch persönliche Schätzungen für den Faktor Qc: Mit einer Wahrscheinlichkeit von 1:6, meint er, wird ein solcher Computer innerhalb von zehn Jahren existieren, mit einer 50:50-Wahrscheinlichkeit in 15 Jahren. Hat sich das durch die Nachricht der letzten Woche geändert? "Es ist noch ein schwieriger Weg", sagt Mosca auf Nachfrage von ZEIT ONLINE, "aber solche Fortschritte verbessern tatsächlich die Chancen für die Kryptoanalyse durch Quantencomputer." Seine neue Schätzung will er auf einer Konferenz im November bekannt geben.

Ein Vorbild: das McEliece-Kryptosystem

Deshalb sagt Buchmann: "Wir müssen heute damit beginnen, unsere komplexen IT-Systeme quantencomputerresistent zu machen. Solche Umstellungen dauern lange." Und möglichst viele der Informationen, die wir heute erzeugen, etwa Gesundheitsdaten, sollten für eine lange Zeit sicher sein und nicht rückwirkend von einem Quantencomputer geknackt werden können.

Erste Verfahren dazu gibt es bereits. Eine Reihe von Algorithmen sind quantensicher – wobei das einschränkend heißt: Noch ist kein Quantenverfahren bekannt, das sie knacken kann. Denn eine mathematisch beweisbare Sicherheit gibt es nicht. Ein Beispiel ist das McEliece-Kryptosystem, das auf der Multiplikation großer Matrizen beruht und nach heutiger Kenntnis immun gegen Quantencomputer-Attacken ist. Das Verfahren wurde bereits 1978 erfunden und vor allem deshalb nicht eingesetzt, weil es datenhungriger ist als die heute verwendeten Methoden: Der Schlüssel braucht etwa 1.000-mal so viel Platz, bei heutigen Sicherheitsstandards ein Megabyte. Aber inzwischen sind die Internetverbindungen schnell genug und der Speicherplatz groß genug, um diesen Nachteil in Kauf nehmen zu können. Andere Verfahren haben diesen Nachteil nicht, dafür blähen sie die übertragenen Nachrichten auf. 

Welches System die beste Alternative ist, diskutieren Forscherinnen und Forscher noch. Auch die US-amerikanische Standardisierungsbehörde NIST begutachtet die Postquanten-Kryptoalgorithmen, 26 gelten derzeit als besonders vielversprechend. Die Chancen stehen also gut, sich vor der Quantenapokalypse auf eine neue, sicherere Internetkommunikation zu einigen.

*Anm. d. Red.: Wir haben diese Stelle nachträglich präzisiert.