Informatiker erweitern den Umfang des Testwissens

Das Universum computergesteuerter Aufgaben ist gewachsen. Dank welcher geheimen Zutat ist das passiert? Aufgrund von Quantenverschränkung.

Stellen Sie sich vor, jemand kam zu Ihnen und sagte, er habe ein Orakel, das die geheimen Geheimnisse des Universums enthüllen kann. Das könnte Sie interessieren, aber es fällt Ihnen schwer, es zu glauben. Sie möchten einen Weg finden, um zu bestätigen, dass das Orakel die Wahrheit sagt.

Dies ist das Hauptproblem der Informatik. Einige Aufgaben sind zu schwierig, um sie in angemessener Zeit zu lösen. Ihre Entscheidungen sind jedoch leicht zu überprüfen. Vor diesem Hintergrund möchten Informatiker wissen: Wie komplex kann eine Aufgabe sein, deren Lösung noch überprüft werden kann?

Es stellt sich heraus, dass die Antwort auf diese Frage lautet: fast unvorstellbar komplex.

In einem Artikel , der im April 2019 erschien, haben zwei Informatikspezialisten die Anzahl der Aufgaben, die in die Kategorie „schwer zu lösen, leicht zu überprüfen“ fallen, radikal erhöht. Sie beschreiben eine Methode, mit der man Lösungen für Probleme von nahezu unverständlicher Komplexität überprüfen kann. "Es klingt verrückt", sagte Thomas Widick, ein IT-Spezialist am California Institute of Technology, der nicht an dieser Arbeit beteiligt ist.

Die Studie ist auf Quantencomputer anwendbar, die Berechnungen nach den nicht intuitiven Regeln der Quantenmechanik durchführen. Quantencomputer sind kaum aufgetaucht, aber in Zukunft haben sie das Potenzial, das Computing zu revolutionieren.

Die neue Arbeit gibt uns tatsächlich eine Hebelwirkung auf dieses allmächtige Orakel. Selbst wenn das Orakel verspricht, Ihnen vorgefertigte Lösungen für Probleme zu geben, deren Lösungsmöglichkeiten weit über Ihren Fähigkeiten liegen, bleibt eine Möglichkeit zu prüfen, ob das Orakel die Wahrheit sagt.

Bis zum Ende des Universums

Wenn ein Problem schwer zu lösen, aber leicht zu überprüfen ist, dauert es lange, eine Lösung zu finden, die Richtigkeit einer bestimmten Lösung jedoch nicht. Angenommen, eine Person zeigt Ihnen ein Diagramm - eine Reihe von Punkten (Eckpunkten), die durch Linien (Kanten) verbunden sind. Eine Person fragt, ob es möglich ist, die Scheitelpunkte des Diagramms mit drei Farben zu färben, sodass keine zwei verbundenen Scheitelpunkte dieselbe Farbe haben.



Die Aufgabe von drei Farben ist schwer zu lösen. Im allgemeinen Fall nimmt die Zeit, die erforderlich ist, um nach der Färbung von Scheitelpunkten zu suchen (oder festzustellen, dass eine solche Färbung nicht vorhanden ist), mit zunehmender Größe des Diagramms exponentiell zu. Wenn beispielsweise die Suche nach einer Lösung für einen Graphen mit 20 Eckpunkten 3 bis ²⁰ ns dauert, dh einige Sekunden, dauert ein Graph mit 60 Eckpunkten 3 bis ⁶⁰ ns, was dem 100-fachen des aktuellen Alters des Universums entspricht.

Angenommen, jemand behauptet, die Zählung mit drei Farben bemalt zu haben. Die Überprüfung dieser Anwendung dauert nicht lange. Sie müssen nur alle Scheitelpunkte einzeln umgehen und die mit ihnen verbundenen Scheitelpunkte untersuchen. Mit zunehmender Größe des Diagramms nimmt die Zeit dieser Überprüfung langsam zu - als Polynom . Infolgedessen benötigt ein Computer nicht viel länger, um die Farbe eines Diagramms mit 60 Scheitelpunkten zu überprüfen, als um ein Diagramm mit 20 Scheitelpunkten zu überprüfen.

"Mit den richtigen Farben in drei Farben ist es einfach, die Leistung zu testen", sagte John Wright , Physiker am Massachusetts Institute of Technology, der diese Arbeit zusammen mit Anand Natarajan von Caltech schrieb.

In den 1970er Jahren bestimmten Informatiker eine Klasse von Aufgaben, die leicht zu überprüfen sind, auch wenn einige von ihnen schwer zu lösen sind. Sie nannten diese Klasse NP nicht deterministische Polynomzeit . Seitdem wurde in der Informatik die NP-Klasse mehr als andere studiert. Insbesondere möchten Informatiker wissen, wie sich diese Klasse ändert, wenn der Testalgorithmus neue Möglichkeiten zur Überprüfung der Richtigkeit der Lösung erhält.

Richtige Fragen

Vor der Arbeit von Natarajan und Wright nahm die Inspektionskraft in zwei großen Sprüngen zu.

Stellen Sie sich vor, Sie unterscheiden nicht zwischen Farben, um die erste zu verstehen. Jemand legt zwei Würfel vor sich auf den Tisch und fragt, ob sie die gleiche oder eine andere Farbe haben. Diese Aufgabe ist für Sie unmöglich. Darüber hinaus können Sie die Richtigkeit der Lösung dieses Problems durch eine andere Person nicht bestätigen.

Sie dürfen dieser prüfenden Person jedoch Fragen stellen. Angenommen, der Prüfer sagt Ihnen, dass die Würfel unterschiedliche Farben haben. Sie nennen einen von ihnen "Würfel A" und den anderen "Würfel B". Dann versteckst du sie hinter deinem Rücken und tauschst versehentlich die Plätze zwischen ihnen. Dann öffnen Sie die Würfel und bitten den Prüfer, den Würfel A zu finden.

Wenn die Würfel unterschiedliche Farben haben, ist dies eine sehr einfache Frage. Der Prüfer erkennt Würfel A, wenn es sich beispielsweise um einen roten Würfel handelt, und bestimmt ihn jedes Mal korrekt.

Wenn die Würfel jedoch dieselbe Farbe haben - und der Prüfer sie fälschlicherweise als anders bezeichnet hat -, kann der Prüfer nur raten, welcher welcher ist. Daher kann er den Würfel A nur in 50% der Fälle korrekt bestimmen. Indem Sie den Prüfer ständig nach seiner Entscheidung befragen, können Sie bestätigen, ob sie richtig ist.


Anand Natarajan und John Wright

"Der Prüfer kann Fragen an den Prüfer senden", sagte Wright, "und vielleicht wird der Prüfer am Ende des Gesprächs mehr von der Antwort überzeugt sein."

1985 haben drei Informatiker bewiesen, dass solche interaktiven Beweise verwendet werden können, um Lösungen für komplexere Probleme als Probleme von NP zu bestätigen. Ihre Arbeit schuf eine neue Klasse von Aufgaben, IP, "interaktive Polynomzeit". Die Methode zur Bestätigung der Farben der Würfel kann verwendet werden, um Antworten auf viel komplexere Fragen zu bestätigen.

Der zweite Durchbruch erfolgte im selben Jahrzehnt. Es sieht aus wie die Logik einer polizeilichen Untersuchung. Wenn Sie zwei Verdächtige haben, die Ihrer Meinung nach ein Verbrechen begangen haben, werden Sie sie nicht gemeinsam verhören. Sie werden sie in verschiedenen Räumen abfragen und die Antworten des einen mit den Antworten des anderen vergleichen. Wenn Sie sie einzeln interviewen, können Sie mehr Wahrheit enthüllen, als wenn Sie einen Verdächtigen hätten.

"Die beiden Verdächtigen werden nicht in der Lage sein, eine verteilte konsistente Geschichte zu erstellen, da sie die anderen Antworten nicht kennen", sagte Wright.

1988 haben vier Informatiker bewiesen, dass Sie eine Klasse von Problemen bestätigen können, die noch größer als IP ist, wenn Sie zwei Computer bitten, dasselbe Problem separat zu lösen und dann separat zu hinterfragen: die MIP-Klasse, interaktive Beweise mit vielen Beweisen.

Mit diesem Ansatz ist es beispielsweise möglich, die Richtigkeit der Färbung eines Diagramms in drei Farben für eine Folge von Diagrammen zu bestätigen, deren Größe viel schneller zunimmt als Diagramme aus NP. In NP nehmen die Diagrammgrößen linear zu - die Anzahl der Scheitelpunkte kann von 1 auf 2, auf 3, auf 4 usw. ansteigen -, sodass die Größe des Diagramms nicht unverhältnismäßig größer ist als die Zeit, die zum Überprüfen der Färbung erforderlich ist. In MIP wächst die Anzahl der Diagrammscheitelpunkte jedoch exponentiell von 2 ¹ auf 2 ² , 2 ³ , 2 ⁴ usw.

Infolgedessen sind die Diagramme zu groß, um in den Arbeitsspeicher des Computers zu passen. Dieser muss die Liste der Scheitelpunkte durchgehen und die Farbgebung überprüfen. Die Färbung kann jedoch weiterhin überprüft werden, indem den beiden Prüfern unterschiedliche, aber verwandte Fragen gestellt werden.

In MIP verfügt der Tester über genügend Speicher, um ein Programm auszuführen, mit dem wir feststellen können, ob zwei Scheitelpunkte des Diagramms durch eine Kante verbunden sind. Er kann die Antworten der Tester überprüfen, um sicherzustellen, dass die Farbgebung korrekt ist.

Erweiterung der Liste der Aufgaben, die schwer zu lösen, aber leicht zu überprüfen sind, von klassischen Computern über NP bis hin zu IP und MIP Aber Quantencomputer arbeiten ganz anders. Und über mehrere Jahrzehnte war nicht klar, wie ihre Verwendung dieses Bild verändert - ist es einfacher oder schwieriger, Lösungen mit ihrer Hilfe zu überprüfen?

Die neue Arbeit von Natarajan und Wright hat die Antwort auf diese Frage.

Quantentricks

Quantencomputer führen Berechnungen mit Quantenbits oder Qubits durch. Sie haben eine Eigenschaft wie Verstrickung miteinander. Und wenn zwei Qubits - oder sogar große Qubitsysteme - verwechselt werden, bedeutet dies, dass sich ihre physikalischen Eigenschaften in gewisser Weise gegenseitig beeinflussen.

In ihrer neuen Arbeit betrachten Natarajan und Wright ein Szenario, das zwei verschiedene Quantencomputer umfasst, wobei die Qubits des einen mit den Qubits des anderen verwechselt werden.

Es scheint, dass ein solches Setup die Qualität der Antwortüberprüfung verschlechtert. Die ganze Kraft interaktiver Beweise mit vielen Beweisen beruht auf der Tatsache, dass Sie zwei Zeugen einzeln befragen und ihre Antworten überprüfen können. Wenn die Antworten der Prüfer gleich sind, sind sie höchstwahrscheinlich wahr. Wenn jedoch die Quantenzustände zweier Prüfer verwechselt werden, scheinen sie mehr Möglichkeiten zu haben, konsequent auf der Richtigkeit falscher Antworten zu bestehen.

Als das Szenario mit zwei verschränkten Quantencomputern 2003 erstmals vorgestellt wurde, schlugen Informatiker vor, dass eine Verschränkung die Möglichkeit einer Verifizierung verringern würde. "Die offensichtliche Reaktion aller, einschließlich meiner, war, dass die Prüfer in diesem Fall mehr Möglichkeiten hatten", sagte Vidik. "Sie können Verwirrung verwenden, um ihre Antworten zu verknüpfen."

Trotz des anfänglichen Pessimismus versuchte Vidik mehrere Jahre lang, das Gegenteil zu beweisen. 2012 haben er und Tsuyoshi Ito bewiesen, dass die Möglichkeit besteht, alle Aufgaben in MIP mit verworrenen Quantencomputern zu testen.

Jetzt haben Natarajan und Wright bewiesen, dass die Situation noch besser ist: Mit Hilfe der Komplexität kann man eine noch größere Klasse von Problemen beweisen als ohne sie. Es ist möglich, die Verbindung zwischen verschränkten Quantencomputern zum Vorteil des Verifizierers umzukehren.

Um zu verstehen, wie dies zu tun ist, rufen Sie das Verfahren von MIP auf, um die Färbung von Diagrammen zu überprüfen, deren Größe exponentiell zunimmt. Der Tester verfügt nicht über genügend Speicher, um das gesamte Diagramm zu speichern, aber er verfügt über genügend Speicher, um zwei verbundene Scheitelpunkte zu bestimmen und den Testern eine Frage zur Farbe dieser Scheitelpunkte zu stellen.

In der von Natarajan und Wright betrachteten Problemklasse - NEEXP genannt, eine nicht deterministische zweimal exponentielle Zeit - wächst die Größe der Graphen noch schneller als in MIP. Diagramme in NEEXP wachsen mit "doppelter Exponentialrate". Anstatt als Grad von zwei zu wachsen - 2 ¹ , 2 ² , 2 ³ , 2 ⁴ usw. - wächst die Anzahl der Eckpunkte in den Diagrammen als Grad von zwei - 2 ^{2 1} , 2 ^{2 2} , 2 ^{2 3} , 2 ^{2 4} und so weiter. Infolgedessen sind die Diagramme schnell so groß, dass der Inspektor nicht einmal mehr ein Paar verbundener Scheitelpunkte finden kann.

"Um den Scheitelpunkt zu identifizieren, werden 2 ⁿ Bits benötigt, was exponentiell mehr ist, als der Verifizierer im Speicher hat", sagte Natarajan. Natarajan und Wright haben jedoch bewiesen, dass es möglich ist, die Färbung eines doppelt exponentiellen Graphen in drei Farben zu überprüfen, auch ohne die Möglichkeit zu bestimmen, welche Eckpunkte nach Beweisen gefragt werden müssen. Tatsache ist, dass Sie die Prüfer selbst dazu bringen können, die richtigen Fragen auszuwählen.

Die Idee, Computer dazu zu bringen, sich selbst über ihre eigenen Entscheidungen zu befragen, klingt für Informatiker ungefähr so ​​vernünftig wie die Aufforderung verdächtiger Krimineller, sich selbst zu befragen, ist definitiv eine dumme Angelegenheit. Das ist nur Natarajan und Wright haben bewiesen, dass dies nicht so ist. Und der Grund dafür ist Verwirrung.

"Verwickelte Staaten sind gemeinsame Ressourcen", sagte Wright. "Unser gesamtes Protokoll besteht darin, zu verstehen, wie diese gemeinsam genutzte Ressource verwendet wird, um miteinander verbundene Probleme zu erstellen."

Wenn Quantencomputer verwirrt sind, korreliert die Auswahl der Scheitelpunkte und gibt genau die richtigen Fragen zur Überprüfung der Farbgebung in drei Farben aus.

Gleichzeitig muss der Inspektor die beiden Quantencomputer nicht miteinander verflechten, damit ihre Antworten auf diese Fragen miteinander korrelieren (ähnlich wie zwei mutmaßliche Kriminelle ihr falsches Alibi korrelieren). Ein weiteres seltsames Quantenmerkmal befasst sich mit diesem Problem. In der Quantenmechanik verhindert das Unsicherheitsprinzip, dass wir gleichzeitig den genauen Ort und Moment eines Teilchens kennen. Wenn Sie eine Eigenschaft messen, zerstören Sie Informationen über eine andere. Das Unsicherheitsprinzip schränkt Ihr Wissen über zwei „komplementäre“ Eigenschaften eines Quantensystems stark ein.

Natarajan und Wright verwenden dies in ihrer Arbeit. Um die Farbe des Scheitelpunkts zu berechnen, zwingen sie zwei Quantencomputer, komplementäre Messungen durchzuführen. Jeder Computer berechnet die Farbe seines eigenen Scheitelpunkts und zerstört so alle Informationen über den anderen. Mit anderen Worten, Verwirrung ermöglicht es Computern, korrelative Fragen zu stellen, aber das Prinzip der Unsicherheit verbietet es ihnen, sich zu verschwören, um sie zu beantworten.

"Wir müssen die Prüfer vergessen lassen, und dies ist die Hauptsache, die Natarajan und Wright bei ihrer Arbeit getan haben", sagte Vidik. "Sie zwingen den Prüfer, die Informationen durch die Messung zu löschen."

Die Folgen ihrer Arbeit können als fast existenziell bezeichnet werden. Vor der Veröffentlichung der Arbeit war die Einschränkung des Wissens, die wir mit vollem Vertrauen erhalten können, viel geringer. Wenn wir eine Antwort auf ein Problem aus dem NEEXP-Satz erhalten würden, müssten wir es nur im Glauben akzeptieren. Aber Natarajan und Wright brachen aus diesen Grenzen heraus und ermöglichten es, die Antworten aus einem viel größeren Universum von Rechenproblemen zu bestätigen.

Und jetzt, da sie dies getan haben, ist nicht klar, wo die nächste Überprüfbarkeitsgrenze liegt. "Es könnte viel weiter gehen", sagte Lance Fortnau, IT-Spezialist am Georgia Institute of Technology. "Sie lassen die Gelegenheit offen, den nächsten Schritt zu tun."