👏🏿 🕋 ♍️ Ein wesentlicher Beweis für den Satz der Informatik erfasst die Physik mit der Mathematik 📤 📶 👐🏽

Fachleute der Informatik haben neue Grenzen des Wissens identifiziert, die durch Berechnung verifiziert wurden. Gleichzeitig lösten sie bedeutende Probleme aus der Quantenmechanik und der reinen Mathematik.

1935 versuchte Albert Einstein zusammen mit Boris Podolsky und Nathan Rosen, die sich mit den neuen Gesetzen der Quantenphysik eröffneten Möglichkeiten zu bewältigen: die "Verschränkung" zweier Teilchen, die in diesem Fall durch eine große Entfernung voneinander getrennt werden können.

Im folgenden Jahr formulierte Alan Turing die erste verallgemeinerte Berechnungstheorie und bewies die Existenz von Problemen, die im Prinzip keinen Computern unterliegen.

Diese beiden Ideen haben ihre jeweiligen Bereiche revolutioniert. Außerdem schienen sie nichts miteinander zu tun zu haben. Jetzt vereinte ein bedeutender Beweis sie und löste gleichzeitig eine ganze Reihe von Problemen aus den Bereichen Informatik, Physik und Mathematik.

Die neuen Erkenntnisse legen nahe, dass Quantencomputer, die Berechnungen mit Quantenbits oder „Qubits“ anstelle klassischer Nullen und Einsen durchführen, theoretisch verwendet werden können, um Lösungen für eine Vielzahl von Problemen zu bestätigen. Die Verbindung zwischen Quantenverschränkung und Computertechnologie war für viele Forscher ein Schock.

"Es war völlig unerwartet", sagte Miguel NavazquezStudium der Quantenphysik am Institut für Quantenoptik und Quanteninformation in Wien.

Die Mitautoren des Beweises beschlossen, die Grenzen der Möglichkeiten zur Bestätigung von Lösungen für Rechenprobleme zu bestimmen. Ihr Ansatz verwendet Verwirrung. Nachdem die Forscher diese Grenzen gefunden hatten, beantworteten sie gleichzeitig als beinahe Nebeneffekt zwei weitere Fragen: das Zirelson- Problem in der Physik hinsichtlich der mathematischen Modellierung von Verschränkungen und das damit verbundene Problem der reinen Mathematik, Conns Hypothese der Verschachtelung.

Die Ergebnisse fielen schließlich wie Dominosteine.

„Alle ursprünglichen Ideen wurden ungefähr zur gleichen Zeit geboren. Es ist praktisch, dass sie alle auf so erstaunliche Weise zusammengekommen sind “, sagte Henry Ewanvon der University of Toronto, einem der Autoren der Beweise. Andere Autoren: Zhengfeng Ji von der University of Technology Sydney, Anand Natarajan und Thomas Widick vom California Institute of Technology sowie John Wright von der University of Texas in Austin. Alle fünf sind Informatiker.

Unlösbare Aufgaben

Turing identifizierte die Hauptplattform für das Studium des Rechnens bereits vor dem Aufkommen der Computer selbst. Und buchstäblich sofort zeigte er, dass Computer bestimmte Probleme im Prinzip nicht lösen konnten - und dass dies bewiesen werden konnte. Die Sache ist, ob das Programm, das ein bestimmtes Problem löst, seine Arbeit beendet.

In der Regel empfangen Computerprogramme Eingabedaten und erzeugen nach einiger Zeit Ausgabedaten. Aber manchmal bleiben sie in endlosen Zyklen stecken, wodurch sich ihre Zahnräder für immer drehen. In diesem Fall haben Sie nur noch eine Option.

„Ich muss das Programm manuell festnageln. Halte sie einfach auf «, sagte Ewan.

Turing hat bewiesen, dass es keinen allgemeinen Algorithmus gibt, der bestimmen kann, ob ein Programm die Ausführung abschließt oder für immer funktioniert. Um dies herauszufinden, müssen Sie das Programm selbst ausführen.

Ewan, Vidik, Ji, Natarajan und Wright

„Sie haben eine Million Jahre gewartet, und das Programm hat nicht funktioniert. Müssen Sie noch eine Million Jahre warten? Auf diese Frage gibt es keine Antwort “, sagte William Slofstra , Mathematiker an der University of Waterloo.

Technisch gesehen ist die Aufgabe, ein Programm anzuhalten, nicht lösbar - selbst der leistungsstärkste Computer, den Sie sich vorstellen können, kann es nicht lösen.

Nach Turing begannen Informatiker, andere Aufgaben nach ihrer Komplexität zu klassifizieren. Komplexere Aufgaben erfordern mehr Rechenressourcen - mehr Zeit zum Arbeiten, mehr Speicher. Studieren Sie also die rechnerische Komplexität von Aufgaben.

Infolgedessen können Sie zu jeder Aufgabe zwei Fragen stellen: „Wie schwierig ist es, sie zu lösen?“ und "Wie schwierig ist es, die richtige Antwort zu überprüfen?"

Befragung zur Bestätigung

Bei einfachen Aufgaben kann die Antwort unabhängig überprüft werden. Da sie jedoch komplizierter werden, kann es unmöglich werden, die Antwort zu überprüfen. 1985 erkannten Informatiker jedoch, dass es möglich war, die Richtigkeit der Antwort zu überprüfen, auch wenn es unmöglich war, sie selbst zu bestätigen.

Diese Methode folgt der Logik einer polizeilichen Untersuchung. Wenn der Verdächtige eine verwirrende Geschichte erzählt, können Sie möglicherweise nicht jedes Detail überprüfen. Aber wenn Sie die richtigen Fragen stellen, können Sie den Verdächtigen in einer Lüge erwischen oder sich der Wahrheit der Geschichte sicher sein.

In Bezug auf die Informatik enthält die Abfrage einen leistungsstarken Computer, der eine Lösung für das Problem bietet - den so genannten „Prüfer“ - und einen weniger leistungsfähigen Computer, der den Prüfer der Fragen auffordert, die Richtigkeit der Antwort zu ermitteln, die als „Test“ bezeichnet wird.

Ein einfaches Beispiel: Stellen Sie sich vor, Sie unterscheiden nicht zwischen Farben, und die andere Person - der Prüfer - behauptet, dass zwei der Kugeln eine andere Farbe haben. Sie können diese Aussage nicht selbst überprüfen, aber durch ausgeklügelte Befragung können Sie immer noch überprüfen, ob sie wahr ist.

Legen Sie die Kugeln hinter sich und mischen Sie. Bitten Sie den Prüfer, Ihnen zu sagen, welche Farbe welche hat. Wenn sie wirklich unterschiedliche Farben haben, muss der Prüfer die Frage ständig richtig beantworten. Wenn sie dieselbe Farbe haben - das heißt, sie sehen gleich aus -, drückt der Prüfer in der Hälfte der Fälle die falsche Vermutung aus.

"Wenn ich sehe, dass Sie viel erfolgreicher sind als in der Hälfte der Fälle, bin ich mir fast sicher, dass sie nicht die gleiche Farbe haben", sagte Vidik.

Indem Sie den Prüfern Fragen stellen, können Sie die Richtigkeit von Lösungen für ein breiteres Spektrum von Aufgaben bestätigen, als Sie selbst lösen könnten.

1988 dachten Informatiker darüber nach, was passieren würde, wenn zwei Prüfer Lösungen für dasselbe Problem vorschlagen würden. Wenn Sie die Möglichkeit haben, zwei Verdächtige zu befragen, ist es für Sie sogar noch einfacher, das Verbrechen aufzuklären oder die Richtigkeit der Entscheidung zu bestätigen - sie können miteinander verglichen werden.

„Für diejenigen, die es überprüfen, gibt es mehr Raum für Druck. Sie befragen, stellen Fragen zum Fall und überprüfen die Antworten “, sagte Vidik. Wenn die Verdächtigen die Wahrheit sagen, sollten ihre Antworten die meiste Zeit übereinstimmen. Wenn sie lügen, wird es mehr Widersprüche geben.

In ähnlicher Weise zeigten die Forscher, dass man durch getrennte Befragung der beiden Prüfer hinsichtlich ihrer Antworten schnell die Richtigkeit der Lösung für eine noch größere Klasse von Problemen bestätigen kann, verglichen mit der, die man mit nur einem Prüfer angehen kann.

Computerkomplexität mag Ihnen als rein theoretische Idee erscheinen, ist aber dennoch eng mit der realen Welt verbunden. Die Ressourcen, die Computer benötigen, um Probleme zu lösen und Entscheidungen zu bestätigen - Zeit und Speicher - sind grundsätzlich physisch. Neue Entdeckungen in der Physik können daher die Komplexität der Berechnungen verändern.

"Wenn Sie einen anderen Satz physikalischer Gesetze wählen, zum Beispiel die Quantenwelt anstelle der klassischen, kann daraus eine andere Komplexitätstheorie abgeleitet werden", sagte Natarajan.

Der neue Beweis ist das Endergebnis der Konfrontation zwischen einem Informatiker des 21. Jahrhunderts und einer der seltsamsten Ideen der Physik des 20. Jahrhunderts: Verwirrung.

Conns Verschachtelungshypothese

Wenn sich zwei Teilchen verwickeln, beeinflussen sie sich nicht gegenseitig - sie haben keinen kausalen Zusammenhang. Einstein et al. Enthüllten diese Idee in einem Artikel von 1935. Danach versuchten Physiker und Mathematiker, eine mathematische Methode zu finden, um zu beschreiben, was Verwirrung eigentlich bedeutet.

Es gab jedoch einige Verwirrung. Wissenschaftler entwickelten zwei verschiedene mathematische Modelle der Verschränkung - und die Tatsache, dass sie einander äquivalent sind, war überhaupt nicht offensichtlich.

Indirekt beeinflusste diese mögliche Dissonanz die Entstehung eines wichtigen Problems aus dem Bereich der reinen Mathematik, Conns Hypothese der Verschachtelung. Und am Ende diente es auch als Schisma, das fünf Informatiker in ihren neuen Beweisen ausnutzten.

Die erste Möglichkeit, die Verschränkung zu modellieren, besteht darin, sich räumlich isolierte Partikel vorzustellen. Einer von ihnen ist zum Beispiel auf der Erde und der andere auf dem Mars; Der Abstand zwischen ihnen schließt einen Kausalzusammenhang aus. Dies wird als Tensorproduktmodell bezeichnet.

In einigen Situationen ist jedoch nicht ganz klar, ob zwei Objekte wirklich kausal voneinander isoliert sind. Daher haben Mathematiker einen allgemeineren Weg gefunden, um die kausale Unabhängigkeit zu beschreiben.

Wenn die Reihenfolge der Operationen an Objekten keine Rolle spielt, wird die Operation als geschaltet betrachtet: 3 x 2 ergibt das Gleiche wie 2 x 3. Im zweiten Modell werden Partikel verwickelt, wenn ihre Eigenschaften korrelieren, aber die Reihenfolge der Messungen spielt keine Rolle. Messen Sie Partikel A, um den Impuls von Partikel B vorherzusagen, oder umgekehrt. In jedem Fall ist die Antwort dieselbe. Dies wird als Verschränkungsmodell für geschaltete Operatoren bezeichnet.

Beide Beschreibungen der Verschränkung verwenden Arrays von Zahlen, die in Spalten und Zeilen - Matrizen - organisiert sind. Das Tensorproduktmodell verwendet Matrizen mit einer endlichen Anzahl von Spalten und Zeilen. Das Verschränkungsmodell des Kommutierungsoperators verwendet ein allgemeineres Objekt, das wie eine Matrix funktioniert, jedoch eine unendliche Anzahl von Zeilen und Spalten aufweist.

Im Laufe der Zeit begannen Mathematiker, diese Matrizen unabhängig von ihrer Verbindung zur Physik selbst zu erforschen. Im Rahmen dieser Arbeit stellte der Mathematiker Alain Conn 1976 die Hypothese auf, dass viele Matrizen unendlicher Dimension durch Matrizen endlicher Dimension approximiert werden können. Dies war eine der Schlussfolgerungen von Conns Hypothese der Verschachtelung.

Im nächsten Jahrzehnt wird der sowjetische Physiker [im ursprünglichen Physiker, aber auf Wikipedia als Mathematiker aufgeführt / ca. transl.] Boris Tsirelson schlug seine eigene Version dieses Problems vor, das wiederum mit der Physik in Verbindung gebracht wurde. Zirelson schlug vor, dass das Tensorprodukt und die kommutativen Operatormodelle, die die Verschränkung beschreiben, ungefähr gleichwertig sind. Dies ist sinnvoll, da dies theoretisch zwei verschiedene Arten sind, dasselbe physikalische Phänomen zu beschreiben. Nachfolgende Arbeiten zeigten, dass aufgrund der Verbindung der Matrizen und der physikalischen Modelle, die sie verwenden, Conns Hypothese über die Verschachtelung und das Zirelson-Problem aufeinander folgen: Lösen Sie eine und Sie lösen die andere.

Die Lösung für beide Probleme zeigte sich jedoch in einer völlig anderen Richtung.

Physik und Spiele

In den 1960er Jahren entwickelte der Physiker John Bell einen Test, um festzustellen, ob Verschränkung ein reales physikalisches Phänomen oder nur eine theoretische Idee ist. So etwas wie ein Spiel nahm an dem Test teil, dessen Ergebnis berichtete, ob etwas anderes als gewöhnliche Nicht-Quantenphysik eine Rolle in dem Experiment spielte.

Später werden Informatiker erkennen, dass dieser Verschränkungstest auch als Werkzeug zur Validierung von Lösungen für sehr komplexe Probleme verwendet werden kann.

Um zu verstehen, wie diese Spiele funktionieren, stellen Sie sich zunächst zwei Spieler vor, Alice und Bob, und eine 3x3-Box. Der Richter gibt Alice eine Zeile und schlägt vor, dass sie 0 oder 1 Zeilen in jede der Zellen setzt, so dass die Summe der Zahlen ungerade ist. Bob wird eine Spalte zugewiesen, und er muss alle seine Zellen ausfüllen, damit die Summe der Zahlen gerade ist. Sie gewinnen, wenn sie dieselbe Zahl in dieselbe Zelle setzen - wo sich die ausgewählte Zeile und Spalte schneiden. Gleichzeitig können sie aber nicht kommunizieren.

Unter normalen Bedingungen ist das Beste, was Spieler können, in 89% der Fälle zu gewinnen. Aber in der Quantenwelt können sie dieses Ergebnis verbessern.

Angenommen, Alice und Bob teilen sich ein Paar verwickelter Partikel. Jeder von ihnen nimmt Messungen seines Partikels vor und verwendet die Ergebnisse, um zu bestimmen, ob 0 oder 1 in jede Zelle geschrieben werden soll. Da die Partikel verwickelt sind, korrelieren die Ergebnisse ihrer Messungen miteinander, was bedeutet, dass auch ihre Antworten korrelieren - was bedeutet In 100% der Fälle können sie gewinnen.

Wenn Sie also sehen, dass zwei Spieler das Spiel unerwartet oft gewinnen, können Sie daraus schließen, dass sie etwas außerhalb der klassischen Physik verwenden. Jetzt werden Bells Experimente als "nicht-lokale" Spiele bezeichnet und beziehen sich auf die Trennung von Spielern. Und Physiker machen solche Experimente tatsächlich in Laboratorien.

"Die Leute haben solche Experimente jahrelang durchgeführt, und daraus folgt, dass dieser erschreckende Effekt wirklich existiert", sagte Ewan.

Bei der Analyse eines Spiels benötigen Sie möglicherweise Informationen darüber, wie oft Spieler ein nicht lokales Spiel gewinnen, wenn sie versuchen, auf die bestmögliche Weise zu spielen. Wenn Sie beispielsweise Solitaire Solitaire nehmen, können Sie die Wahrscheinlichkeit berechnen, mit der der Spieler, der perfekt spielt, gewinnen kann.

Im Jahr 2016 hat William Slofstra jedoch bewiesen, dass es keinen allgemeinen Algorithmus zur Berechnung der genauen maximalen Gewinnwahrscheinlichkeit bei nicht lokalen Spielen gibt. Die Forscher stellten die Frage: Ist es möglich, den maximalen Prozentsatz der Gewinne zumindest grob vorherzusagen?

Informatiker suchten nach einer Antwort anhand von zwei Modellen, die Feinheiten beschreiben. Der Algorithmus unter Verwendung des Tensorproduktmodells bestimmte die Untergrenze oder den Minimalwert der ungefähren maximalen Gewinnwahrscheinlichkeit für alle nicht lokalen Spiele. Ein anderer Algorithmus, der das Verschränkungsmodell mit einem DFÜ-Operator verwendete, bestimmte seine Obergrenze.

Je länger diese Algorithmen arbeiten, desto genauer ist das Ergebnis, das sie erzeugen. Wenn Zirelsons Vorhersage wahr ist und diese beiden Modelle wirklich gleichwertig sind, sollten sich die Unter- und Obergrenze allmählich annähern und zu einem einzigen Wert der ungefähren maximalen Gewinnwahrscheinlichkeit konvergieren.

Aber wenn Cirelsons Vorhersage falsch ist und die beiden Modelle nicht gleichwertig sind, "bleiben die unteren und oberen Grenzen für immer getrennt", sagte Ewan. Es wird unmöglich sein, auch nur den ungefähren Wert der maximalen Gewinnwahrscheinlichkeit für nicht lokale Spiele zu berechnen.

In der neuen Arbeit verwendeten fünf Forscher dieses Thema - ob die unteren und oberen Grenzen konvergieren und ob die Zirelson-Hypothese wahr ist -, um eine separate Frage nach der Möglichkeit zu lösen, die Richtigkeit der Lösung eines Rechenproblems zu bestätigen.

Komplizierte Hilfe

In den frühen 2000er Jahren dachten Informatiker: Wie wird sich das Aufgabenspektrum ändern, dessen Lösungen durch die Befragung zweier Prüfer mit komplizierten Partikeln bestätigt werden können?

Die meisten entschieden, dass Verstrickung gegen Bestätigung spielen würde. In der Tat wird es für zwei Verdächtige einfacher sein, eine konsistente Lüge zu konstruieren, wenn sie die Antworten koordinieren können.

In den letzten Jahren haben Informatiker jedoch erkannt, dass das Gegenteil der Fall ist: Durch Abfragen von Prüfern und Teilen von Paaren verschränkter Partikel kann man Lösungen für ein viel breiteres Spektrum von Problemen bestätigen als ohne Verschränkung.

"Verwirrung ist ein Weg, um eine Korrelation zu erhalten, die ihnen zu lügen und zu betrügen scheint", sagte Vidik. "Aber Sie können es tatsächlich zu Ihren Gunsten einwickeln."

Um zu verstehen, wie dies möglich ist, müssen Sie zunächst den nahezu übernatürlichen Aufgabenbereich bewerten, dessen Lösungen Sie mit diesem interaktiven Verfahren überprüfen können.

Stellen Sie sich ein Diagramm vor - eine Reihe von Punkten (Eckpunkten), die durch Linien (Kanten) verbunden sind. Vielleicht möchten Sie herausfinden, ob es möglich ist, die Scheitelpunkte mit drei Farben zu färben, sodass keine Scheitelpunktpaare derselben Farbe vorhanden sind, die durch eine gemeinsame Kante verbunden sind.

Wenn Sie ein paar Leuten ein sehr großes Diagramm beweisen und sagen, dass es wie beschrieben in drei Farben gefärbt werden kann, werden Sie denken: Gibt es eine Möglichkeit, diese Antwort zu überprüfen?

Sehr große Grafiken können nicht direkt überprüft werden. Stattdessen können Sie jeden Prüfer bitten, die Farbe von zwei durch eine Kante verbundenen Scheitelpunkten anzugeben. Wenn sie unterschiedliche Farben melden und jedes Mal während der Umfrage über andere Scheitelpunkte unterschiedliche Farben ausgeben, wächst Ihr Vertrauen, dass das Malen in drei Farben funktioniert.

Eine solche Abfragestrategie funktioniert jedoch auch nicht mehr, wenn die Graphen wirklich groß werden - wenn die Anzahl der Kanten und Eckpunkte beginnt, die Anzahl der Atome im Universum zu überschreiten. Für den Prüfer wird selbst eine Aufgabe wie das Stellen einer bestimmten Frage („Sagen Sie mir die Farbe des XYZ-Scheitelpunkts“) unerträglich - die Datenmenge, die zum Benennen eines bestimmten Scheitelpunkts benötigt wird, übersteigt den ihm zur Verfügung stehenden Arbeitsspeicher.

Durch Verwirrung können die Prüfer jedoch selbst Fragen stellen.

„Der Rezensent muss die Fragen nicht herausfinden. Der Inspektor lässt die Prüfer die Fragen für ihn selbst berechnen “, sagte Wright.

Der Inspektor benötigt die Prüfer, um ihm die Farben der verbundenen Eckpunkte mitzuteilen. Wenn die Eckpunkte nicht verbunden sind, sagen die Antworten auf die Frage nichts über die Möglichkeit aus, das Diagramm in drei Farben zu färben. Mit anderen Worten, der Prüfer möchte, dass der Prüfer verwandte Fragen stellt: Ein Prüfer stellt die Frage nach dem Scheitelpunkt ABC und der andere nach dem Scheitelpunkt XYZ. Und ich möchte, dass diese beiden Peaks miteinander verbunden werden, obwohl keiner der Prüfer weiß, über welchen Peak der andere spricht. Genau wie Alice und Bob hoffen, die gleiche Zahl auf das gleiche Quadrat zu setzen, obwohl keiner von ihnen weiß, mit welcher Zeile und Spalte der andere arbeitet.

Wenn jeder der beiden Prüfer eine Frage vollständig für sich stellen würde, könnte er nicht gezwungen werden, verbundene oder korrelierende Spitzen auszuwählen, damit der Prüfer seine Antworten bestätigen könnte. Durch Verschränkung können Sie jedoch nur eine Korrelation erstellen.

„Wir werden Verwirrung stiften, um die ganze Arbeit auf die Prüfer zu werfen. Wir werden sie dazu bringen, ihre eigenen Fragen zu wählen “, sagte Vidik.

Am Ende des Verfahrens meldet jeder Prüfer eine Farbe. Der Prüfer überprüft sie auf Übereinstimmung. Wenn ein Diagramm tatsächlich in drei Farben gefärbt werden kann, sollten Prüfer niemals dieselbe Farbe erzeugen.

"Wenn die Zählung in drei Farben gemalt werden kann, können die Prüfer Sie davon überzeugen", sagte Ewan.

Es stellt sich heraus, dass dieses Bestätigungsverfahren ein weiteres Beispiel für ein nicht lokales Spiel ist. Die Prüfer „gewinnen“, indem sie Sie von der Richtigkeit ihrer Entscheidung überzeugen.

Im Jahr 2012 haben Vidik und Tsiyoshi Ito bewiesen, dass es möglich ist, durch Spielen verschiedener nicht lokaler Spiele mit verwirrenden Beweisen die Antworten auf mindestens die gleiche Anzahl von Aufgaben zu bestätigen, wie bei der Befragung zweier klassischer Computer. Das heißt, die Verwendung verwirrender Prüfer schadet der Bestätigung ihrer Otteten nicht. Und letztes Jahr haben Natarajan und Wright bewiesen, dass die Interaktion mit verschlungenen Prüfern die Klasse der validierten Aufgaben tatsächlich erweitert.

Bis zu diesem Punkt haben Informatiker jedoch nicht die Größe des gesamten Aufgabenspektrums erraten, dessen Lösungen auf ähnliche Weise bestätigt werden können.

Kaskade von Konsequenzen

In der neuen Arbeit beweisen fünf Informatiker, dass die Befragung verschlungener Prüfer Lösungen für ungelöste Probleme, einschließlich des Stoppproblems, bestätigen kann.

"Die Validierungsfunktionen dieses Modells sind erstaunlich", sagte Ewan.

Das Stoppproblem kann jedoch nicht gelöst werden. Und diese Tatsache wurde zum Schlüssel, um den Beweis zu vervollständigen.

Angenommen, Sie geben ein paar verwirrenden Prüfern ein Programm. Sie bitten sie zu sagen, ob die Ausführung gestoppt wird. Sie sind bereit, ihre Antwort durch eine Vielzahl von nicht lokalen Spielen zu testen: Die Prüfer stellen Fragen und gewinnen je nach Konsistenz ihrer Antworten.

Wenn das Programm wirklich stoppt, sollten die Prüfer in 100% der Fälle in der Lage sein, dieses Spiel zu gewinnen - wie im Fall eines Diagramms, das mit drei Farben gefärbt werden kann, wenn die gewundenen Prüfer nicht für zwei verbundene Scheitelpunkte dieselbe Farbe angeben müssen. Wenn das Programm nicht stoppt, sollten die Prüfer nur zufällig gewinnen - das heißt in 50% der Fälle.

Dies bedeutet, dass Sie zuerst das Problem des Stopps lösen müssen, wenn jemand Sie auffordert, die ungefähre maximale Gewinnwahrscheinlichkeit für ein bestimmtes nicht lokales Spiel zu bestimmen. Aber es ist unmöglich zu lösen. Dies bedeutet, dass die Aufgabe der Berechnung der ungefähren maximalen Gewinnwahrscheinlichkeit nicht lösbar ist, ebenso wie das Problem des Stopps.

Und dies bedeutet wiederum, dass die Antwort auf das Zirelson-Problem negativ ist - die beiden Verschränkungsmodelle sind nicht gleichwertig. Wenn dies der Fall wäre, wäre es möglich, die Unter- und Obergrenze der Punktzahl zusammen zu reduzieren und die ungefähre maximale Gewinnwahrscheinlichkeit zu berechnen.

"Es kann keinen solchen Algorithmus geben, daher müssen die beiden Modelle unterschiedlich sein", sagte David Perez-Garcia von der Complutense-Universität Madrid.

Die neue Arbeit beweist, dass die Klasse von Problemen, deren Lösungen durch Wechselwirkung mit verschränkten Quantenprüfern bestätigt werden können, MIP *, vollständig der Klasse von Problemen entspricht, die nicht komplizierter sind als das Stoppproblem RE. Der Titel der Arbeit beschreibt kurz ihre Essenz: „MIP * = RE“.

Auf der Suche nach Beweisen für die Gleichheit der beiden Komplexitätsklassen haben Informatiker die Falschheit der Tsirelson-Hypothese bewiesen, die dank früherer Arbeiten die Falschheit von Conns Hypothese über das Verschachteln bedeutet.

Für Forscher aus den relevanten Bereichen war es ein Schock, dass die Antworten auf solch komplexe Probleme im Prozess scheinbar nicht verwandter Beweise aus dem Bereich der Informatik identifiziert wurden.

"Als ich eine Arbeit namens MIP * = RE sah, würde ich definitiv nicht glauben, dass sie etwas mit meiner Arbeit zu tun hat", sagte Navazquez, Co-Autor einer früheren Arbeit, die die Cirelson-Hypothese mit Conns Hypothese über das Verschachteln verband. "Es war eine völlige Überraschung für mich."

Spezialisten für Quantenphysik und Mathematik fangen gerade erst an, diese Informationen zu verarbeiten. Zuvor waren Mathematiker daran interessiert, ob sie unendlich dimensionale Matrizen durch große endliche annähern können. Jetzt, da sie die Falschheit von Conns Hypothese des Verschachtelns kennen, wissen sie, dass sie es nicht können.

"Aufgrund ihres Ergebnisses ist es unmöglich", sagte Slofstra.

Die Informatiker selbst haben nicht versucht, eine Bestätigung für Conns Hypothese über das Verschachteln zu finden, daher sollten andere Leute alle Konsequenzen der Antworten erklären, die sie stattdessen gefunden haben.

„Ich selbst bin kein Mathematiker. Ich verstehe die ursprüngliche Definition von Conns Hypothese über das Verschachteln nicht sehr gut “, sagte Natarajan.

Sie und Mitautoren schlagen vor, dass Mathematiker selbst das neue Ergebnis in die Sprache ihres Fachs übersetzen. In einem Artikel, in dem Beweise erklärt wurden, schrieb Vidik: „Ich habe keinen Zweifel daran, dass die Komplexitätstheorie nicht mehr benötigt wird, um rein mathematische Ergebnisse zu erhalten.“

Die daraus resultierenden Beweise unterbrechen die lange Forschungskette, die dazu geführt hat. Seit mehr als drei Jahrzehnten versuchen Informatiker herauszufinden, wie weit ihre interaktive Bestätigung führen wird. Jetzt haben sie eine Antwort in Form einer langen Arbeit mit einer einfachen Überschrift und Verweisen auf Turing.

"Es gibt eine ziemlich große Liste von Arbeiten, in denen nach Möglichkeiten gefragt wurde", sagte Natarajan im Bestätigungsverfahren mit Hilfe von zwei verwirrenden Prüfern. „Jetzt wissen wir welche. Die Geschichte ist vorbei. “

Ein wesentlicher Beweis für den Satz der Informatik erfasst die Physik mit der Mathematik