On the separation of correlation-assisted sum capacities of multiple access channels

Akshay Seshadri, Felix Leditzky, Vikesh Siddhu, Graeme Smith

Introduction

In information theory, the Multiple Access Channel (MAC) serves as a fundamental model for scenarios where multiple senders transmit information to a single receiver simultaneously. A central challenge in this field is determining the "sum capacity"—the maximum total data rate achievable across the channel. Unlike simple point-to-point communication, calculating the sum capacity for MACs is a notoriously difficult non-convex optimization problem. In fact, finding the exact solution has been proven to be NP-hard, leading many researchers to rely on "convex relaxation" shortcuts to approximate the answer.

This paper investigates the fundamental accuracy of these approximations and introduces a robust new framework for computing capacities with guaranteed precision. By leveraging nonlocal games and a new class of mathematical functions, the authors provide a clearer picture of how classical, quantum, and no-signalling correlations impact communication rates.

The Risks of Convex Relaxation

To bypass the non-convexity of MAC optimization, researchers often use a relaxed version of the problem that is easier to solve. However, the authors prove that this shortcut can be dangerously inaccurate. Through the construction of a specific "Signalling Game," they demonstrate that the gap between the true sum capacity and the convex relaxation can grow infinitely large as the number of possible inputs increases. This finding suggests that existing literature relying solely on relaxed bounds may be significantly overestimating channel capacities.

A New Framework: Lipschitz-like Optimization

A major theoretical breakthrough in this work is the identification of "Lipschitz-like" functions. While standard Shannon and von Neumann entropies are not Lipschitz-continuous—meaning they change too rapidly near zero for standard global optimization tools—the authors prove they belong to this new, broader class.

This realization allows the application of global optimization algorithms that were previously thought to be incompatible with information theory. Specifically, the authors adapt the Piyavskii-Shubert algorithm and utilize dense curves (space-filling curves) to map high-dimensional non-convex problems into manageable one-dimensional ones. This approach enables the computation of capacities to a fixed precision $\epsilon$ with theoretical guarantees in quasi-polynomial time.

Quantum Boosts and Correlation Hierarchy

The paper provides a rigorous hierarchy for sum capacities based on the type of assistance available to the senders:

$$S_{classical} \leq S_{quantum} \leq S_{no-signalling} \leq C_{relaxed}$$

By applying their high-precision algorithm to landmark problems like the Magic Square Game, the authors discovered that the benefits of quantum entanglement (shared entanglement between senders) are much larger than previously thought. Their analysis shows that entanglement increases the sum rate by at least 4.7%, nearly five times the 0.9% boost reported in prior literature. This suggests that the potential for "quantum assistance" in communication networks has been significantly undervalued.

Algorithmic Performance

Beyond theoretical proofs, the authors demonstrated the practical utility of their methods. In numerical tests for two-sender MACs, their modified Piyavskii-Shubert algorithm reached target precision levels 250 times faster than standard grid-search methods. Furthermore, the algorithm successfully identified true capacities in cases where convex solvers simply overshot the value, providing a more reliable benchmark for channel performance.

Limitations and Future Directions

While the "dense curve" approach is highly effective for small dimensions, it still faces challenges with exponential scaling as the number of senders or the size of input alphabets grows. Currently, the method is most efficient for two-sender MACs with relatively small input sets.

Future research will focus on:

  • Developing scalable algorithms for high-dimensional MACs.
  • Exploring randomized algorithms to potentially speed up convergence.
  • Applying the "Lipschitz-like" framework to other non-convex challenges, such as determining the private capacity of quantum channels.

Summary updated

BibTeX
@article{seshadri2023separation,
  author = {Akshay Seshadri and Felix Leditzky and Vikesh Siddhu and Graeme Smith},
  title = {{On the separation of correlation-assisted sum capacities of multiple access channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
  doi = {10.1109/tit.2023.3274434},
}
Figure