Limite de Gottesman-Knill sobre a Complexidade de Comunicação em Uma Direção: Rastreando a Vantagem Quântica até a Magia

Um resultado recente influente de Frenkel e Weiner estabelece que, na presença de aleatoriedade compartilhada (SR), qualquer correlação de entrada-saída, com uma entrada clássica fornecida a uma parte e uma saída clássica produzida por uma parte distante, alcançável com um sistema quântico d-dimensional, pode sempre ser reproduzido por um sistema clássico d-dimensional. Em contraste, sistemas quânticos são conhecidos por oferecer vantagens em tarefas de complexidade de comunicação, que consideram uma variável de entrada adicional para a segunda parte. Aqui, mostramos que, na presença de SR, qualquer protocolo de complexidade de comunicação em uma direção implementado usando um sistema quântico de dimensão prima pode sempre ser simulado exatamente por um sistema clássico da mesma dimensão, sempre que protocolos quânticos sejam restritos a preparações de estados estabilizadores e medições estabilizadoras. Em analogia direta com o teorema de Gottesman-Knill em computação quântica, que atribui vantagem quântica a recursos não estabilizadores (ou mágicos), nosso resultado identifica os mesmos recursos como essenciais para realizar vantagem quântica em complexidade de comunicação em uma direção. Apresentamos ainda tarefas explícitas onde 'mágica mínima' é suficiente para oferecer uma vantagem quântica provável, sublinhando o uso eficiente de tais recursos em complexidade de comunicação.