Des preuves que Linial, Shraibman limite inférieure sur la complexité de la communication quantique n'est pas serrée?

11

Pour autant que je sache, la borne inférieure de la norme de factorisation donnée par Linial et Shraibman est essentiellement la seule borne inférieure connue pour la complexité de la communication quantique (ou du moins elle subsume toutes les autres). Y a-t-il des preuves que cette limite n'est pas stricte?

La borne de normalisation de factorisation (également appelée borne ) dont je parle est le théorème 13 de Linial, Shraibman 2008 . En fait, cette limite découle d'une réduction de la complexité de la communication quantique au biais dans un jeu XOR à 2 joueurs Degorre, et al. 2008 . Pour cette raison, on pourrait s'attendre à ce que ce soit une mauvaise liaison, car le jeu XOR n'a même rien à voir avec la communication. Pour les impatients, un bref aperçu est donné dans quelques diapositives de Troy Lee .γ2

Le texte d'introduction de Jain, Klauck 2010 dit que les techniques de théorie de l'information peuvent offrir une certaine concurrence mais on ne sait pas si elles dépassent la borne . Il semblerait donc qu'au moins il y a quelques années, γ 2 était la meilleure technique. Mais j'aimerais savoir s'il existe même un exemple spécifique d'une fonction qui est supposée avoir une complexité de communication quantique bien supérieure à la borne γ 2 .γ2γ2γ2

Dan Stahlke
la source
pour être complet, pouvez-vous fournir un lien vers le résultat?
Suresh Venkat
1
@SureshVenkat: J'ai ajouté quelques liens et contexte.
Dan Stahlke
2
+1. C'est exactement le genre de question que je ne saurais pas où poser si CSTheory n'existait pas.
Robin Kothari

Réponses:

6

γ2γ2

γ2

Marcos Villagra
la source
Je vous remercie. Je n'avais pas entendu parler de cet aspect.
Dan Stahlke
γ2
@RobinKothari, oui, c'est vrai. Parce que le coût de la communication QCMA est inférieur à celui de la communication BQP, nous avons besoin d'une borne supérieure QCMA et d'une borne inférieure BQP (plus serrée).
Marcos Villagra
ou peut-être sont-ils les mêmes?
Marcos Villagra
1
@MarcosVillagra: Je ne comprends pas. Le complément de Disjointness est en NP, et donc en QCMA. Cependant, la disjonction (ou son complément) a une forte limite exponentielle inférieure dans la complexité de la communication quantique. N'est-ce pas séparé BQP et QCMA?
Robin Kothari