Beating the Sum-Rate Capacity of the Binary Adder Channel with Non-Signaling Correlations

We address the problem of coding for multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity. Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of $\frac{\log_2(72)}{4} \simeq 1.5425$ can be reached with zero error, beating the maximum classical sum-rate capacity of $\frac{3}{2}$. Furthermore, we show that this capacity increase persists if a small amount of noise is added to the channel. In order to achieve this, we show that efficient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a finite number of copies of a multiple-access channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.