Konsequenzen von$MIP^\ast=RE$Über Quantenalgorithmen
Der (ausstehende Peer-Review) Beweis für$MIP^\ast=RE$in diesem Pre-Print wurde als bedeutender Durchbruch gefeiert. Die Bedeutung dieses Ergebnisses wird von Henry Yuen (einer der Autoren) in diesem Blogbeitrag angesprochen . Scott Aaronson listet in diesem Blogbeitrag auch einige der wichtigsten Auswirkungen auf .
Für ein nicht lokales Spiel ($G$), definieren das Supremum der Erfolgswahrscheinlichkeiten für nichtrelativistische Tensorproduktstrategien als$\omega^\ast(G)$, und das Supremum der Erfolgswahrscheinlichkeiten für eine Strategie mit relativistischen Pendeloperatoren (QFT) als$\omega^{co}(G)$. Da die nicht-relativistische QM ein Sonderfall der QFT ist, ist klar, dass eine optimale, auf Pendeloperatoren basierende Strategie mindestens so gut ist wie eine auf optimalen Tensorprodukten basierende Strategie.$\omega^\ast(G) \le \omega^{co}(G)$.
Mein Verständnis von Yuens Beitrag ist das eine Folge davon$MIP^\ast=RE$ist, dass nicht-lokale Spiele für die existieren$\omega^\ast(G) < \omega^{co}(G)$. Konkret, sagt er
Es muss ein Spiel geben$G$, für die sich der Quantenwert vom Wert des Pendeloperators unterscheidet. Dies impliziert jedoch, dass Tsirelsons Problem eine negative Antwort hat, und daher ist die Einbettungsvermutung von Connes falsch.
Ich verstehe das so, dass es eine Klasse von Problemen gibt, bei denen Algorithmen mit Techniken aus der QFT (kommutierende Operatoren) höhere Erfolgswahrscheinlichkeiten haben als Algorithmen mit Techniken aus der nicht-relativistischen QM (Tensorprodukte, Quantenschaltungsformalismus).
Der erste Teil meiner Frage ist, vorausgesetzt, dieser Beweis steht :
- Tut$MIP^\ast=RE$implizieren, dass es eine Reihe von Problemen gibt, die effizienter gelöst werden können, indem der mathematische Formalismus der QFT (kommutierende Operatoren) anstelle des nicht-relativistischen QM-Formalismus (konventionelle Quantenschaltkreise) verwendet wird?
Wenn ich nicht falsch interpretiere, scheint dies direkt aus Yuens Aussagen zu folgen. Wenn dem so ist, ist es möglich, dass es eine Reihe von nicht lokalen Spielen gibt, für die$\omega^\ast(G) < 0.5$und$\omega^{co}(G) > 0.5$? Konkret lautet der zweite Teil meiner Frage:
- Tut$MIP^\ast=RE$implizieren, dass es eine Reihe von Problemen gibt (oder geben könnte), die mit Kommutierungsoperatoren gelöst werden können, die nicht mit Quantenschaltkreisen gelöst werden können, oder wird diese Möglichkeit durch die Universalität des Quantenschaltkreismodells ausgeschlossen?
BEARBEITEN: Henry Yuen hat ein MIP * Wiki für diejenigen erstellt, die daran interessiert sind, diese oder die Komplexitätsklasse besser zu verstehen$MIP^\ast = RE$Ergebnis.
Antworten
Ich weiß nicht, ob das MIP* = RE-Ergebnis und insbesondere die Behauptung, dass es ein nichtlokales Spiel gibt, nicht bekannt ist$G$wo$\omega^*(G) \neq \omega^{co}(G)$, hat irgendwelche algorithmischen Implikationen für Quantencomputer. Hier gibt es ein paar Dinge zu sagen.
Das MIP* = RE-Ergebnis bezieht sich darauf, welche Rechenprobleme mit nichtlokalen Spielen verifiziert werden können , im Gegensatz dazu, was durch nichtlokale Spiele gelöst werden kann (ich bin mir sowieso nicht sicher, was das bedeuten würde!). Die Unterscheidung zwischen Verifizieren und Lösen hat folgenden Grund: In einem nichtlokalen Spiel nehmen wir an, dass Alice und Bob auf magische Weise die Antwort auf das Problem kennen (also nehmen wir an, dass sie jedes Rechenproblem sofort lösen können). Ihre Herausforderung besteht nicht darin, es zu lösen, sondern zu beweisenzu einem klassischen polynomiellen Verifizierer kennen sie die Antwort. Nur die Antwort auf etwas zu kennen, bedeutet nicht, dass Sie jemand anderen von der Antwort überzeugen können. Ob Alice und Bob Korrelationen aus dem Tensorprodukt-Framework oder dem Pendeloperator-Framework verwenden können, wirkt sich darauf aus, was sie dem Verifizierer beweisen können. MIP* = RE zeigt, dass Alice und Bob mit Tensorproduktkorrelationen beweisen können, dass sie wissen, dass eine Turingmaschine irgendwann anhält. Dies ist etwas, was nicht möglich ist, wenn Alice und Bob die Korrelationen der Pendeloperatoren teilen; daher unterscheidet sich das Pendeloperatormodell vom Tensorproduktmodell.
Das zweite, was ich erwähnen wollte, ist, dass es eine interessante Frage ist, ob man ein Modell der Quantenberechnung definieren kann, das über Pendeloperatoren und unendlich dimensionale Systeme spricht. Es scheint, dass Cleve et al. versucht haben, ein Modell dafür zu entwickeln, etwas, das sie das C*-Circuit-Modell nennen:https://arxiv.org/pdf/1811.12575.pdf. Das könnte Sie interessieren.