Es ist eine der großen Fragen der Informatik: Können Computer jedes Problem in vertretbarer Zeit prüfen? Ja, sagt ein neuer Fachaufsatz – und löst damit große Begeisterung aus.
Mit P und NP fängt der Spaß erst an: Computerwissenschaftler haben mittlerweile eine Hierarchie von Komplexitätsklassen erstellt, von sehr einfachen hin zu extrem anspruchsvollen. Eine Wendung hat der Quantencomputer gebracht: Er ermöglicht neue Strategien, wenn es darum geht, die vorgegebene Lösung für ein Problem auf ihre Korrektheit zu überprüfen.
Die lange Geschichte der Komplexitätsklassen
Allerdings ist der Beweisführer nicht vertrauenswürdig, weshalb man zusätzlich einen Prüfer braucht, der das gelieferte Ergebnis nachrechnet. Beim Sudoku wäre er es, der sicherstellt, dass eine Lösung korrekt ist. Der Prüfer ist – anders als der Beweisführer – ein realistischer Computer, der begrenzte Ressourcen hat. Das heißt, seine Berechnungsdauer darf bloß polynomial von der Größe der Aufgabe abhängen.
Verhör mehrerer Verdächtiger
Nach diesem Ergebnis ruhte das Gebiet der interaktiven Beweissysteme erst einmal. Zumindest bis sich einige Forscher fragten, was passieren würde, wenn die beiden Beweisführer keine klassischen Computer wären, sondern Quantencomputer, die per Quantenphysik aneinander gekoppelt sind. Möglich macht es das Phänomen der Verschränkung, über das sich schon Albert Einstein den Kopf zerbrochen hat.
Er nannte es «spukhafte Fernwirkung», denn wenn man den Zustand eines von zwei verschränkten Objekten misst, legt man auch den Zustand des anderen fest – unabhängig davon, wie weit die beiden voneinander entfernt sind. Anfangs bereitete dieser Umstand Physikern Bauchschmerzen, doch inzwischen weiß man, dass sich auf diese Weise keine Information transportieren lässt.
Zu Beginn schenkten Komplexitätsforscher der Möglichkeit von verschränkten Beweisführern nicht viel Aufmerksamkeit, da man davon ausging, dass die dazugehörige Komplexitätsklasse MIP* kleiner wäre als MIP oder gar IP. Schließlich liegt der Vorteil von MIP darin, dass man die allwissenden Computer separat befragt. Wenn sie dagegen verschränkt sind, wirkt sich die Antwort des einen auf den Zustand des anderen aus.
Verschränkte Quantencomputer als Lösung
Doch 2012 kam die erste große Überraschung: Vidick bewies mit seinem Kollegen Tsuyoshi Ito von der University of Waterloo, dass man mit verschränkten Quantencomputern auch alle Probleme aus MIP in polynomialer Zeit überprüfen kann. Demnach sind beide Komplexitätsklassen mindestens gleich groß.
Der Trick besteht darin, durch die Verschränkung geeignete Fragen zu identifizieren. Das heißt, die Beweisführer befragen sich zunächst selbst. Das scheint auf den ersten Blick paradox; weil die zwei Beweisführer aber miteinander verschränkt sind, können sie gleich mehrere Antworten gleichzeitig durchspielen und so mehr denkbare Überprüfungsschritte abhandeln. Diese Fragen übermitteln sie dem Prüfer.
Der muss beim eigentlichen Test dann nur noch garantieren, dass die Fragen repräsentativ und sinnvoll sind und die Antworten zu keinen Widersprüchen führen. Auf diese Weise kann er die Prüfung in angemessener Zeit durchführen; die dafür benötigte Rechenzeit wächst bloß polynomial mit der Länge an.
Wenn man die Geschwindigkeit eines Teilchens gemessen hat und danach seine Position ermittelt, weiß man nicht mehr, wie schnell das Objekt nun ist. Deshalb dürfen die Beweisführer bloß jeweils komplementäre Messungen durchführen, so dass sich ihre Antworten nicht gegenseitig beeinflussen. Befragt man den ersten Quantencomputer nach einem Rechenwert, löscht das die dazugehörige Information des zweiten Quantencomputers.
Unerwartete Wendung für Mathematiker
Anders als häufig angenommen, kann man ein unendliches System nicht immer beliebig genau durch ein endliches annähern
Spektrum der Wissenschaft
Wir sind Partner von Spektrum der Wissenschaft und möchten dir fundierte Informationen besser zugänglich machen. Folge Spektrum der Wissenschaft, falls dir die Artikel gefallen.
Wissenschaftler lieben es, Dinge zu kategorisieren – zumindest auf abstrakter Ebene. Chemiker teilen beispielsweise alle Elemente in das Periodensystem ein. Biologen ordnen die Lebewesen der Erde nach Familien und Arten. Und Mathematiker haben im vergangenen Jahrzehnt, nach langer Suche, alle endlichen einfachen Gruppen gefunden und aufgelistet.
Informatiker suchen ebenfalls nach Ordnung, wenn auch ein wenig anders: Sie sortieren Probleme nach ihrer Komplexität. Bereits in der Vergangenheit haben sie herausgefunden, dass gewisse Aufgaben für Computer sehr einfach zu lösen sind. Bei ihnen wächst die zur Lösung nötige Rechenzeit bloß langsam (polynomial) mit der Länge des Problems an. Aus Sicht von Informatikern gehören solche Rechenaufgaben damit zur Komplexitätsklasse P.
Probleme, die man einfach überprüfen kann, selbst wenn sie schwer zu lösen sind, zählen hingegen zur Klasse NP. Ein Beispiel ist ein anspruchsvolles Sudoku-Rätsel: Bei diesem ist es schwierig, die richtige Lösung zu finden. Hat man sie jedoch einmal ausgetüftelt oder bekommt ein ausgefülltes Blatt präsentiert, lässt sich leicht überprüfen, ob es korrekt ist.
Clique-Problem | Das Clique-Problem beschreibt die Aufgabe, die maximale Anzahl an Knoten innerhalb eines Graphen zu finden, die direkt benachbart sind. Es gehört zur Komplexitätsklasse NP. Die Abbildung zeigt einen Algorithmus zur Lösung des Clique-Problems. In diesem Fall beträgt die Clique-Zahl vier. Quelle: Thore Husfeldt at English Wikipedia [CC BY-SA (https://creativecommons.org/licenses/by-sa/3.0)]
Eine offene Frage der Komplexitätsforschung war dabei stets, wie kompliziert ein Problem höchstens sein darf, damit es ein Computer noch in angemessener – also polynomialer – Zeit überprüfen kann. Ein Team um Zhengfeng Ji von der University of Technology, Sydney, hat nun eine überraschende Antwort gefunden, die derzeit für großes Aufsehen unter Fachleuten sorgt. Demnach lassen sich rein theoretisch selbst die schwierigsten Probleme der Informatik in vertretbarer Zeit angehen.
«Ich kann mich nicht an eine einzige Person erinnern, die das erwartet hätte», schreibt der angesehene Informatiker Scott Aaronson von der University of Austin dazu in seinem Blog. Sollte die Arbeit der Prüfung durch unabhängige Experten standhalten, handle es sich um eine der größten Überraschungen aus der theoretischen Informatik in diesem Jahrhundert.
Seit den 1970er Jahren versuchen Computerwissenschaftler, Komplexitätsklassen immer feiner zu unterteilen. Dazu haben sie immer wieder kompliziertere Probleme als NP identifiziert. Raum für mehr Komplexität bot dabei vor allem die Überprüfung der Lösung. In manchen Fällen wächst die dafür nötige Zeit nicht mehr polynomial mit der Länge der Aufgabe an, sondern etwa exponentiell. Hier ist die Sache also sehr viel schwieriger als bei einem Sudoku-Rätsel, dessen Lösung man vorgesetzt bekommt.
Um auch solche Probleme klassifizieren zu können, führten Informatiker in den 1980er Jahren so genannte interaktive Beweissysteme ein. Sie stellten sich dabei einen allmächtigen Computer vor, den «Beweisführer». Dieser ist stets in der Lage, die Lösung einer Aufgabe zu liefern, unabhängig davon, wie komplex sie ist. Er kann folglich auch Probleme berechnen, die weit komplizierter sind als Sudoku-Rätsel. Dabei verfügt er über unendliche Speicherkapazitäten und kann im Prinzip auch unendlich lange rechnen.
Weil die vom Beweisführer gelieferte Lösung unter Umständen extrem lang und kompliziert ist, stellt ihm der Prüfer verschiedene Fragen und versucht sich so vom Wahrheitsgehalt zu überzeugen. Man denke zum Beispiel an einen Tisch in einem stockfinsteren Zimmer, auf dem mehrere identisch geformte Holzklötze liegen. Die Aufgabe besteht darin, sie nach ihrer Farbe zu sortieren. Der Beweisführer – allmächtig wie er ist – hat kein Problem damit. Trotz Dunkelheit teilt er die Klötze in zwei Stapel auf.
Der Prüfer muss nun durch Fragen herausbekommen, ob zwei beliebig herausgegriffene Klötze von zwei unterschiedlichen Stapeln wirklich verschiedene Farben haben. Der Beweisführer könnte in diesem Fall sagen, dass der eine Klotz rot und der andere blau ist. Aber stimmt das? Oder lügt der Beweisführer? Um das zu klären, kann der Prüfer die Holzklötze hinter seinem Rücken verstecken, sie vertauschen und den Beweisführer fragen, welcher nun der rote sei. Wiederholt man das Experiment oft genug, wird der Beweisführer entweder in rund der Hälfte aller Fälle falschliegen, wenn er gelogen hat, oder immer richtig antworten – sofern er die Wahrheit gesagt hat.
Computerwissenschaftler haben herausgefunden, dass sich die Lösung mancher Aufgaben nur mit einer solchen Frage-Strategie auf ihrer Korrektheit hin überprüfen lässt. Berücksichtigt man diese Probleme, erweitert sich die Komplexitätsklasse NP zu «IP». Es gibt sogar eine Möglichkeit, noch komplexere Probleme anzugehen: Man lässt nicht bloß einen Beweisführer, sondern gleich mehrere zu. Diese dürfen sich austauschen, während sie eine Aufgabe bearbeiten. Doch sobald sie ein Ergebnis liefern und der Prüfer es untersucht, sind sie voneinander getrennt.
Auf diese Weise kann die Aufgabe, die der Prüfer anschließend mit der Frage-Antwort-Strategie beackert, noch komplizierter ausfallen – und trotzdem in polynomialer Zeit überprüft werden. Denn der Prüfer hat es leichter, wenn er zwei oder mehr Instanzen befragen kann: So wie ein Polizeikommissar bei mehreren separaten Verhören größere Chancen hat, Zeugen einer Lüge zu überführen, lassen sich auf diese Weise anspruchsvollere Probleme lösen. Die dazugehörige Komplexitätsklasse «MIP» ist noch größer als IP, wie Informatiker 1988 entdeckten.
«Die natürliche Reaktion von allen, inklusive mir, war, dass man den Beweisführern nun mehr Macht einräumt», erinnerte sich der Computerwissenschaftler Thomas Vidick vom California Institute of Technology, Mitautor der neuen Veröffentlichung, vor einiger Zeit im Quanta Magazine. Schließlich könnten die Beweisführer die Verschränkung nutzen, um beim Verhör durch den Prüfer ihre Antworten abzustimmen.
2019 folgte die nächste Wendung. Die Physiker Anand Natarajan vom California Institute of Technology und John Wright vom Massachusetts Institute of Technology entdeckten, dass die Quantencomputer-Klasse MIP* sogar größer ist als MIP. Demnach muss die Verschränkung kein Nachteil sein, sondern der Prüfer kann sie sogar zu seinem Vorteil nutzen – und so noch komplexere Aufgaben als gedacht gegenchecken.
Diese Strategie der «korrelierten Fragen» führt also dazu, dass man einen Beweis schneller überprüfen kann. Dabei muss man allerdings aufpassen, dass die Antworten der Beweisführer nicht auch verschränkt sind. Denn das käme zwei Verdächtigen gleich, die sich während einer Befragung absprechen. Natarajan und Wright lösten das Problem, indem sie ein weiteres bizarres Konzept aus der Quantenmechanik nutzten: die dem Mikrokosmos innewohnende Unschärfe, der zufolge sich zwei «komplementäre» Eigenschaften eines Objekts, etwa Ort und Impuls, nicht gleichzeitig beliebig genau bestimmen lassen.
Clique-Problem | Das Clique-Problem beschreibt die Aufgabe, die maximale Anzahl an Knoten innerhalb eines Graphen zu finden, die direkt benachbart sind. Es gehört zur Komplexitätsklasse NP. Die Abbildung zeigt einen Algorithmus zur Lösung des Clique-Problems. In diesem Fall beträgt die Clique-Zahl vier. Quelle: Thore Husfeldt at English Wikipedia [CC BY-SA (https://creativecommons.org/licenses/by-sa/3.0)]
Nun wussten Informatiker, dass MIP* die Komplexität von MIP übersteigt. Doch wie groß die Klasse tatsächlich ist, war zunächst unklar. Um wie viel besser lassen sich Lösungen überprüfen, wenn man verschränkte Quantencomputer befragt? Tatsächlich scheint dies die Menge der Aufgaben auf maximale Art und Weise zu vergrößern: Wie Zhengfeng Ji zusammen mit Natarajan, Vidick, Wright und Henry Yuen von der University of Toronto nun in ihrem Aufsehen erregenden Fachaufsatz gezeigt haben, enthält MIP* alle berechenbaren Probleme der Informatik.
Dem Beweis zufolge ist MIP* identisch mit der riesigen Komplexitätsklasse RE. Sie umfasst alle Entscheidungsprobleme (solche, deren Antwort Ja oder Nein lautet), die ein Computer in endlicher Zeit bejahen kann. Darunter fällt unter anderem das berühmte Halteproblem: Dabei geht es darum, zu bestimmen, ob ein Computer bei der Berechnung einer Aufgabe jemals zum Halten kommt – oder für immer weiterrechnet.
Der britische Informatiker Alan Turing bewies zwar 1936, dass es keinen Algorithmus gibt, der das Halteproblem allgemein lösen kann. Das widerspricht allerdings nicht der neuesten Veröffentlichung. Denn die Arbeit von Ji und seinen Kollegen besagt, dass ein gewöhnlicher Prüfer in polynomialer Zeit die Aussage von zwei miteinander verschränkten allwissenden Quantencomputern überprüfen kann, die behaupten, dass ein Computer für eine bestimmte Aufgabe zum Halten kommt.
Das allein ist schon bemerkenswert. Doch das Ergebnis der Computerwissenschaftler wirkt sich auch auf die Mathematik und die Quantenphysik aus. Denn dadurch entpuppt sich das vom Fields-Medaillen-Preisträger Alain Connes formulierte Einbettungsproblem aus den 1970er Jahren als falsch – das hatten viele Wissenschaftler nicht erwartet. Von dieser hängen weitere Hypothesen ab, die folglich ebenso wenig stimmen können.
Das Einbettungsproblem handelt unter anderem von so genannten Operatoralgebren, die zum mathematischen Bereich der Funktionalanalysis gehören, aber auch in der Quantenmechanik auftauchen. Und tatsächlich gibt es eine physikalische Aussage, die äquivalent zum Problem von Connes ist: Alle quantenmechanisch erlaubten Korrelationen lassen sich beliebig gut durch endlich viele verschränkte Qubits annähern. Anders als die meisten Wissenschaftler erwarteten, zeigt das Ergebnis der theoretischen Informatiker, dass diese Behauptung falsch ist.
Das hat drastische Folgen, beispielsweise wenn es um den Unterschied zwischen endlichen und unendlichen Systemen geht. Anders als häufig angenommen, kann man ein unendliches System nicht immer beliebig genau durch ein endliches annähern. Ji und seine Kollegen nennen in ihrer Veröffentlichung ein Beispiel für eine Situation, in der zwei Personen ein Spiel spielen. Wenn beide unendlich stark miteinander verschränkt sind, dann gewinnen sie mit einer Chance von eins; wenn sie dagegen nur endlich verschränkt sind, dann beträgt die Wahrscheinlichkeit höchstens einhalb.
Anders als die von John Bell in den 1960er Jahren formulierten Ungleichungen lässt sich ein solches Spiel aber nicht im Labor überprüfen, denn es besteht keine Möglichkeit, zwei Systeme unendlich miteinander zu verschränken. Doch die Arbeit beweist, dass die Komplexitätstheorie – anders als oft behauptet – kein völlig lebensfernes Gebiet ist, das allein für sich steht, sondern Auswirkungen auf andere Bereiche hat, seien sie auch so abstrakt wie die theoretische Quantenphysik.
