On the Capacity of Vector Linear Computation over a Noiseless Quantum Multiple Access Channel with Entangled Transmitters

Network function computation is an active topic in network coding, with much recent progress for linear (over a finite field) computations over broadcast (LCBC) and multiple access (LCMAC) channels. Over a quantum multiple access channel (QMAC) with quantum-entanglement shared among transmitters, the linear computation problem (LC-QMAC) is non-trivial even when the channel is noiseless, because of the challenge of optimally exploiting transmit-side entanglement through distributed coding. Given an arbitrary linear function of data streams defined in a finite field ${\mathbb{F}}_d$, the LC-QMAC problem seeks the optimal communication cost (minimum number of qudits that need to be sent by the transmitters to the receiver, per computation instance) over a noise-free QMAC, when the independent input data streams originate at the corresponding transmitters, who share quantum entanglement in advance. As our main result, we fully solve this problem for $K=3$ transmitters ($K\ge 4$ settings remain open). Coding schemes based on the $N$-sum box protocol (along with time-sharing and batch-processing) are shown to be information theoretically optimal in all cases.