Gibt es Hinweise darauf, dass die Untergrenze von Linial und Shraibman für die Komplexität der Quantenkommunikation nicht eng ist?

11

Soweit ich weiß, ist die von Linial und Shraibman gegebene Untergrenze der Faktorisierungsnorm im Wesentlichen die einzige Untergrenze, die für die Komplexität der Quantenkommunikation bekannt ist (oder zumindest alle anderen subsumiert). Gibt es Beweise dafür, dass diese Bindung eng ist?

Die Faktorisierungsnorm (auch als Grenze bezeichnet), von der ich spreche, ist Satz 13 von Linial, Shraibman 2008 . Tatsächlich ergibt sich diese Grenze aus einer Verringerung der Komplexität der Quantenkommunikation auf die Verzerrung in einem 2-Spieler-XOR-Spiel von Degorre et al. 2008 . Aus diesem Grund ist zu erwarten, dass es sich um eine schlechte Sache handelt, da das XOR-Spiel nicht einmal etwas mit Kommunikation zu tun hat. Für Ungeduldige gibt Troy Lee in einigen Folien einen kurzen Überblick .γ2

Der Einführungstext von Jain, Klauck 2010 besagt, dass informationstheoretische Techniken eine gewisse Konkurrenz bieten können, aber es ist nicht bekannt, ob diese die -Grenze überschreiten. Es scheint also, dass γ 2 zumindest vor einigen Jahren die beste Technik war. Aber ich würde gerne wissen, ob es überhaupt ein spezifisches Beispiel für eine Funktion gibt, von der angenommen wird, dass sie eine Quantenkommunikationskomplexität aufweist, die viel größer ist als die γ 2 -Grenze.γ2γ2γ2

Dan Stahlke
quelle
Können Sie der Vollständigkeit halber einen Link zum Ergebnis angeben?
Suresh Venkat
1
@ SureshVenkat: Ich habe einige Links und Kontext hinzugefügt.
Dan Stahlke
2
+1. Dies ist genau die Art von Frage, die ich nicht stellen würde, wenn CSTheory nicht existiert.
Robin Kothari

Antworten:

6

γ2γ2

γ2

Marcos Villagra
quelle
Vielen Dank. Ich hatte von diesem Aspekt noch nichts gehört.
Dan Stahlke
γ2
@RobinKothari, ja, das stimmt. Da die QCMA-Kommunikationskosten niedriger sind als die BQP-Kommunikation, benötigen wir eine QCMA-Obergrenze und eine (engere) BQP-Untergrenze.
Marcos Villagra
oder vielleicht sind sie gleich?
Marcos Villagra
1
@ MarcosVillagra: Ich verstehe nicht. Das Komplement der Disjunktheit ist in NP und daher in QCMA. Disjunktheit (oder ihr Komplement) hat jedoch eine starke exponentielle Untergrenze in der Komplexität der Quantenkommunikation. Trennt das nicht BQP und QCMA?
Robin Kothari