Hasta donde sé, la norma de factorización del límite inferior dada por Linial y Shraibman es esencialmente el único límite inferior conocido para la complejidad de la comunicación cuántica (o al menos subsume todos los demás). ¿Hay alguna evidencia en contra de que este límite sea estricto?
La norma de factorización ligada (también llamada ligada ) de la que hablo es el Teorema 13 de Linial, Shraibman 2008 . De hecho, este límite se deriva de una reducción de la complejidad de la comunicación cuántica al sesgo en un juego XOR de 2 jugadores Degorre, et al. 2008 . Por esta razón, podría esperarse que sea un pésimo límite ya que el juego XOR ni siquiera tiene nada que ver con la comunicación. Para los impacientes, Troy Lee ofrece una breve descripción general en algunas diapositivas .
El texto de introducción de Jain, Klauck 2010 dice que la información de las técnicas teóricas pueden ofrecer cierta competencia, pero no se sabe si estos golpearon la ruedas. Parece que, al menos desde hace unos años, γ 2 era la mejor técnica. Pero me gustaría saber si hay incluso un ejemplo específico de una función que se cree que tiene la comunicación cuántica complejidad mucho mayor que la γ 2 ruedas.
fuente
Respuestas:
fuente