Wie Primzahlen helfen, den Quantencomputer zu verbessern

Wissenschaftler des Jülich Supercomputing Centre haben einen neuen Weltrekord aufgestellt: Sie simulierten einen Quantencomputer mit 48 Qubits gleich auf zwei verschiedenen Supercomputern. Um die Belastungsgrenzen ihres simulierten Quantenrechners zu testen, verwendeten sie ein Verfahren, das höchste Rechenkapazitäten erfordert: Die Primfaktorenzerlegung großer Zahlen. In ihrem simulierten Quantencomputer setzten sie den sogenannten Shor-Algorithmus so erfolgreich um, dass sie ihn für eine Zahl bisher unerreichter Größe anwenden konnten: 65531.

Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen. Was sind die Primfaktoren der Zahl 21? Die meisten Grundschüler kennen die Antwort – 3 und 7 – auswendig. Für eine größere Zahl, sagen wir mal 217, werden die meisten Menschen schon etwas länger brauchen, vermutlich auch einen Taschenrechner. Die Zerlegung – oder Faktorisierung – einer sehr großen Zahl mit mehreren hundert Stellen kann Jahre in Anspruch nehmen, selbst für Wissenschaftler mit Supercomputern.

Weil die Primfaktorenzerlegung großer Zahlen so unglaublich schwierig ist, ist sie die Grundlage für alle weitverbreiteten Verschlüsselungsverfahren zum Schutz von Kreditkarten, Staatsgeheimnissen und anderen vertraulichen Daten. Wegen der langen Rechenzeit, die ein herkömmlicher Computer braucht, um einen solchen Code zu knacken, gelten sie als sehr sicher.

Deshalb sorgte es für großes Aufsehen, als der amerikanische Mathematiker und Computerwissenschaftler Peter Shor im Jahr 1994 seinen Faktorisierungs-Algorithmus für Quantencomputer vorstellte. Der Shor’sche Algorithmus erlaubt die effiziente Zerlegung einer großen Zahl in zwei Primzahlen, schneller – viel schneller – als klassische Computer dazu in der Lage sind.

"Der Grund dafür ist nicht allein die extrem schnelle Rechenleistung eines Quantencomputers", erklärt Kristel Michielsen vom Jülich Supercomputing Centre. "Besonders nützlich ist er nämlich für Probleme mit ganz speziellen Eigenschaften: Probleme für deren Lösung man die Gesetze der Quantenmechanik anwenden kann."

Dazu gehören neben Simulationen quantenmechanischer Systeme wie Atome oder Moleküle auch Suchalgorithmen, etwa für das Aufspüren von Einträgen in ungeordneten Datenbanken. Auch die Primfaktorenzerlegung großer Zahlen ist eines der Probleme, für die sich Quantencomputer besonders gut eignen. Wie eben der Shor-Algorithmus. Neben seiner Anwendung für Verschlüsselungssysteme ist er auch einer der wichtigsten Programmcodes, um die Funktionsweise und Leistungsfähigkeit von Quantencomputern zu testen.

Effizient simuliert

Ein wirklich praktisch anwendbarer Quantencomputer selbst ist allerdings noch Zukunftsmusik, auch wenn große Firmen wie Google, Intel und IBM seit einigen Jahren an seiner Realisierung arbeiten. Vor allem die besondere Fehleranfälligkeit solcher Computer ist noch ein großes Problem. Doch wenn die ersten Quantencomputer verfügbar sein werden, müssen Software-Entwickler und Ingenieure nicht bei Null anfangen.

"Auf herkömmlichen digitalen Computern lässt sich bereits heute die Funktionsweise relativ großer Quantenrechner simulieren. Der Rechenaufwand ist allerdings enorm", erklärt Michielsen. Mit jedem simulierten Quantenbit – kurz: Qubit – verdoppelt sich der Bedarf an Speicherplatz. "Es gibt derzeit nur wenige Supercomputer auf der Welt, die über ausreichend Speicher, Rechenkerne und angemessen schnelle Netzwerkverbindungen verfügen."

Ebenso wichtig ist die Software. Anders als herkömmliche Rechner haben Supercomputer hunderttausende oder sogar Millionen Prozessoren. Viele Programmiercodes sind nicht darauf ausgerichtet, auf so vielen Elementen gleichzeitig zu laufen und verlieren mit jedem zusätzlichen Rechenknoten an Effizienz. Die von Michielsen gemeinsam mit ihren Partnern seit über zehn Jahren weiterentwickelte Software dagegen zeigt praktisch keine Performance-Einbußen. Ihr Code reduzierte den Speicherbedarf für einen simulierten Quantencomputer auf ein Achtel.

Für ihre Simulation nutzten sie zwei der schnellsten Supercomputer der Welt: den chinesischen Sunway TaihuLight und den japanischen K. Damit gelang es ihnen, den weltweit größten universalen Quantencomputer zu simulieren. Er verfügt über 48 Qubits.

Unendlich viele Möglichkeiten

Das Qubit ist die die grundlegende Einheit des Quantencomputers. Während das herkömmliche Bit, auf dem unsere jetzigen Computer beruhen, entweder den Wert 0 oder 1 annimmt, kann ein Qubit beide Werte gleichzeitig annehmen. "Physiker sprechen von einer Überlagerung oder Superposition der beiden Zustände", erklärt Kristel Michielsen. "Tatsächlich befindet sich das Qubit – solange es nicht ausgelesen wird – in überhaupt keinem festen Zustand. Es ist sowohl 0 als auch 1 als auch jeder mögliche Wert dazwischen. Erst durch das Auslesen werden die unendlich vielen Möglichkeiten auf entweder 0 oder 1 reduziert."

Zur Verdeutlichung kann man sich einen gewöhnlichen Tischventilator mit zwei Flügeln vorstellen. Ein herkömmliches Bit ist ein Ventilator in Ruhe, die beiden Flügel zeigen, beispielsweise, nach oben und nach unten. Ein Qubit dagegen ist ein Ventilator, der sich so schnell dreht, dass man seine Flügel nicht mehr erkennen kann: sie zeigen scheinbar in alle Richtungen gleichzeitig.

Rechenzeit von Jahren auf Tage verkürzt

Diese Überlagerung der Zustände macht sich der Quantencomputer zunutze. Er rechnet nicht nur mit den Werten 0 und 1, sondern mit einer Überlagerung aller möglichen Werte. Dadurch werden viele Rechenwege gleichzeitig durchlaufen. Als Ergebnis der Rechnung ergibt sich ein sogenanntes Interferenzmuster – ähnlich einem Stroboskopeffekt, der einen Tischventilator aussehen lässt, als würde er stillstehen oder sich langsam rückwärts drehen.

Der Shor’sche Algorithmus nutzt diese Interferenzmuster, um Primfaktoren zu finden: eine Aufgabe die für sehr große Zahlen extrem schwierig ist. Bei einem herkömmlichen Computer nimmt der Aufwand exponentiell mit der Länge der Zahl zu: Vereinfacht gesagt werden alle möglichen Faktoren nacheinander ausprobiert. Auf einem Quantencomputer hingegen wächst der Aufwand nur mit dem Quadrat der Zahlenlänge an – für sehr große Zahlen kann sich damit die benötigte Rechenzeit von Jahren auf Tage verkürzen.

Ein Meilenstein

Nun haben Kristel Michielsen und ihre Kollegen Shors Algorithmus in ihrer Quantencomputer-Simulation erfolgreich angewendet. Es gelang ihnen, die Zahl 65531 in ihre Faktoren 19 und 3449 zu zerlegen – ein Meilenstein, der gleichzeitig den praktischen Nutzen von Algorithmen für Quantencomputer demonstriert. Doch noch ist ihre Primzahlenzerlegung weit davon entfernt, die Verschlüsselungstechnik zu revolutionieren. Denn je größer die Zahl, desto mehr Qubits benötigt man.

"Unsere Simulation verfügt über 48 Qubits, und ist damit der größte simulierte universelle Quantencomputer, weltweit", erklärt Michielsen. 65531 ist die größte Zahl, die auf einem solchen System mit dem Shor-Algorithmus berechnet werden kann. "Wir vermuten, dass sich das auch in den nächsten fünf Jahren oder so nicht ändern wird", sagt Michielsen. "Doch wir hoffen, dass wir uns irren."

Regine Panknin