Für manche Aufgaben braucht ein Computer nur einen Augenblick, für andere eine Ewigkeit. Genau diesen Unterschied versucht die Komplexitätstheorie zu verstehen: Sie gibt ein Maß dafür an, wie kompliziert ein Problem grundsätzlich ist.

Doch das Feld verändert sich. Mit dem Aufkommen von Quantencomputern ist eine völlig neue Art von Maschine entstanden: Rechner, die nicht mehr mit klassischen Informationseinheiten arbeiten, die entweder einer Null oder einer Eins entsprechen, sondern mit quantenmechanischen Mischungen beider Zustände. Bei bestimmten Aufgaben, etwa der Zerlegung großer Zahlen in ihre Primteiler, sind Quantencomputer den klassischen Rechnern deutlich überlegen.

Die Komplexitätstheorie hat diese Vorteile in den letzten Jahrzehnten vermessen. Doch jenseits dessen öffnet sich ein kaum erforschtes Gebiet: Probleme, bei denen auch die Ein- und Ausgaben der Maschinen quantenmechanisch sind, also beispielsweise aus überlagerten Zuständen bestehen.

Genau dort setzt der Komplexitätstheoretiker Henry Yuen an. Er möchte herausfinden, wie man die Schwierigkeit eines Problems bestimmt, wenn schon die Daten quantenhaft sind. »Die traditionelle Komplexitätstheorie sagt dazu nichts«, stellt Yuen fest. »Vielleicht brauchen wir eine separate Theorie, um diese andere Klasse von Problemen zu verstehen.« Yuen ist Professor an der Columbia University; im Jahr 2020 war er Mitautor eines viel beachteten Beweises in der Komplexitätstheorie. Inzwischen führt er ein ambitioniertes Projekt an: den Aufbau einer vollständig quantenmechanischen Theorie, welche die Komplexität von Problemen mit quantenhaften Ein- und Ausgaben erfassen soll.

Seine Biografie passt erstaunlich gut zu dieser Suche nach einem unkonventionellen Ansatz. 1989 geboren, verbrachte Yuen einen Großteil seiner Jugend im Restaurant seiner Familie im Süden Kaliforniens. Er fand nur über Umwege zur Wissenschaft: Programmieren lernte er, weil er Videospiele entwickeln wollte. Doch im Studium zog ihn die theoretische Seite des Fachs an – insbesondere die Frage, wie Quantencomputer Informationen verarbeiten. Sie wurde zum Ausgangspunkt seiner heutigen Forschung.

Herr Yuen, Ihr familiärer Hintergrund ist für eine wissenschaftliche Laufbahn nicht gerade typisch. Wie sind Ihre Eltern in die USA gekommen?

Meine Eltern wuchsen in den 1970er-Jahren in Kambodscha auf, als die Roten Khmer das Land übernahmen und Millionen Menschen in Arbeitslager zwangen. Die Familie meiner Mutter wurde in diese Lager verschleppt und leistete drei oder vier Jahre Zwangsarbeit, bevor ihr die Flucht gelang. Meine Verwandten verbrachten Monate damit, Berge und Felder zu überqueren, die mit Landminen übersät waren. Die Familie meines Vaters hatte etwas mehr Glück: Sie erkannte die Vorzeichen der damaligen Situation und floh früher aus dem Land. Schließlich gelangten beide Familien in die USA. Meine Mutter und mein Vater betrieben ein Restaurant, in dem mein Bruder und ich arbeiteten, bis wir unser Studium begannen.

Die Geschichten meiner Eltern als Kind zu hören, hat mich natürlich stark geprägt. Ich habe das Privileg, über Mathematik und Quantenphysik nachzudenken und mit anderen zusammenzuarbeiten, die sich für diese extrem nischigen und unfassbar obskuren Themen interessieren. Das ist enorm weit von dem entfernt, was meine Eltern durchmachen mussten.

Wie sind Sie zu diesen »nischigen Themen« gekommen?

Als ich aufs College ging, wollte ich Physik und Informatik studieren. Physik fand ich konzeptionell interessant, und Informatik gefiel mir wegen meines Interesses an Videospielen. Ich habe die Physik aber recht schnell aufgegeben, weil ich in den Laborpraktika miserabel war. 2007 oder 2008 entdeckte ich dann Scott Aaronsons Blog, in dem er über Quantencomputing und theoretische Informatik schreibt. Ich dachte: »Das ist großartig. Das will ich studieren.« Aber die wohl prägendste Erfahrung war die Forschungsarbeit bei meinem Professor Len Adleman. Sein Mantra war: »Wir ignorieren alles, was die Leute seit 100 Jahren getan haben. Wir biegen links ab, wo alle rechts abgebogen sind.« Es fühlte sich an, als wären wir Außenseiter, die etwas Rebellisches tun.

Seit Jahrzehnten haben Komplexitätsforscher die Leistungsfähigkeit von Quantencomputern untersucht. Was haben sie dabei übersehen?

In der traditionellen Komplexitätstheorie sind die Ein- und Ausgaben eines Computers stets klassisch. Was dazwischen mit den Daten passiert, spielt keine Rolle. Man kann versuchen, das Problem mit einem klassischen Computer zu lösen, oder auch einen Quantencomputer einsetzen. Aber wir haben uns gefragt, warum die Eingaben und Ausgaben überhaupt klassisch sein sollten.

Was wäre denn ein Beispiel für so ein Problem?

In der Kryptografie gibt es etwa ein Verfahren namens Bit-Commitment. Das ist, als würde man eine Nachricht in einen versiegelten Umschlag stecken. Dadurch bleibt sie bis zur Offenlegung geheim. Zugleich stellt man dadurch sicher, dass die Nachricht nicht verändert wird. Mit Bit-Commitment werden etwa Gebote bei einer Auktion oder Stimmen bei einer geheimen Wahl abgegeben.

Etliche kryptografische Verfahren beruhen auf dem klassischen Bit-Commitment. Und dieses fußt wiederum auf der Annahme, dass bestimmte mathematische Probleme schwer zu lösen sind – sie sichern gewissermaßen den Umschlag. Wenn es aber eine Möglichkeit gäbe, diese notorisch schweren Probleme zu lösen, dann ließe sich jedes Bit-Commitment-Verfahren brechen. Und damit auch jede andere Anwendung, die darauf basiert.

Das ist der klassische Fall.

Und jetzt stellen Sie sich ein Quanten-Bit-Commitment vor, bei dem die Umschläge Quantenobjekte sind. In diesem Fall ist völlig unklar, ob eine Lösung des klassischen Bit-Commitments auch die entsprechenden Quantenumschläge entsiegeln kann.

Weil das Bit-Commitment-Verfahren jetzt ein Problem mit quantenmechanischen Eingaben ist?

Genau. Das Problem ist nun weniger mathematisch und mehr physikalisch. Eine exorbitante klassische Rechenleistung, die das klassische Bit-Commitment knacken würde, bringt nicht notwendigerweise die Fähigkeit mit sich, auch ein quantenphysikalisches Problem zu lösen. Diese beiden Arten von Rechenaufgaben könnten grundlegend verschieden sein. Meiner Meinung nach ist das größte offene Problem der Komplexitätstheorie: Wir müssen herausfinden, wie diese beiden Welten zusammenhängen.

Was meinen Sie damit?

Nehmen wir an, wir wüssten alles, was es über die traditionelle Komplexitätstheorie zu wissen gibt. Würde uns das automatisch alles über eine quantenmechanische Komplexitätstheorie verraten? Vielleicht ließe sich unser Verständnis einfach übertragen. Es ist aber ebenso möglich, dass die quantenmechanische Komplexitätstheorie nichts mit der traditionellen Komplexität zu tun hat.

Diese Fragestellung lässt sich auch in anderer Form ausdrücken. Wenn ich Zugang zu einem unendlich mächtigen klassischen Orakel hätte – einem fiktiven Gerät, das jedes Problem mit klassischen Eingaben sofort löst –, könnte ich es dann nutzen, um jede beliebige Transformation eines Quantenzustands meiner Wahl durchzuführen? Wenn die Antwort nein ist, dann sind diese Probleme mit quantenhaften Ein- und Ausgaben von grundlegend anderer Natur als klassische. Diese Frage ist nach wie vor offen.

Sie haben erste Schritte zu einer neuen Komplexitätstheorie gemacht. Was haben Sie bisher herausgefunden?

Meine Mitarbeitenden und ich kartieren seit ein paar Jahren, wie diese neue Welt von Quantenproblemen aussieht und wie sie zusammenhängt. Dabei ist uns aufgefallen, dass ein Problem immer wieder in vielen unterschiedlichen Kontexten auftauchte.

Welches?

Es geht von einem sehr grundlegenden Resultat der Quanteninformationstheorie aus, dem sogenannten Uhlmann-Theorem, das in der Quantenkommunikation, der Quantenkomplexität, der Quantenkryptografie und darüber hinaus eine sehr wichtige Rolle spielt.

Es lautet so: Angenommen, Sie haben zwei Quantenteilchen, die miteinander verschränkt sind. Sie teilen sich also einen gemeinsamen Quantenzustand, der in diesem Fall nur aus zwei möglichen Zuständen besteht. Laut Quantenmechanik lassen sich gewisse Operationen auf beiden Teilchen durchführen, die den ersten Zustand in den zweiten überführen. Aber was, wenn Sie nur an einem der Teilchen operieren dürfen: Können Sie den ersten Zustand dann trotzdem in den zweiten verwandeln? Und falls nicht: Wie nahe können Sie dem zweiten Zustand kommen? Das Uhlmann-Theorem gibt genau an, was man für ein Paar verschränkter Zustände im besten Fall erreichen kann.

Und dieses Theorem ist eine Quantenaufgabe, die Sie mit Ihrer neuen Theorie untersuchen?

Ja, wir haben das Theorem als Problem mit quantenhaften Ein- und Ausgaben aufgefasst. Es hat als Ziel, einen Zustand in den anderen zu transformieren, wobei man nur lokal auf einem der Teilchen agieren darf. Nun stellt sich die Frage, wie komplex diese Aufgabe ist. Welche Ressourcen sind nötig, um sie zu lösen? Wir konnten zeigen, dass tatsächlich eine ganze Reihe von Quantenproblemen gleich komplex sind.

»Wir wissen nicht einmal unbedingt, was die richtigen Fragen sind«

Zum Beispiel?

Eines besteht etwa darin, die Hawking-Strahlung eines Schwarzen Lochs zu decodieren. Das ist ein Problem mit quantenhaften Eingaben, weil man all diese verschränkten Teilchen untersuchen muss. Und wie sich herausstellt, handelt es sich dabei um das Uhlmann-Problem in anderer Form.

Das Uhlmann-Problem scheint der Knotenpunkt für all die anderen Quantenaufgaben zu sein: Bit-Commitments, das Decodieren Schwarzer Löcher, das Komprimieren von Quanteninformation und mehr.

Damit haben Sie schon erstaunliche Erkenntnisse gewonnen.

Ja, und ich muss sagen, diese Arbeit ist eine ganz andere Übung als das, was ich sonst in der Forschung gewohnt bin. Niemand drückt mir einen Satz in die Hand und sagt: »Hier, beweise ihn!« Wir wissen nicht einmal unbedingt, was die richtigen Fragen sind. Eine neue Theorie zu entwickeln, ist wie eine richtige Sprache zu finden. Und das ist wirklich wichtig – selbst wenn man nichts wirklich Technisches beweist. Denn wenn man nicht die richtige Sprache spricht, lässt sich nicht klar denken.