Recursos para a complexidade da comunicação quântica

Recentemente, eu vim a conhecer esse interessante tópico da " complexidade da comunicação ". Em palavras simples, a Wikipedia define como:

Na ciência da computação teórica, a complexidade da comunicação estuda a quantidade de comunicação necessária para resolver um problema quando a entrada para o problema é distribuída entre duas ou mais partes. Foi introduzido por Andrew Yao em 1979, que investigou o seguinte problema envolvendo duas partes separadas, tradicionalmente chamadas Alice e Bob. Alice recebe uma sequência de n bits e Bob outra sequência de bits , e o objetivo é que um deles (digamos, Bob) calcule uma determinada função com a menor quantidade de comunicação entre eles. Obviamente, eles sempre podem ter sucesso ao receber Alice enviando toda a sequência de n bits para Bob, que calcula a função$x$$n$$y$$f(x,y)$$f$, mas a idéia aqui é encontrar maneiras inteligentes de calcular com menos de n bits de comunicação. Observe que, na complexidade da comunicação, não estamos preocupados com a quantidade de computação realizada por Alice ou Bob, nem com o tamanho da memória usada.$f$

Agora, eu estava revisando as duas primeiras páginas deste artigo: " Quantum Communication Complexity (A Survey) - Brassard ". Aparentemente, parece que se as partes que não estão se comunicando estão emaranhadas anteriormente, mais bits de informação podem ser comunicados do que no caso clássico. O jornal parece bom, e então vou ler mais. No entanto, existem outros documentos ou textos importantes que são "leituras obrigatórias" ao aprender sobre a "complexidade da comunicação quântica"? (Estou mais interessado no lado teórico / algorítmico)

Para uma revisão do assunto, consulte este artigo: "Não localidade e complexidade da comunicação" https://arxiv.org/abs/0907.3584

Um avanço recente que não é coberto nessa pesquisa são as folhas de dicas . Vejo,

Separações na complexidade da comunicação usando folhas de dicas e complexidade da informação ; Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee e Miklos Santha; arXiv: 1605.01142 [quant-ph]

Pode ser uma boa idéia se familiarizar primeiro com a estrutura da cábula.

Separações na complexidade da consulta usando folhas de dicas ; Scott Aaronson, Shalev Ben-David, Robin Kothari; arXiv: 1511.01937 [quant-ph]

Pessoalmente, gosto de pensar na complexidade da consulta como um todo, em vez de me especializar na complexidade da comunicação. Muitos teoremas da complexidade tradicional de consultas podem ser elevados à complexidade da comunicação, e é isso que eles fazem no artigo acima.