Es ist ein populäres Missverständnis, dass sowohl das Potenzial als auch die Grenzen des Quantencomputing von der Hardware abhängen. Im digitalen Zeitalter haben wir uns daran gewöhnt, Fortschritt an Taktraten und Speicherkapazitäten festzumachen. Und die jetzt online gehenden 50-Qubit-Quantenrechner von Intel, IBM und anderen Firmen haben zu der Vorhersage geführt, wir würden uns der Quantenüberlegenheit nähern – jener nebulösen Grenze, hinter der Quantencomputer Dinge schaffen, die jenseits der Fähigkeiten klassischer Maschinen liegen.

Doch die angestrebte Quantenüberlegenheit ist kein singulärer, durchschlagender Sieg, sondern eher eine langwierige Reihe kleinerer Duelle. Problem für Problem gibt es einen Wettstreit zwischen Quantenalgorithmen und klassischen Algorithmen. »Bei Quantencomputern lässt sich Fortschritt nicht allein an der Geschwindigkeit festmachen«, sagt der Quantentheoretiker Michael Bremner von der University of Technology im australischen Sydney. »Es geht vielmehr um die Komplexität der verwendeten Algorithmen.«

Paradoxerweise erweisen sich Berichte über leistungsfähige Quantencomputer als motivierend für die Verbesserung klassischer Rechner – und machen es so noch schwerer für die Quantenmaschinen, einen Vorsprung zu erringen. »Wenn die Leute über Quantencomputer reden, werden klassische Computer zumeist als überholt abgetan«, erklärt der Mathematiker und Informatiker Cristian Calude von der University of Auckland in Neuseeland. »Doch das trifft keineswegs zu. Es ist ein Wettkampf, der immer noch nicht entschieden ist.«

Ein Wettkampf zudem, bei dem sich die Bedingungen ständig verändern. »Die Antwort auf die Frage, an welchem Punkt die Quantenüberlegenheit erreicht ist, hängt davon ab, wie gut die besten klassischen Algorithmen sind«, erläutert der theoretische Physiker John Preskill vom California Institute of Technology. »Wenn diese besser werden, verschiebt sich auch jener Punkt.«

Alles zu berechnen, was im physikalischen Universum berechenbar ist

Bevor in den 1980er Jahren die Träume von Quantencomputern Form annahmen, gingen die meisten Informatiker davon aus, dass es ausschließlich klassische Computer geben würde. Die Pioniere dieses Forschungsgebiets hatten überzeugend dargelegt, dass klassische Computer – verkörpert durch die mathematische Abstraktion der Turing-Maschine – in der Lage sein sollten, alles zu berechnen, was im physikalischen Universum überhaupt berechenbar war – von grundlegender Arithmetik über den Aktienmarkt bis zur Kollision Schwarzer Löcher.

Allerdings könnten klassische Maschinen nicht alle diese Berechnungen effizient durchführen. Nehmen wir an, wir wollen das chemische Verhalten eines Moleküls verstehen. Dieses chemische Verhalten hängt seinerseits vom Verhalten der Elektronen in dem Molekül ab, die sich in Superpositionen vieler klassischer Zustände befinden. Schlimmer noch: Der Quantenzustand jedes einzelnen Elektrons hängt vom Zustand aller anderen Elektronen ab – über ein als Verschränkung bezeichnetes quantenmechanisches Phänomen. Die klassische Berechnung dieser verschränkten Zustände ist selbst bei sehr einfachen Molekülen ein Alptraum mit exponentiell anwachsender Komplexität.

Im Gegensatz dazu kann ein Quantencomputer die miteinander verflochtenen Schicksale der Elektronen analysieren, indem er seine eigenen Quantenbits in superponierte und verschränkte Zustände bringt. Das ermöglicht es einem Quantencomputer, ungewöhnlich große Informationsmengen zu verarbeiten. Jedes hinzugefügte Qubit verdoppelt die Zahl der Zustände, die das System simultan speichern kann: Zwei Qubits können 4, drei Qubits 8, vier Qubits 16 Zustände speichern, und so weiter.

»Die Natur ist nicht klassisch, verdammt, und wenn man die Natur simulieren will, muss man es deshalb quantenmechanisch machen«Richard Feynman

Deshalb würden 50 Qubits ausreichen, um Quantenzustände zu modellieren, für die 1,125 Billiarden klassische Bits nötig wären. Für eine Quantenmaschine wäre also die klassisch undurchführbare Simulation eines großen, quantenmechanischen Systems durchführbar – so schien es jedenfalls. »Die Natur ist nicht klassisch, verdammt, und wenn man die Natur simulieren will, muss man es deshalb quantenmechanisch machen«, so ein berühmter Ausspruch des Physikers Richard Feynman aus dem Jahr 1981. »Und zum Donnerwetter, es ist ein wundervolles Problem, denn es sieht keineswegs einfach aus.« Und das war es natürlich tatsächlich nicht.

Noch bevor irgendjemand anfing, an Quantenhardware zu basteln, mühten sich Theoretiker bereits ab, brauchbare Software für Quantenrechner zu entwickeln. Schon früh zeigten Feynman und David Deutsch, Physiker an der University of Oxford, dass sich Quanteninformation mit Hilfe mathematischer Operationen kontrollieren lässt, die der linearen Algebra entstammen: den Logikgattern. Analog zu klassischen Gattern manipulieren Quantengatter Qubits auf alle möglichen Arten – sie leiten sie durch eine Abfolge von Superpositionen und Verschränkungen und messen am Ende ihren Output. Indem sie Gatter zusammenfügten und vermischten, konnten Theoretiker leicht Quantenalgorithmen entwickeln.

Doch Quantenalgorithmen zu konzipieren, die klare Vorteile bei Berechnungen bieten, erwies sich als schwieriger. Bis Anfang der 2000er Jahre hatten Mathematiker eine Reihe guter Kandidaten präsentiert. Am bekanntesten ist der 1994 von Peter Shor, einem jungen Mitarbeiter der Bell Laboratories, vorgeschlagene Quantenalgorithmus, der ganze Zahlen exponentiell schneller faktorisiert als jeder bekannte klassische Algorithmus. Mit dieser Effizienz ließen sich viele populäre Verschlüsselungsmethoden knacken. Zwei Jahre später entwarf Shors Kollege Lov Grover einen Algorithmus, der klassisch mühsame Suchprozesse in unsortierten Datenbanken erheblich beschleunigte. »Es gab eine Menge Beispiele dafür, dass Quantencomputer klassischen Rechnern überlegen sein sollten«, berichtet der Quanteninformatiker Richard Jozsa von der University of Cambridge.

Schöne Quantenprozesse sind kompliziert

Doch Jozsa und andere Forscher stießen auch auf viele Beispiele dafür, dass es umgekehrt sein könnte. »Es zeigte sich, dass viele schöne Quantenprozesse zwar aussehen, als ob sie kompliziert wären« – und deshalb nur schwer auf klassischen Computern zu simulieren sind, sagt Jozsa. »Aber mit geschickten, raffinierten mathematischen Methoden lässt sich herausfinden, was diese Prozesse machen.« Jozsa und seinen Kollegen gelang es mit diesen Verfahren, eine überraschend große Anzahl von Quantenschaltkreisen effizient zu simulieren – oder zu »dequantisieren«, wie Calude es ausdrücken würde. Das gilt beispielsweise für Schaltkreise, die ohne Verschränkung arbeiten und für solche, die nur eine begrenzte Anzahl ihrer Qubits verschränken oder nur bestimmte Arten von Gattern zur Verschränkung nutzen.

Was ist dann aber der Grund dafür, dass der Algorithmus von Shor so einzigartig leistungsstark ist? »Das ist immer noch eine offene Frage«, gesteht Jozsa. »Wir konnten bislang nicht herausfinden, warum einige Algorithmen sich leicht klassisch simulieren lassen, andere nicht. Offensichtlich ist Verschränkung wichtig, aber das ist nicht alles.« Und einige Experten warfen die Frage auf, ob nicht viele der vermeintlich überlegenen Quantenalgorithmen in Wahrheit ganz gewöhnlich sein könnten.

Noch bis vor Kurzem war das Streben nach höherer Leistungsfähigkeit bei Quantenalgorithmen eher abstrakter Natur. »Wir haben uns keine großen Gedanken über die Implementierung unserer Algorithmen gemacht, weil niemand ernsthaft daran geglaubt hat, dass wir in der vorhersehbaren Zukunft einen Quantencomputer zur Verfügung hätten«, urteilt Jozsa. Um Shors Algorithmus auf ganze Zahlen anzuwenden, die groß genug sind, um eine 128-Bit-Verschlüsselung zu knacken, wären Tausende von Qubits nötig – sowie vermutlich viele tausend weitere für die Fehlerkorrektur. Dabei hatten die Experimentatoren immer noch genug damit zu tun, auch nur eine Hand voll Qubits unter Kontrolle zu bringen.

Ringen um die richtige Stichprobe

Doch im Jahr 2011 begann sich die Lage zu ändern. Im Herbst spekulierte Preskill auf einer Tagung in Brüssel, dass »der Tag, an dem ein gut kontrolliertes Quantensystem Aufgaben erfüllen kann, die die Möglichkeiten klassischer Systeme übertreffen«, nicht mehr allzu fern sei. Jüngste Laborergebnisse, so der Forscher weiter, könnten schon bald zu Quantenmaschinen mit etwa 100 Qubits führen. Und mit diesen eine »überklassische« Aufgabe durchzuführen, wäre nicht undenkbar. Andererseits: Obwohl der kommerzielle Quantenprozessor von D-Wave Systems damals 128 Qubits umfasste und heute sogar mit über 2000 Qubits arbeitet, nimmt er nur sehr spezielle Optimierungsprobleme in Angriff. Viele Experten bezweifeln, dass sich damit klassische Computer übertreffen lassen.

»Ich habe lediglich versucht hervorzuheben, dass wir nahe dran sind – dass wir schon bald tatsächlich jenen Meilenstein der menschlichen Zivilisation erreichen könnten, ab dem die Quantentechnologie die leistungsstärkste Informationstechnologie ist, die wir zur Verfügung haben«, erläutert Preskill seine Absicht. Er taufte diesen Meilenstein »Quantenüberlegenheit« (engl.: quantum supremacy). Diese Bezeichnung – und sein Optimismus – blieben haften. »Es entwickelte einen von mir nicht erwarteten Schwung.«

Die Aufregung um die Quantenüberlegenheit spiegelte die wachsende Begeisterung wider, die in dem Forschungsgebiet herrschte – über den experimentellen Fortschritt, aber mehr noch über eine ganze Reihe theoretischer Durchbrüche. Den ersten davon präsentierten 2004 die IBM-Physiker Barbara Terhal und David DiVincenzo. Bei ihrem Versuch, die Vorteile von Quantenrechnern zu verstehen, hatte sich das Forscherduo mit einer Klasse einfacher Quantenrätsel befasst, die als Stichprobenprobleme oder geläufiger mit dem englischen Begriff »Sampling-Problems« bezeichnet werden. Mit der Zeit wurden diese Probleme zur größten Hoffnung der Experimentatoren: Mit Hilfe solcher Rechnungen hofften sie, zweifelsfrei die Überlegenheit der Quantenmaschinen zu demonstrieren.

Flüchtige Natur der Quanten schafft Probleme

Sampling-Problems basieren auf der flüchtigen Natur von Quanteninformationen. Nehmen wir einmal an, wir wenden eine Reihe von Gattern auf 100 Qubits an. Ein solcher Schaltkreis wandelt die Qubits in ein mathematisches Monstrum um, das etwa 2 hoch 100 klassischen Bits entspricht. Doch wenn wir dieses System messen, kollabiert seine Komplexität zu einer Folge von nur noch 100 Bits. Das System spuckt also eine einzige Bitfolge aus – eine einzige Stichprobe, deren Wahrscheinlichkeit von der genauen Beschaffenheit des Schaltkreises abhängt.

Bei einem Sampling-Problem geht es darum, eine Reihe von Stichproben zu produzieren, die so aussehen, als kämen sie von diesem Schaltkreis. Es ist ähnlich wie beim Werfen einer Münze: Im Durchschnitt erhält man zu 50 Prozent Kopf und zu 50 Prozent Zahl. Nur dass wir bei einem Quantensystem bei jedem »Wurf« nicht einen einzigen Wert, sondern eine ganze Reihe von Werten erhalten und jeder dieser Werte von einigen (oder gar allen) anderen Werten beeinflusst wird.

Für einen gut funktionierenden Quantencomputer ist das ein Klacks – es ist genau das, was seiner Natur entspricht. Klassische Computer tun sich damit jedoch schwer. Im schlimmsten Fall müssen sie die Wahrscheinlichkeiten für alle möglichen Ausgabe-Bitfolgen – alle 2 hoch 100! – berechnen und dann zufällige Stichproben aus dieser Verteilung wählen. »Die Leute sind immer davon ausgegangen, dass das so ist«, insbesondere für sehr komplexe Quantenschaltkreise, betont Ashley Montanaro, Experte für Quantenalgorithmen an der University of Bristol.

Terhal und DiVincenzo zeigten, dass es selbst für einige einfache Quantenschaltkreise schwierig ist, mit klassischen Mitteln Stichproben zu erzeugen. Damit hatten sie die Messlatte hoch gelegt: Wenn Experimentatoren ein Quantensystem dazu bringen konnten, diese Stichproben auszuspucken, dann gäbe es gute Gründe anzunehmen, dass sich das mit einem klassischen Rechner nicht erreichen ließe.

Was lässt sich mit einem klassischen Rechner nicht erreichen?

Theoretiker erweiterten diesen Ansatz rasch auf andere Arten von Sampling-Problems. Eine der vielversprechendsten Ideen kam von Scott Aaronson, einem Informatiker am Massachusetts Institute of Technology und seinem Doktoranden Alex Arkhipov. Auf ArXiv, einem Server für wissenschaftliche Vorabveröffentlichungen, beschrieben sie 2010 eine Quantenmaschine, in der Photonen durch einen optischen Schaltkreis geschickt werden, der die Lichtteilchen quantenmechanisch manipuliert und so als Ausgabe Photonen mit einer spezifischer Wahrscheinlichkeitsverteilung liefert.

Die Reproduktion dieses Musters bezeichnen Forscher als »Bosonen-Sampling« (Stichprobe der Bosonenverteilung; Photonen sind Bosonen). Aaronson und Arkhipov argumentierten, solche Bosonen-Stichproben würden klassische Methoden bereits bei etwa 30 Photonen überfordern – ein plausibles experimentelles Ziel.

Ähnlich verlockend für die Forscher waren als instantane quantenpolynomische Schaltkreise (instantaneous quantum polynomial circuits) bezeichnete Berechnungen. Ein solcher IQP-Schaltkreis besteht ausschließlich aus Gattern, die kommutieren, die also in jeder beliebigen Reihenfolge angewendet werden können, ohne dass sich das Ergebnis ändert – ähnlich, wie 2 + 5 dasselbe Ergebnis liefert wie 5 + 2. Diese Eigenschaft macht IQP-Schaltkreise mathematisch angenehm. »Wir haben damit angefangen, solche Schaltkreise zu untersuchen, weil sie einfacher zu analysieren sind«, gesteht Bremner. Doch er stieß auf weitere Vorteile der IQP-Schaltkreise. Seine im Jahr 2010 angefangenen Arbeiten, die 2016 in einer gemeinsamen Veröffentlichung mit Montanaro und Dan Shepard, der jetzt am britischen National Cyber Security Center beschäftigt ist, gipfelten, lieferten eine Erklärung dafür, warum IQP-Schaltkreise extrem leistungsfähig sein können: Selbst für physikalisch realistische Systeme von Hunderten – oder gar nur Dutzenden – von Qubits würde eine Stichprobenentnahme schnell zu einem sehr schwierigen Problem für klassische Systeme werden.

Plan für die Erreichung der Quantenüberlegenheit

2016 war das Bosonen-Sampling immer noch nicht über sechs Photonen hinausgekommen. Forscherteams von Google und IBM werkelten dagegen bereits an Chips mit fast 50 Qubits. Und im August 2016 veröffentlichte Google ohne viel Aufsehen ein Konzeptpapier, das einen Plan für die Erreichung der Quantenüberlegenheit mit Hilfe »in Kürze« realisierbarer Maschinen enthielt.

»Wir nagen nur an der Grenze, wir sprengen sie nicht«John Preskill

Das Google-Team hatte eine Erzeugung von Stichproben mit Hilfe eines IQP-Schaltkreises in Betracht gezogen. Doch eine genauere Betrachtung führte Bremner und seine Kollegen zu der Schussfolgerung, dass ein solcher Schaltkreis vermutlich eine Fehlerkorrektur benötigen würde – und damit zusätzliche Gatter und mindestens ein paar hundert weiterer Qubits. Nur so könnte er eindeutig die besten klassischen Algorithmen übertreffen. Deshalb zeigte das Team mit Argumenten ähnlich jenen von Aaronson und Bremner, dass Schaltkreise aus nichtkommutierenden Gattern, obwohl schwerer zu bauen und zu analysieren wie IQP-Schaltkreise, zugleich für klassische Schaltkreise schwerer zu simulieren wären. Um die klassischen Berechnungen zu einer noch größeren Herausforderung zu machen, schlug das Team vor, Stichproben mit einem zufällig gewählten Schaltkreis zu erzeugen. Auf diese Weise wäre es für einen klassischen Konkurrenzalgorithmus nicht möglich, vertraute Eigenschaften der Schaltkreisstruktur zu nutzen, um dessen Verhalten besser vorherzusagen.

Doch nichts stoppte die klassischen Algorithmen darin, immer einfallsreicher zu werden. So zeigte im Oktober 2017 ein IBM-Team, wie mit ein wenig klassischer Erfindungsgabe ein Supercomputer Stichproben aus zufälligen Schaltkreisen mit bis zu 56 Qubits simulieren kann – jedenfalls, solange die Schaltkreise nicht übermäßig tief sind, also nicht zu viele Schichten von Gattern aufweisen. Und ein noch fähigerer Algorithmus hat die klassische Grenze für das Bosonen-Sampling auf etwa 50 Photonen heraufgesetzt.

Zwei Tage Rechenzeit versus eine Zehntelmillisekunde

Diese Verbesserungen sind jedoch immer noch furchtbar ineffizient. Die IBM-Simulation benötigte beispielsweise zwei Tage Rechenzeit – doch ein Quantencomputer hätte, so die Erwartung, dafür lediglich eine Zehntelmillisekunde gebraucht. Fügt man ein paar weitere Qubits hinzu – oder etwas mehr Schaltungstiefe –, so erreichen Quantenrechner das Reich der Quantenüberlegenheit. »Allgemein formuliert: Wenn man hochgradig verschränkte Systeme emulieren will, dann gibt es keinen klassischen Durchbruch, der die Spielregeln wirklich geändert hätte«, sagt Preskill. »Wir nagen nur an der Grenze, wir sprengen sie nicht.«

Das bedeutet nicht, dass es einen klaren Sieger geben wird. »Die Leute werden weiter darüber streiten, wo die Grenze liegt«, schätzt Bremner die Situation ein. Stellen wir uns folgendes Szenario vor: Forscher nehmen Stichproben von einem 50-Quibit-Schaltkreis einer bestimmten Tiefe – oder einem etwas größeren mit weniger Tiefe – und erklären, sie hätten die Quantenüberlegenheit erreicht.

»Die erste Welle von Problemen, die wir lösen werden, sind solche, bei denen uns die Antworten eigentlich egal sind«Ashley Montanaro

Doch der Schaltkreis rauscht stark – die Qubits verhalten sich schlecht oder die Gatter arbeiten nicht zuverlässig. Prompt kommen ein paar begabte klassische Theoretiker und simulieren den Quantenschaltkreis ohne große Anstrengung, denn »mit Rauschen werden Dinge, von denen du denkst, sie sind schwer, aus klassischer Sicht nicht mehr so schwer«, erklärt Bremner. »Das ist, was vielleicht passieren wird.«

Was sicherlich passieren wird, ist, dass die ersten »überlegenen« Quantenmaschinen, wann immer es sie gibt, keineswegs Verschlüsselungen knacken oder neue pharmazeutische Moleküle simulieren werden. »Das ist das Komische an der Überlegenheit«, sagt Montanaro. »Die erste Welle von Problemen, die wir lösen werden sind solche, bei denen uns die Antworten eigentlich egal sind.«

Doch diese ersten Siege, egal wie klein sie sind, werden den Forschern zeigen, dass sie auf dem richtigen Weg sind – dass tatsächlich eine neue Art von Rechnung möglich ist. Und bislang kann niemand auch nur erahnen, was die nächste Welle von Problemen sein wird, die dann von Quantencomputern gelöst werden.

Der Text ist im Original am 1. Februar 2018 unter dem Titel »Quantum Algorithms Struggle Against Old Foe: Clever Computers« im »Quanta Magazine« erschienen.