«Für sehr kleine Problemgrössen ist ein klassischer Computer schneller»

Quantencomputer versprechen, dass sie einige Rechenprobleme viel schneller lösen können als klassische Computer. Inwieweit ist das wahr oder zumindest realistisch?
Torsten Hoefler: Allgemein betrachtet ist diese Aussage richtig. Quantencomputer können tatsächlich einige Rechenprobleme wesentlich schneller lösen als klassische Computer. Ich würde sagen, sie sind tatsächlich in der Lage, die Rechenzeit von Jahrzehnten oder Jahren auf Stunden oder sogar Minuten zu verkürzen. Das ist zwar richtig, aber nicht für alle Rechenprobleme realistisch.

Bei welchen Problemen sind Quantencomputer nicht schneller?
Torsten Hoefler: Wenn wir zum Beispiel Wettervorhersagen oder Klimasimulationen viel schneller machen wollen, dann wüsste ich heute noch nicht, wie man diese Anwendungen mit einem Quantencomputer erheblich beschleunigen könnte. Genauso wenig wüsste ich, wie man heute maschinelles Lernen mit einem Quantencomputer deutlich beschleunigen könnte. Auch für die Strömungsdynamik in Turbulenzen werden wir wahrscheinlich mit den derzeitigen Quantenalgorithmen in absehbarer Zeit keinen praktischen Vorteil erzielen.

Sehen Sie Anwendungsbereiche in der Grundlagenforschung oder in der Industrie, in denen Quantencomputer in naher Zukunft ihre Vorteile ausspielen können?
Torsten Hoefler: Bislang wissen wir mit Sicherheit, dass Quantencomputer für eine Vielzahl von Forschungs- und Entwicklungsbereichen äusserst relevant sind. Ich denke da an Probleme wie das Knacken der bekannten kryptographischen Verfahren, die auf der Primfaktorzerlegung beruhen. Oder wenn es darum geht chemische Systeme mit einer sehr hohen Präzision zu simulieren, dann hat Quantenrechnen ein gewaltiges Verbesserungspotenzial.
Darüber hinaus ist Quantenrechnen sehr vielversprechend für Forschungsbereiche wie die Simulation von Materialeigenschaften, die auf Quantenphänomenen beruhen, neue Medikamente für die Zukunft, die Erfindung neuer Düngemittel oder das Verständnis, wie biologische Systeme funktionieren. In all diesen Bereichen können Quantencomputer eine entscheidende Rolle, spielen um die Berechnungen zu beschleunigen.

Aber noch ist das eine Zukunftsvision?
Torsten Hoefler: Ja, aber auch wenn Quantenrechnen noch nicht auf alle offenen Fragen in diesen Bereichen anwendbar ist, so sehen wir doch eindeutig einen Weg, wie wir das Potenzial von Quantencomputern besser ausschöpfen können. Das gilt jedoch nicht für alle Algorithmen. Man kann nicht einfach irgendeinen Algorithmus nehmen, ihn auf einem Quantencomputer laufen lassen und die Berechnungen werden automatisch schneller. Im Prinzip können Quantencomputer jedes Rechenproblem lösen, aber die entscheidende Frage für ihre Anwendung ist, welche Probleme sie in der Praxis schneller oder kostengünstiger lösen als klassische Computer.

Inwieweit revidieren Sie die Annahme, dass Quantencomputer immer schneller sind als klassische Computer?
Torsten Hoefler: Manche gehen davon aus, dass Quantencomputer grundsätzlich schneller sind, weil sie zum Beispiel in der Lage sind, viele Probleme in quadratisch weniger Schritten zu lösen. Aber ein einzelner Quanten-Rechenschritt ist wesentlich langsamer als ein klassischer. Aufgrund der Prinzipien der Quantenmechanik wie Überlagerung, Interferenz oder Verschränkung sind weniger Rechenschritte nötig, um ein gegebenes Problem zu lösen. Das ist der Grund, weshalb Quantencomputer versprechen, bestimmte Probleme schneller zu lösen als klassische Computer. Jedoch wäre es ein Trugschluss zu glauben, dass Quantencomputer jedes Problem wesentlich schneller lösen können als herkömmliche Computer.

Warum ist das so?
Torsten Hoefler: Beim derzeitigen Design der Quantencomputer ist jeder Rechenschritt langsamer als ein entsprechender klassischer Rechenschritt. Das liegt an der hohen Komplexität der Fehlerkorrektur und der einzelnen Schritte einer Quantenberechnung. Ausserdem hat die Industrie in der konventionellen Datenverarbeitung die Technologien seit 60 Jahren so weit vorangetrieben, dass sie extrem schnell geworden sind. Heute kann ein klassischer Computer Millionen bis Milliarden von Rechenschritten pro Sekunde ausführen. Ein Quantencomputer hingegen kann nur Hunderttausende bis vielleicht Millionen von Schritten pro Sekunde ausführen. Aus diesem Grund sind die Quantencomputer nicht in jedem Fall überlegen. Diese irrige Vorstellung einer allumfassenden Quantenüberlegenheit versuchen wir zu widerlegen. Ich bin aber sehr optimistisch, dass wir zuverlässige Quantencomputer bauen werden.

Zu welchen wissenschaftlichen Erkenntnissen sind Sie in Ihrer Studie gekommen? Für welche Arten von Problemen sind Quantencomputer am ehesten schneller?
Torsten Hoefler: Wir haben die Leistung eines marktführenden klassischen Chips mit der eines optimistisch entworfenen Quantenchips verglichen, und zwar jeweils für dasselbe Problem. Auf diese Weise haben wir als Erste ermittelt, was genau erforderlich ist, damit Quantencomputer einen echten Geschwindigkeitsvorteil erzielen. Unsere Analyse zeigt, dass bei so gut wie allen Algorithmen der klassische Computer bei sehr kleinen Problemgrössen schneller ist und der Quantencomputer bei sehr grossen Problemgrössen. Das liegt daran, dass die Zeit zur Lösung bestimmter Probleme auf einem Quantencomputer langsamer mit der Grösse der Probleme wächst als auf klassischen Computern (vgl. Grafik). Das nennen wir «Quanten-Speedup» oder Beschleunigung des Quantenrechnens.
Wir sehen auch, dass Quantencomputer im Allgemeinen schneller und praktischer für grosse Rechenprobleme mit kleinen Daten sind, aber sie sind nicht praktisch für Big-Data-Probleme. Aufgrund der begrenzten Eingangs- und Ausgangsbandbreite sind grosse Datenmengen ein Problem, das klassische Computer schneller berechnen. Ausserdem lösen klassische Computer auch ein Suchproblem in einer Datenbank schneller als ein Quantencomputer. Daher wurden Quantencomputer im Zusammenhang mit Big Data zu Unrecht gehypt.

Eine Ihrer Erkenntnisse ist, dass eine «quadratische Beschleunigung» für Quantencomputer nicht ausreicht, um ihre potenziellen Geschwindigkeitsvorteile wirklich auszuschöpfen.
Torsten Hoefler: In unserer Studie zeigen wir, dass quadratische Beschleunigungen, welche die Rechenzeit verkürzen, indem die Quadratwurzel aus der Laufzeit eines Algorithmus gezogen wird, für praktische Quantenvorteile in absehbarer Zukunft nicht ausreichen.
Wir sehen, dass wenn nur quadratische Geschwindigkeitssteigerungen implementiert werden, die Quantenberechnung für viele Probleme immer noch mehrere Monate dauern wird. Das ist in der Praxis zu langsam und zu teuer. Daraus leiten wir ab, dass mindestens kubische oder quartische  Beschleunigungen, die auf der dritten und vierten Wurzel beruhen, erforderlich sind, weil nur dann Tausende oder Millionen von Rechenoperationen machbar sind. Aber selbst kubische oder quartische Beschleunigungen sind nur die niedrigste Anforderung.
Es ist notwendig, sich auf exponentielle Beschleunigungen zu konzentrieren, bei denen die Laufzeit des Quantenalgorithmus der Logarithmus der Laufzeit des klassischen Algorithmus ist. Die vielversprechendsten Kandidaten, um echte praktische Quantenvorteile zu erzielen, sind daher Probleme mit kleinen Datenmengen und exponentieller Beschleunigung.

Was muss anders gemacht werden, um echte Hochgeschwindigkeits-Quantenberechnungen zu erreichen?
Torsten Hoefler: Ein entscheidender Schlüssel, um Quantenberechnungen zu beschleunigen, sind neuartige Quantenalgorithmen. Ohne deutliche Verbesserungen der Algorithmen ist es unwahrscheinlich, dass selbst einige der oft zitierten Anwendungen in der Praxis wirklich zu einem Quantenvorteil führen. Aus praktischer Sicht ermöglichen die meisten der heute verfügbaren Quantenalgorithmen keine echten Beschleunigung des Quantenrechnens. Selbst wenn wir wissen, dass kubische, quartische oder exponentielle Algorithmen das Quantenrechnen stärker beschleunigen als quadratische Algorithmen, ist die reale Situation immer noch so, dass wir bis heute nicht sehr viele solcher Beschleunigungs-Algorithmen kennen.
Gegenwärtig basieren viele Quantenbeschleunigungs-Algorithmen auf quadratischer «Quantenbeschleunigung», die auf dem bekannten Grover-Algorithmus aufbauen. Wir argumentieren, dass es nicht ausreicht, mehr Algorithmen im Stil von Grover zu entwickeln. Um neue Quantenalgorithmen zu entwickeln, die wirklich eine Rechenbeschleunigung bewirken, muss sich die Forschung auf Algorithmen konzentrieren, die in der Praxis tatsächlich ein schnelleres  Quantenrechnen möglich machen. Andernfalls könnten Quantencomputer die schnellsten klassischer Computer nicht übertreffen.

Was wird von den Informatiker:Innen verlangt, um Quantenberechnungen wirklich zu beschleunigen?
Torsten Hoefler: Wir müssen neuartige Hochgeschwindigkeits-Quantenalgorithmen erfinden. Die große Herausforderung besteht darin, dass wir derzeit nur etwa eine Handvoll grundlegender Quantenalgorithmen haben, wie den Grover-Algorithmus oder den Shor-Algorithmus, die in der Chemie oder Kryptografie weit verbreitet sind. Es ist sehr schwierig, neue grundlegende Algorithmen zu entwickeln. Da die Quantenmechanik ein komplexes mathematisches Konzept ist, ist es ein ziemliches Unterfangen zu verstehen, wie man dieses in nützliche Quantenalgorithmen übertragen kann. Als Faustregel gilt, dass etwa ein grundlegender Algorithmus pro Jahrzehnt entwickelt wird.

Was sind die nächsten Schritte in der Entwicklung von Quantenalgorithmen, namentlich an der ETH Zürich?
Torsten Hoefler: Wir brauchen mehr Informatiker:innen und Mathematiker:innen, um neue Quantenalgorithmen zu erforschen. Bislang ist es sehr schwierig, exzellente Wissenschaftler:innen für Quantenalgorithmen zu finden. Eine grosse Chance besteht darin, diesen Bedarf mit dem Lehrauftrag der ETH Zürich zu verbinden und die nächste Generation von Wissenschaftlern zu ermutigen, sich mit dem Design von Quantenalgorithmen zu beschäftigen. Mit dem Quantum Center können wir Mathematiker:innen, Informatiker:innen, Physiker:innen und Ingenieur:innen zusammenbringen, um gemeinsam an Quantencomputern zu arbeiten. Das ist die Chance für die ETH.