MIP * = RE: epochale Beweise aus dem Bereich der Informatik, die den Dominoeffekt in Physik und Mathematik verursacht haben

Informatiker haben neue Grenzen bei der Überprüfung von Problemlösungen durch Berechnungsmethoden erreicht. Gleichzeitig fanden sie Antworten auf die wichtigsten offenen Fragen der Quantenmechanik und der reinen Mathematik.

Albert Einstein untersuchte 1935 in Zusammenarbeit mit Boris Podolsky und Nathan Rosen die Möglichkeit, die sich aus den neuen Gesetzen der Quantenphysik ergibt: Zwei Teilchen können sich in einem verschränkten Zustand befinden, wenn selbst große Entfernungen ihre Verbindung nicht verletzen. Im folgenden Jahr formulierte Alan Turing die erste allgemeine Berechnungstheorie und bewies, dass es Probleme gibt, die von Computern niemals gelöst werden können.  Diese beiden Ideen revolutionierten die Bereiche der Wissenschaft, auf die sie sich beziehen. Außerdem schienen sie nichts miteinander zu tun zu haben. Aber jetzt der Beweis





MIP * = RE kombinierte sie, was zur Lösung vieler Probleme in den Bereichen Informatik, Physik und Mathematik führte.

Quantencomputer führen Berechnungen mit verschränkten Quantenbits (Qubits) anstelle klassischer Nullen und Einsen durch. Neue Erkenntnisse deuten darauf hin, dass solche Computer theoretisch verwendet werden können, um Lösungen für eine Vielzahl von Problemen zu testen. Die Verbindung zwischen Quantenverschränkung und traditionellem Computing war für viele Forscher eine große Überraschung.

Miguel Navascués studiert Quantenphysik am Institut für Quantenoptik und Quanteninformation in Wien. "Das war eine völlige Überraschung", sagte er und kommentierte die Beweise.

Die Mitautoren der Evidenz haben sich zum Ziel gesetzt, die Grenzen des Ansatzes zur Überprüfung von Lösungen für Rechenprobleme zu definieren. Dieser Ansatz beinhaltet eine Quantenverschränkung. Nachdem die Forscher diese Grenzen entdeckt hatten, kamen sie zur Lösung von zwei weiteren Problemen, die fast ein Nebenprodukt ihrer Arbeit waren. Wir sprechen über die Zirelson-Hypothese in der Physik bezüglich der mathematischen Modellierung der Quantenverschränkung und das damit verbundene Problem in der reinen Mathematik - das Conn-Problem in der von Neumann-Algebra-Theorie (Conns Einbettungsproblem).

Infolgedessen verursachten die Ergebnisse der Anwendung der Beweise in Mathematik und Physik so etwas wie den Dominoeffekt.

„Alle Ideen gehören zur gleichen Zeit. Es ist schön zu sehen, wie sie auf so spektakuläre Weise wieder zusammenkommen “, sagt Henry Yuen) von der University of Toronto - einer der Mitautoren der Beweise. Neben ihm nahmen an dieser Arbeit Chzhenfen Ji ( Zhengfeng of Ji ) von der University of Technology Sydney, John Wright ( John Wright ) von der University of Texas in Austin, Anand Natarajan ( Anand Natarajan ) und Thomas Vidic ( von Thomas Vidick ) vom California Institute of Technology teil. Alle fünf Wissenschaftler arbeiten auf dem Gebiet der Informatik.

Unlösbare Probleme

Turing legte bereits vor dem Aufkommen der Computer den Grundstein, auf dem Überlegungen zum Computer aufbauen. Gleichzeitig zeigte er, dass es ein bestimmtes Problem gibt, das Computer nachweislich nicht lösen können. Dies ist das sogenannte Shutdown-Problem.

In der Regel empfangen Computerprogramme etwas an der Eingabe und erzeugen eine Ausgabe. Aber manchmal bleiben sie in endlosen Zyklen stecken, was bedeutet, dass sie nie aufhören. In diesem Fall gibt es nur einen Ausweg aus dieser Situation. Laut Henry Yuen müssen Sie das Programm manuell stoppen. Sie müssen nur ihrer Arbeit ein Ende setzen.

Turing hat bewiesen, dass es keinen universellen Algorithmus gibt, der herausfinden kann, ob ein Programm jemals gestoppt wird. Um dies herauszufinden, müssen Sie das Programm ausführen.

Henry Yuen, Thomas Widick, Zhengfeng Ji, Anand Natarajan und John Wright

„Sie haben eine Million Jahre gewartet, und das Programm hat nicht aufgehört. Vielleicht müssen Sie nur 2 Millionen Jahre warten? Es gibt keine Möglichkeit, dies im Voraus zu sagen "- sagt William Slofstra ( William Slofstra ), ein Mathematiker der University of Waterloo.

Turing hat aus technischer Sicht bewiesen, dass das Problem des Herunterfahrens unlösbar ist. Selbst der leistungsstärkste Computer, den Sie sich vorstellen können, kann damit nicht umgehen.

Nach Turing begannen Informatiker, andere Aufgaben nach ihrer Komplexität zu klassifizieren. Komplexere Aufgaben erfordern mehr Rechenleistung - mehr Prozessorzeit und Speicher. Dies ist eine Untersuchung der rechnerischen Komplexität von Algorithmen.

Infolgedessen wirft jedes Problem zwei große Fragen für die Forscher auf: „Wie schwer ist es, es zu lösen? Was ist die Schwierigkeit zu überprüfen, ob die resultierende Lösung korrekt ist? “

Befragung der Entscheidung durch Befragung

Wenn die Aufgaben relativ einfach sind, können ihre Lösungen unabhängig überprüft werden. Wenn Aufgaben jedoch komplizierter werden, kann es unglaublich schwierig sein, die Ergebnisse ihrer Lösung zu überprüfen. Trotzdem entschieden Informatiker 1985, dass es möglich sei, Vertrauen in die Richtigkeit der Antwort aufzubauen, auch wenn dies nicht allein bestätigt werden könne.

Die Überprüfungsmethode folgt der Logik der polizeilichen Befragung.

Wenn der Verdächtige eine sorgfältig durchdachte Geschichte erzählt, kann der Ermittler wahrscheinlich nicht einfach jede seiner Details bestätigen. Wenn Sie jedoch die richtigen Fragen stellen, können Sie entweder den Verdächtigen auf einer Lüge erwischen oder die Richtigkeit seiner Geschichte bestätigen.

In Bezug auf die Informatik werden die beiden Seiten der Befragung durch zwei Computer dargestellt. Das erste ist ein leistungsstarkes Computersystem, das eine Lösung für das Problem bietet. Er wird der Zeuge genannt. Das zweite Gerät ist nicht mehr so ​​leistungsfähig, dass der Tester Fragen stellt, um festzustellen, ob die von ihm angebotene Antwort korrekt ist. Dieser Computer wird als Verifizierer bezeichnet.

Betrachten Sie ein einfaches Beispiel. Angenommen, jemand (der Prüfer) leidet an Farbenblindheit. Jemand anderes (der Zeuge) behauptet, dass die beiden Kugeln in verschiedenen Farben bemalt sind und sich nicht voneinander unterscheiden. Der Prüfer kann diese Anweisung selbst nicht überprüfen. Nachdem er das Verhör geschickt aufgebaut hat, kann er dennoch herausfinden, ob dies wirklich so ist.

Dazu können Sie die Kugeln hinter dem Rücken verstecken und mischen. Und dann - fragen Sie den Prüfer, welcher Ball in welcher Hand ist. Wenn sie wirklich unterschiedlich sind, sollte der Prüfer eine solche Frage immer richtig beantworten. Aber wenn sie die gleiche Farbe haben, das heißt, sie sehen genauso aus, wird sich die Hälfte der Antworten des Prüfers als falsch herausstellen.

Thomas Widick sagt, wenn sich weit mehr als die Hälfte der Antworten des Prüfers als richtig herausstellt, kann man sehr sicher sein, dass die Kugeln unterschiedliche Farben haben.

Indem Sie den Prüfern Fragen stellen, können Sie die Lösungen einer größeren Klasse von Problemen überprüfen, als Sie selbst überprüfen können.

1988 untersuchten Informatiker eine Situation, in der es zwei Prüfer gibt, die Lösungen für dasselbe Problem anbieten. Wenn zwei Verdächtige verhört werden können, vereinfacht dies letztendlich die Aufdeckung des Verbrechens oder - die Überprüfung der Entscheidung, da sie gezwungen werden können, gegeneinander zu spielen.

Dies gibt dem Prüfer laut Thomas Widick mehr Einfluss. Er befragt, stellt verwandte Fragen, überprüft die Antworten. Wenn die Verdächtigen die Wahrheit sagen, sollten ihre Antworten die meiste Zeit übereinstimmen. Wenn sie lügen, gehen ihre Antworten oft auseinander.

In ähnlicher Weise zeigten die Forscher, dass es durch die getrennte Befragung von zwei Zeugen und die Frage nach den gefundenen Lösungen möglich ist, die Lösungen einer noch umfangreicheren Problemklasse schnell zu überprüfen, als wenn sie mit einem Prüfer arbeiten.

Studien zur rechnerischen Komplexität von Algorithmen mögen rein theoretisch erscheinen, sind jedoch sehr eng mit der realen Welt verbunden. Die Ressourcen, die Computer benötigen, um Probleme zu lösen und Lösungen zu überprüfen - Zeit und Speicher -, sind physische Ressourcen. Aus diesem Grund können neue Entdeckungen in der Physik den Ansatz zur Untersuchung der Komplexität von Berechnungen ändern.

Anand Natarajan sagt, wenn wir uns von der klassischen physikalischen Basis der Berechnungen entfernen und etwas völlig anderes wählen, wie Quantenmechanismen, werden wir auch eine neue Theorie der rechnerischen Komplexität erhalten.

Der neue Beweis ist das Endergebnis einer Kollision von Informatikern des 21. Jahrhunderts mit einer der seltsamsten Ideen der Physik des letzten Jahrhunderts - mit der Idee der Quantenverschränkung.

Conns Problem

Wenn zwei Teilchen verwickelt sind, beeinflussen sie sich tatsächlich nicht gegenseitig. Es gibt keinen kausalen Zusammenhang zwischen ihren Handlungen. Einstein und seine Co-Autoren arbeiteten 1935 in einem Artikel an dieser Idee. Anschließend versuchten Physiker und Mathematiker, eine mathematische Methode zu finden, um zu beschreiben, was Quantenverschränkung tatsächlich bedeutet.

Diese Bemühungen haben jedoch zu gemischten Ergebnissen geführt. Wissenschaftler haben zwei verschiedene mathematische Modelle der Verschränkung entwickelt. Es war jedoch nicht klar, ob diese Modelle einander äquivalent sind.

Das Vorhandensein einer solchen möglichen Dissonanz führte auf Umwegen zu einem wichtigen Problem auf dem Gebiet der reinen Mathematik. Dies ist Conns Problem in der Theorie der von Neumann-Algebren. Am Ende spielte es die Rolle eines „Hinweises“, den fünf Informatiker bei der Ableitung ihrer Beweise ausnutzten.

Die erste Möglichkeit, die Quantenverschränkung zu modellieren, bestand darin, Teilchen als räumlich voneinander isolierte Objekte wahrzunehmen. Angenommen, eines dieser Teilchen befindet sich auf der Erde und das andere auf dem Mars. Der Abstand zwischen ihnen schließt einen Kausalzusammenhang zwischen ihnen aus (sie sind kausal getrennt). Dies wird als Tensorproduktmodell bezeichnet.

In einigen Situationen ist die kausale Trennung von Entitäten jedoch nicht ganz offensichtlich. Infolgedessen gelangten die Mathematiker zu einer zweiten, allgemeineren Methode zur Beschreibung der kausalen Unabhängigkeit.

Wenn die Reihenfolge, in der zwei Operationen ausgeführt werden, das Ergebnis nicht beeinflusst, wird die Operation als kommutativ bezeichnet: 3x2 entspricht 2x3. In diesem zweiten Modell werden Partikel verwickelt, wenn ihre Eigenschaften korreliert sind, aber die Reihenfolge, in der die Messungen durchgeführt werden, spielt keine Rolle. Man kann Messungen an Partikel A durchführen, um den Impuls von Partikel B vorherzusagen, und umgekehrt. In jedem Fall ist das Ergebnis das gleiche. Dies wird als Kommutierungsmodell für Kommutierungsoperatoren bezeichnet.

Beide Beschreibungen der Verschränkung verwenden Arrays von Zahlen, die als Matrizen bezeichnet werden. Matrizen bestehen aus Zeilen und Spalten. Das Tensorproduktmodell verwendet Matrizen mit einer endlichen Anzahl von Zeilen und Spalten. Das Kommutierungsoperatormodell verwendet allgemeinere Objekte, die als Matrizen mit einer unendlichen Anzahl von Zeilen und Spalten fungieren.

Im Laufe der Zeit begannen Mathematiker, diese Matrizen als Objekte von unabhängigem Interesse zu untersuchen, die in keiner Weise mit der physischen Welt verbunden waren. In Übereinstimmung mit dieser Arbeit schlug der Mathematiker Alain Connes 1976 vor, dass es möglich sein sollte, viele Matrizen unendlicher Dimension unter Verwendung von Matrizen endlicher Dimension zu approximieren. Dies ist eine der Konsequenzen des Conn-Problems in der Theorie der von Neumann-Algebren.

Im nächsten Jahrzehnt formulierte der Physiker Boris Tsirelson eine neue Version dieses Problems, die es erneut auf das Gebiet der Physik zurückführte. Zirelson schlug vor, dass die Modelle des Tensorprodukts und des Pendleroperators ungefähr gleichwertig sind. Diese Aussage ist sinnvoll, da beide Modelle theoretisch zwei verschiedene Arten sind, dasselbe physikalische Phänomen zu beschreiben. Nachfolgende Arbeiten zeigten, dass aufgrund der Verbindung zwischen Matrizen und physikalischen Modellen, die sie verwenden, die Probleme von Conn und Zirelson indirekt zusammenhängen: Wenn eines gelöst wird, wird das andere gelöst.

Die Lösung für diese beiden Probleme kam jedoch von einem völlig unerwarteten Ort.

Spielphysik

In den 1960er Jahren entwickelte der Physiker John Bell einen Test, um festzustellen, ob die Quantenverschränkung ein reales physikalisches Phänomen und kein theoretisches Konzept ist. Der Test verwendete so etwas wie ein Spiel, dessen Ergebnisse es ermöglichten herauszufinden, ob bestimmte Mechanismen, die nicht mit der normalen Physik zusammenhängen, während des Spiels funktionieren.

Später erkannten Informatiker, dass dieser Test im Zusammenhang mit der Quantenverschränkung auch als Werkzeug zur Überprüfung von Lösungen für sehr komplexe Probleme verwendet werden kann.

Aber bevor wir weitermachen, lassen Sie uns über das Spiel sprechen. Stellen Sie sich vor, es gibt zwei Spieler: Alice und Bob sowie ein 3x3-Spielfeld. Der Moderator weist Alice eine Zeile zu und fordert sie auf, in jede Zelle 0 oder 1 einzugeben, damit ihre Summe eine ungerade Zahl ergibt. Bob bekommt eine Spalte, die mit Nullen und Einsen gefüllt werden muss, damit ihre Summe eine gerade Zahl ergibt. Sie gewinnen, wenn sie dieselbe Zahl an die Stelle setzen, an der sich Zeile und Spalte schneiden. Es ist unmöglich, mit ihm zu kommunizieren.

Unter normalen Umständen können sie in 89% der Fälle am besten gewinnen. Wenn Sie jedoch den Faktor der Quantenverschränkung berücksichtigen, verbessern sich ihre Chancen.

Stellen Sie sich vor, Alice und Bob haben Quantenteilchen verwickelt. Sie nehmen Messungen ihrer Partikel vor und verwenden die Messergebnisse, um anzugeben, was in jede Zelle geschrieben werden soll - 0 oder 1. Da die Partikel verwickelt sind, korrelieren die Messergebnisse miteinander. Und das bedeutet auch, dass die Aktionen der Spieler miteinander verbunden werden. Infolgedessen stellt sich heraus, dass sie das Spiel immer gewinnen können.

Wenn sich in der Zelle, in der sich Zeile und Spalte schneiden, unterschiedliche Zahlen befinden, geht das Spiel verloren. Wenn sie gleich sind - gewonnen.

Wenn sich herausstellt, dass zwei Spieler dieses Spiel überraschend erfolgreich spielen, können wir daraus schließen, dass sie etwas anderes verwenden als die klassische Physik. Diese "Bell" -Experimente werden heute als "nicht-lokale" Spiele bezeichnet und beziehen sich auf die Trennung von Spielern. In der Tat führen Physiker ähnliche Spiele in Labors durch.

Henry Yuen sagt, dass Wissenschaftler im Laufe der Jahre Experimente durchgeführt haben, um die Realität dieser erschreckenden Phänomene zu beweisen.

Wie bei der Analyse eines Spiels müssen Sie möglicherweise herausfinden, wie oft Spieler in einem nicht lokalen Spiel gewinnen können, da sie so gut wie möglich spielen. Im Fall von Solitaire können Sie beispielsweise die Häufigkeit möglicher Gewinne desjenigen berechnen, der perfekt spielt.

Im Jahr 2016 hat William Slofstra jedoch bewiesen, dass es keinen allgemeinen Algorithmus zur Berechnung der genauen maximalen Gewinnwahrscheinlichkeit für alle nicht lokalen Spiele gibt. Infolgedessen stellten die Forscher die Frage: Ist es möglich, den maximalen Prozentsatz der Gewinne zumindest annähernd zu berechnen?

Informatiker kamen zu der Antwort unter Verwendung der beiden oben beschriebenen Modelle der Quantenverschränkung. Der Algorithmus, der das Tensorproduktmodell verwendet, legt den Minimalwert für die ungefähre Berechnung der maximalen Gewinnwahrscheinlichkeit für alle nicht lokalen Spiele fest. Ein anderer Algorithmus, der das Modell des Schaltoperators verwendet, legt den Maximalwert fest.

Je genauer die Implementierung dieser Algorithmen ist, desto länger läuft das Programm. Wenn die Zirelson-Hypothese wahr ist und diese beiden Modelle äquivalent sind, sollten sich die unteren und oberen Grenzen einander nähern und sich in einen einzigen Wert verwandeln, der die ungefähre maximale Gewinnwahrscheinlichkeit darstellt.

Wenn jedoch die Zirelson-Hypothese nicht zutrifft und die beiden Modelle nicht gleichwertig sind, werden nach Henry Yuen die oberen und unteren Grenzen immer getrennt. Und es wird keine Möglichkeit geben, auch nur den ungefähren Prozentsatz der Gewinne für nicht lokale Spiele zu berechnen.

Fünf Forscher nutzten in ihrer neuen Arbeit das Argument, ob die oberen und unteren Grenzen konvergieren und ob die Zirelson-Hypothese wahr oder falsch ist. Sie taten dies, um die Antwort auf die Frage zu finden, in welchen Situationen es möglich ist, Lösungen für Rechenprobleme zu überprüfen.

Komplizierte Hilfe

Zu Beginn der zweitausendsten Informatiker fragten sie sich, wie sich das Aufgabenspektrum ändern würde, dessen Lösungen überprüft werden können, indem zwei Prüfer mit komplizierten Partikeln „abgefragt“ werden.

Die meisten Wissenschaftler dachten, Verwirrung schadet der Überprüfung. Am Ende wird es für die beiden „Verdächtigen“ einfacher sein, falsche Aussagen miteinander in Einklang zu bringen, wenn sie die Antworten koordinieren können.

In den nächsten Jahren wurde jedoch klar, dass die gegenteilige Aussage zutrifft: Durch das „Abfragen“ von Prüfern mit komplizierten Partikeln kann eine viel breitere Klasse von Problemen überprüft werden als bei der Arbeit mit Prüfern ohne solche Partikel.

Thomas Widick sagt, Verschränkung sei ein Weg, Korrelationen zu schaffen, die Zeugen beim Lügen zu helfen scheinen. Tatsächlich kann dieses Phänomen jedoch zu ihrem Vorteil genutzt werden.

Um zu verstehen, wie man es benutzt, müssen Sie sich zuerst mit dem fast übernatürlichen Umfang von Aufgaben befassen, deren Lösungen dank dieses interaktiven Verfahrens überprüft werden können.

Stellen Sie sich ein Diagramm vor - eine Reihe von Punkten (Eckpunkten), die durch Linien (Flächen) verbunden sind. Sie müssen herausfinden, ob es mit drei Farben möglich ist, die Scheitelpunkte so zu malen, dass das Diagramm keine zwei Scheitelpunkte enthält, die durch ein Gesicht verbunden und gleichzeitig in derselben Farbe gezeichnet sind. Wenn möglich, ist ein solches Diagramm „dreifarbig“.

Wenn Sie einem Beweispaar ein sehr großes Diagramm geben und es meldet, dass es „dreifarbig“ ist, kann man sich fragen, ob es eine Möglichkeit gibt, seine Antwort zu überprüfen.

Bei sehr großen Grafiken ist es unmöglich, die Antwort direkt zu überprüfen. Stattdessen können Sie jeden der Tester fragen, welche Farbe einer der beiden verbundenen Scheitelpunkte hat. Wenn jeder von ihnen unterschiedliche Farben meldet und jedes Mal, wenn er danach gefragt wird, ähnliche Antworten gibt, können wir sicher sein, dass das Diagramm tatsächlich „dreifarbig“ ist.

Aber selbst diese Abfragestrategie funktioniert nicht bei großen Graphen mit mehr Flächen und Eckpunkten als Atomen im Universum. Selbst das Stellen einer bestimmten Frage („Sagen Sie mir die Farbe des XYZ-Scheitelpunkts“) wird zu einem unerträglichen Problem für jemanden, der versucht, eine Lösung für ein Problem zu überprüfen. Die Datenmenge, die zum einfachen Angeben des Namens eines bestimmten Scheitelpunkts benötigt wird, ist größer, als der Prüfer in dem ihm zur Verfügung stehenden Speicher speichern kann.

Die Quantenverschränkung ermöglicht jedoch ein Arbeitsschema, in dessen Anwendung die Zeugen selbst die Fragen formulieren.

„Der Prüfer muss keine Fragen stellen. Der Prüfer zwingt die Befürworter, diese Fragen unabhängig zu formulieren und zu beantworten “, sagt John Wright.

Der Prüfer benötigt die Prüfer, um die Farben der verbundenen Scheitelpunkte zu melden. Wenn die Eckpunkte nicht verbunden sind, sagen die Antworten auf die Fragen nichts darüber aus, ob das Diagramm „dreifarbig“ ist oder nicht. Mit anderen Worten, der Prüfer benötigt Tester, um verwandte Fragen zu stellen. Einer der Prüfer fragt nach der Spitze von ABC und der zweite nach der Spitze von XYZ. Es wird angenommen, dass die beiden Peaks miteinander verbunden sind, obwohl keiner der Beweise weiß, an welchen der andere „denkt“. (Dies ähnelt der Art und Weise, wie Alice und Bob hoffen, dieselbe Nummer in dieselbe Zelle zu schreiben, obwohl keiner von ihnen weiß, mit welcher Zeile oder Spalte der Tabelle der andere arbeitet.)

Wenn zwei Prüfer solche Fragen völlig unabhängig voneinander formulieren würden, gäbe es keinen Mechanismus, um sie zu zwingen, verbundene (korrelierende) Eckpunkte auszuwählen, so dass der Prüfer ihre Antworten überprüfen kann. Aber eine solche Korrelation ist genau das, was eine Quantenverschränkung erreichen kann.

Thomas Widick sagt, dass sie Komplikationen verwenden werden, um praktisch alle Fälle an die Zeugen weiterzuleiten. Wissenschaftler lassen die Tester ihre eigenen Fragen auswählen.

Am Ende dieses Vorgangs meldet jeder der Prüfer eine Scheitelpunktfarbe. Der Prüfer prüft, ob es sich um unterschiedliche Farben handelt oder nicht. Wenn das Diagramm tatsächlich dreifarbig ist, sollten die Tester niemals dieselbe Farbe angeben.

Laut Henry Yuen können die Tester den Forscher davon überzeugen, dass dies tatsächlich der Fall ist, wenn die Grafik „dreifarbig“ ist.

Wie sich herausstellte, ist dieses Überprüfungsverfahren ein weiteres Beispiel für ein nicht lokales Spiel. Proofer „gewinnen“, wenn sie den Forscher davon überzeugen, dass ihre Entscheidung richtig ist.

Im Jahr 2012 Thomas Widik und Tsuyoshi Ito) haben bewiesen, dass man mit komplizierten Testern eine Vielzahl nicht-lokaler Spiele spielen kann, um Lösungen zu testen. Dies gilt mindestens für die gleiche Anzahl von Aufgaben, die durch Abfragen von zwei klassischen Computern überprüft werden können. Die Verwendung verwirrender Beweise schadet daher nicht der Überprüfung. Im vergangenen Jahr haben Anand Natarajan und John Wright bewiesen, dass die Interaktion mit komplizierten Zeugen tatsächlich die Klasse der Probleme erweitert, deren Lösungen überprüft werden können.

Informatiker wussten jedoch nicht über alle Aufgaben Bescheid, deren Lösungen mit diesem Ansatz überprüft werden können. Jetzt wissen sie davon.

Domino-Effekt

In ihrer neuen Arbeit haben fünf Wissenschaftler bewiesen, dass die „Befragung“ verwirrter Zeugen es ermöglicht, Lösungen für unlösbare Probleme zu überprüfen, einschließlich der Lösung eines Abschaltproblems.

Laut Henry Yuen verfügen Modelle dieses Typs über unvorstellbare Überprüfungsmöglichkeiten.

Die Stoppaufgabe ist jedoch unlösbar. Und diese Tatsache war die treibende Kraft, die zum endgültigen Beweis führte.

Stellen Sie sich vor, Sie hätten das Programm einigen verwirrten Zeugen übergeben. Sie haben sie gefragt, ob dieses Programm jemals aufhören wird. Sie sind bereit, ihre Antworten durch ein nicht lokales Spiel zu überprüfen. Proofer generieren Fragen und „gewinnen“ basierend auf der Koordination ihrer Antworten.

Wenn das Programm tatsächlich stoppt, sollten die Befürworter in 100% der Fälle das Spiel gewinnen können. Dies ähnelt einem Beispiel mit einem Diagramm. Wenn es wirklich „dreifarbig“ ist, sollten gewundene Prüfer für verbundene Scheitelpunkte niemals dieselbe Farbe melden. Wenn das Programm nie stoppt, sollten die Tester nur zufällig gewinnen - in 50% der Fälle.

Dies bedeutet, dass Sie zuerst das Stoppproblem lösen müssen, wenn Sie jemand auffordert, die ungefähre maximale Gewinnwahrscheinlichkeit für ein bestimmtes nicht lokales Spiel zu ermitteln. Aber dieses Problem zu lösen ist unmöglich. Dies bedeutet, dass es unmöglich ist, die ungefähre maximale Gewinnwahrscheinlichkeit für nicht lokale Spiele sowie für das Stoppproblem zu finden.

Und dies bedeutet wiederum, dass die Tsirelson-Hypothese falsch ist: Die beiden Modelle der Quantenverschränkung sind nicht äquivalent. Wenn sie äquivalent wären, wäre es möglich, die Unter- und Obergrenze auf den gleichen Wert zu reduzieren und die ungefähre maximale Gewinnwahrscheinlichkeit zu berechnen.

David Pérez-García von der Complutense-Universität Madrid sagt, dass ein solcher Algorithmus nicht existieren kann, weshalb die beiden [Modelle] unterschiedlich sein müssen.

Die neue Arbeit beweist, dass die Klasse von Problemen, deren Lösungen mit Hilfe komplizierter Quantenprüfer überprüft werden können, eine Klasse namens MIP *, genau der Klasse von Problemen entspricht, die nicht komplizierter sind als das Stoppproblem - die Klasse RE. Der Titel des Papiers enthält einen kurzen Hinweis darauf: „MIP * = RE“.

Im Zuge des Beweises, dass die beiden Komplexitätsklassen gleich sind, haben die Wissenschaftler bewiesen, dass die Tsirelson-Hypothese falsch ist, was dank früherer Arbeiten bedeutet, dass die Conn-Hypothese auch falsch ist.

Forscher, die auf ihren jeweiligen Gebieten arbeiteten, waren verblüfft darüber, dass Lösungen für derart große Probleme dank Beweisen aus dem Bereich der Informatik erhalten wurden, die anscheinend nicht mit Mathematik und Physik zu tun haben.

Miguel Navázquez sagt, wenn er einen Artikel mit der Überschrift MIP * = RE gesehen hätte, hätte er nicht gedacht, dass sie etwas mit seiner Arbeit gemeinsam hat. Er war Mitautor einer früheren Arbeit, die die Hypothesen von Zirelson und Conn miteinander verband. Für ihn war das eine völlige Überraschung.

Quantenphysiker und Mathematiker beginnen gerade, einen neuen Beweis zu meistern. Zuvor waren Mathematiker an der Frage interessiert, ob sie Matrizen unendlicher Dimension approximieren können, indem sie stattdessen große Matrizen endlicher Dimension verwenden. Dank der Tatsache, dass Conns Hypothese sich als falsch erwiesen hat, wissen sie nun, dass dies nicht möglich ist.

"Ihre Ergebnisse zeigen, dass dies nicht möglich ist", sagte William Slofstra.

Informatiker versuchten nicht, Conns Hypothese zu analysieren. Infolgedessen sind sie nicht in der besten Position, um die möglichen Folgen der Lösung dieses Problems zu erklären.

„Ich persönlich bin kein Mathematiker. "Ich verstehe die ursprüngliche Formulierung der Conn-Hypothese nicht sehr gut", sagt Anand Natarajan.

Er und seine Co-Autoren erwarten von Mathematikern, dass sie neue Ergebnisse in ihre eigene Sprache übersetzen. In einem Publikationsbericht schreibt Thomas Widick: „Ich habe keinen Zweifel daran, dass die Theorie der Rechenkomplexität am Ende nicht benötigt wird, um rein mathematische Ergebnisse zu erhalten.“

Wenn jedoch andere Forscher mit dem Beweis vertraut werden, endet der Forschungsweg, dank dessen er erreicht werden konnte. Seit mehr als drei Jahrzehnten versuchen Informatiker lediglich herauszufinden, wie weit die interaktive Überprüfung von Problemlösungen sie bringen kann. Jetzt liegt vor ihnen die Antwort in Form eines langen Artikels mit einer einfachen Überschrift und mit Echos von Turings Ideen.

„Es gibt viele Werke, deren Autoren sich nur fragen, welche Möglichkeiten ein Verifizierungsverfahren mit zwei komplizierten Quantenbeweisen bietet. Jetzt wissen wir, wie leistungsfähig dieses Verfahren ist. Diese Geschichte ist zu Ende “, sagt Anand Natarajan.

Liebe Leser! Was bedeutet der Nachweis MIP * = RE für den Bereich, in dem Sie arbeiten?