Communication Efficiency of Summation over a Quantum Erasure MAC with Replicated Inputs

Abstract

The quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC). \(K\) messages are distributed across \(S\) servers so that each server knows a subset of the messages. Each server \(s\in[S]\) sends a quantum subsystem \(\mathcal{Q}_s\) to the receiver who computes the sum of the messages. The download cost from Server \(s\in [S]\) is the logarithm of the dimension of \(\mathcal{Q}_s\). The rate \(R\) is defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. In the symmetric setting with \(K= {S \choose \alpha} \) messages where each message is replicated among a unique subset of \(\alpha\) servers, and the answers from any \(\beta\) servers may be erased, the rate achieved is \(R= \max\left\{ \min \left\{ \frac{2(\alpha-\beta)}{S}, 1-\frac{2\beta}{S} \right\}, \frac{\alpha-\beta}{S} \right\}\), which is shown to be optimal when \(S\geq 2\alpha\).