Als Physiker in den 1980er Jahren zum ersten Mal Quantencomputer erwähnten, klang das nach einer netten theoretischen Idee, die aber wahrscheinlich für immer Theorie bleiben würde. Vor 25 Jahren veröffentlichte der Mathematiker Peter Shor dann jedoch einen Artikel, der diese Wahrnehmung massiv veränderte.

Er zeigte darin, wie Quantencomputer ein entscheidendes Problem überwinden können: Die Maschinen verarbeiten Informationen als Qubits – Quantenversionen von gewöhnlichen Bits, die jeweils als eine Überlagerung der Zustände 0 und 1 vorliegen. Aber Quantenzustände sind anfällig für Rauschen, was zu Informationsverlust führt. Shors Korrekturtechnik erkennt die durch Rauschen verursachten Fehler und stellt damit eine Möglichkeit dar, Quanteninformationen robuster zu machen.

Bereits 1994 hatte der US-Forscher vom Massachusetts Institute of Technology die Welt der Physik und der Informatik aufgeschreckt, als er eine erste potenzielle Anwendung für die damals noch hypothetischen Quantencomputer fand: Ein von ihm geschriebener Algorithmus erlaubt es den Maschinen, blitzschnell große Zahlen in ihre Primfaktoren zu zerlegen. Für unsere heutige Gesellschaft ist das potenziell ein Problem, denn viele Verschlüsselungstechniken im Internet basieren darauf, dass klassische Computer die Primfaktoren großer Zahlen nur mit riesigem Rechenaufwand finden können.

Quantencomputer sind heute eine Realität, obwohl sie noch nicht ausgereift genug sind, um Zahlen mit mehr als zwei Stellen in Primfaktoren zu zerlegen. Aber es ist vermutlich bloß eine Frage der Zeit, bis die Rechner die Internetverschlüsselung bedrohen. Peter Shor spricht im Interview über die Folgen seiner Arbeit und darüber, wohin sich die Internetsicherheit entwickelt.

Herr Shor, waren Quantencomputer vor Ihrem Factoring-Algorithmus vor allem eine theoretische Kuriosität?

Meine Arbeit brachte die Leute sicherlich auf die Idee, dass diese Maschinen etwas Nützliches leisten könnten. Der Informatiker Daniel Simon hat in einem Vorläufer meines Ergebnisses ein von ihm entwickeltes Problem gelöst, das zeigt, dass Quantencomputer exponentiell schneller als gewöhnliche Computer sein können. Aber selbst nach Simons Algorithmus war nicht klar, dass sie dabei etwas Sinnvolles tun könnten.

Wie war die Reaktion auf Ihre Ankündigung des Factoring-Algorithmus?

Zuerst hatte ich nur ein Zwischenergebnis. Ich hielt an einem Dienstag im April 1994 in den Bell Labs, wo ich zu der Zeit arbeitete, einen Vortrag darüber. Die Nachricht verbreitete sich erstaunlich schnell, und am folgenden Wochenende rief mich der Informatiker Umesh Vazirani an. Er sagte: »Ich habe gehört, dass die Primfaktorzerlegung auf einem Quantencomputer funktioniert – sagen Sie mir bitte, wie das funktioniert.«

Dabei hatte ich das Faktorisierungsproblem zu diesem Zeitpunkt noch gar nicht wirklich gelöst. Doch wie bei dem Kinderspiel »Stille Post« hatte sich mein Zwischenergebnis beim Weitererzählen zu einer Art Endergebnis entwickelt. Zum Glück hatte ich die noch ausstehenden Probleme in der Zwischenzeit überwunden, so dass ich Umesh sagen konnte, wie es geht. Alle möglichen Leute baten mich um meinen Fachaufsatz zu dem Thema, bevor ich ihn überhaupt fertig geschrieben hatte. So musste ich vielen einen unvollständigen Entwurf schicken.

Aber viele Experten waren noch der Meinung, dass Quantencomputer Informationen verlieren würden, bevor ihre Berechnung beendet ist.

Einer der Einwände war, dass man in der Quantenmechanik ein System, wenn man es misst, unweigerlich zerstört. Ich habe gezeigt, wie man den Fehler messen kann, ohne die Berechnung zu messen – und dann kann man den Fehler korrigieren, ohne die Berechnung zu zerstören. Nachdem ich diese Abhandlung über Fehlerkorrektur im Jahr 1995 fertig hatte, waren immerhin einige der Skeptiker überzeugt, dass Quantencomputing machbar sein könnte.

»Sicherlich war von Seiten Googles etwas Publicity im Spiel. Aber sie haben auch einen sehr beeindruckenden Quantencomputer«
Peter Shor

Die Fehlerkorrektur stützt sich auf »physikalische« und »logische« Qubits. Was ist der Unterschied?

Wenn Sie einen Quantencomputeralgorithmus schreiben, gehen Sie davon aus, dass die Qubits rauschfrei sind, also beim Rechnen nicht gestört werden. Das sind die logischen Qubits. Tatsächlich haben wir in unseren Quantencomputern aber Störungen. Wenn wir also unseren Algorithmus laufen lassen, ohne das Rauschen auszugleichen, kommt es fast zwangsläufig zu Fehlern. Ein physikalisches Qubit ist solch ein »verrauschtes« Qubit.

Um unseren Algorithmus fehlerfrei auszuführen, müssen wir die physikalischen Qubits verwenden, um logische Qubits zu repräsentieren, bei denen die Fehler korrigiert sind. Der beste bislang bekannte Weg dafür führt zu einem großen Overhead: Für jedes logische Qubit brauchen wir sehr viele physikalische.

Es ist ziemlich kompliziert herauszufinden, wie viele weitere Qubits für diese Technik nötig sind. Wenn Sie einen Quantencomputer mit der so genannten Surface-Code-Fehlerkorrektur bauen wollen – was im Moment der beste Kandidat ist –, brauchen Sie etwa 100 physikalische Qubits für jedes logische Qubit, vielleicht sogar mehr.

Im Jahr 2019 zeigte Google, dass sein 54-Qubit-Quantencomputer ein Problem lösen kann, dessen Lösung auf einem klassischen Computer sehr viel länger dauern würde – die erste Demonstration eines »Quantenvorteils«. Wie war Ihre Reaktion?

Es ist definitiv ein Meilenstein. Es zeigt, dass Quantencomputer bei speziellen Problemen besser sein können als klassische Computer. Sicherlich war von Seiten Googles etwas Publicity im Spiel. Doch sie haben auch einen sehr beeindruckenden Quantencomputer. Allerdings muss dieser noch viel besser werden, bevor er etwas wirklich Interessantes leisten kann. Es gibt auch das Start-up IonQ: Momentan sieht es so aus, als könnte es einen Quantencomputer bauen, der in mancher Hinsicht besser ist als der von Google oder IBM.

»Die NSA hat mit ihrem ersten Quantencomputer sicherlich viel wichtigere Dinge zu tun, als Ihre privaten E-Mails zu lesen – es sei denn, Sie sind der chinesische Botschafter«
Peter Shor

Wenn Quantencomputer einmal große Primzahlen verarbeiten, sollten sie das allgegenwärtige Internetverschlüsselungssystem RSA knacken können.

Ja, aber als Erstes wird entweder die NSA (Anm.: die Nationale Sicherheitsbehörde der USA) die RSA-Verschlüsselung brechen oder eine andere große Institution. Erst mal werden diese Computer vor allem langsam sein. Wenn Sie mit Ihrem Quantencomputer nur einen RSA-Schlüssel pro Stunde knacken können, wird man damit wohl nur Zugänge knacken, die eine hohe Priorität haben oder die nationale Sicherheit betreffen. Die NSA hat mit ihrem ersten Quantencomputer sicherlich viel wichtigere Dinge zu tun, als Ihre privaten E-Mails zu lesen – es sei denn, Sie sind der chinesische Botschafter.

Gibt es denn Kryptografie-Systeme, die auch im Zeitalter der Quantencomputer sicher sein werden – die »Post-Quanten-Verschlüsselung«?

Ich glaube, wir haben Post-Quanten-Kryptosysteme, mit denen man RSA ersetzen könnte. RSA ist im Moment nicht das große Problem. Das große Problem ist, dass es andere Möglichkeiten gibt, die Sicherheit im Internet zu brechen, wie schlecht programmierte Software, Viren und Phishing-E-Mails. Ich denke, das einzige Hindernis, RSA durch ein sicheres Post-Quanten-Kryptosystem zu ersetzen, werden die Willenskraft und die Programmierzeit sein. Wir wissen, wie es geht; es ist nur nicht klar, ob wir es rechtzeitig schaffen werden.

Besteht die Gefahr, dass wir unvorbereitet erwischt werden?

Ja, schauen Sie sich mal an, wie groß die Anstrengungen waren, um 1999 den Millennium-Bug zu beheben. Auch bei einem Übergang zu einem Post-Quantum-System werden wir uns enorm anstrengen müssen. Und wenn wir zu lange warten, wird es zu spät sein.