«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.