Até onde eu sei, o limite inferior da norma de fatoração fornecido por Linial e Shraibman é essencialmente o único limite inferior conhecido pela complexidade da comunicação quântica (ou pelo menos, inclui todos os outros). Existe alguma evidência contra esse limite ser apertado?
O limite da norma de fatoração (também chamado de limite ) de que falo é o Teorema 13 de Linial, Shraibman 2008 . De fato, esse limite decorre da redução da complexidade da comunicação quântica ao viés em um jogo de XOR para dois jogadores Degorre, et al. 2008 . Por esse motivo, pode-se esperar um péssimo limite, já que o jogo XOR nem tem nada a ver com comunicação. Para os impacientes, uma breve visão geral é fornecida em alguns slides por Troy Lee .
O texto de introdução de Jain, Klauck 2010, diz que as técnicas da teoria da informação podem oferecer alguma competição, mas não se sabe se elas ultrapassam o limite . Assim, parece que, pelo menos há alguns anos, γ 2 era a melhor técnica. Mas eu gostaria de saber se existe mesmo um exemplo específico de uma função que se acredita ter uma complexidade de comunicação quântica muito maior que o limite γ 2 .
fonte
Respostas:
fonte