Alguma evidência de que Linial, Shraibman, limite inferior da complexidade da comunicação quântica não seja estreita?

11

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 .γ2

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 .γ2γ2γ2

Dan Stahlke
fonte
para completar, você pode fornecer um link para o resultado?
Suresh Venkat
1
@SureshVenkat: adicionei alguns links e contexto.
Dan Stahlke
2
+1. Esse é exatamente o tipo de pergunta que eu não saberia onde perguntar se o CSTheory não existisse.
Robin Kothari

Respostas:

6

γ2γ2

γ2

Marcos Villagra
fonte
Obrigado. Eu não tinha ouvido falar desse aspecto.
precisa saber é o seguinte
γ2
@RobinKothari, sim, está certo. Como o custo da comunicação QCMA é menor que a comunicação BQP, precisamos de um limite superior do QCMA e de um limite inferior do BQP (mais apertado).
Marcos Villagra
ou talvez eles sejam iguais?
Marcos Villagra
1
@MarcosVillagra: Eu não entendo. O complemento de Disjointness está no NP e, portanto, no QCMA. No entanto, a disjunção (ou seu complemento) tem um forte limite inferior exponencial na complexidade da comunicação quântica. Isso não separa BQP e QCMA?
precisa