Playing Games with Multiple Access Channels

Abstract

Communication networks have multiple users, each sending and receiving messages. A multiple access channel (MAC) models multiple senders transmitting to a single receiver, such as the uplink from many mobile phones to a single base station. The optimal performance of a MAC is quantified by a capacity region of simultaneously achievable communication rates. We study the two-sender classical MAC, the simplest and best-understood network, and find a surprising richness in both a classical and quantum context. First, we find that quantum entanglement shared between senders can substantially boost the capacity of a classical MAC. Second, we find that optimal performance of a MAC with bounded-size inputs may require unbounded amounts of entanglement. Third, determining whether a perfect communication rate is achievable using finite-dimensional entanglement is undecidable. Finally, we show that evaluating the capacity region of a two-sender classical MAC is in fact NP-hard.

arXiv comment25 pages, 7 figures, comments welcome! v2: identical to published version

References in corpus (10)

• Entanglement-Assisted Classical Capacity of Noisy Quantum Channels
• Quantum Pseudo-Telepathy
• Improving zero-error classical communication with entanglement
• Entanglement-Assisted Capacity of Quantum Multiple-Access Channels
• Capacity Theorems for Quantum Multiple Access Channels: Classical-Quantum and Quantum-Quantum Capacity Regions
• Entanglement-Enhanced Classical Communication over a Noisy Classical Channel
• Quantum and Super-quantum enhancements to two-sender, two-receiver channels
• Nonadditivity effects in classical capacities of quantum multiple-access channels
• Entanglement in non-local games and the hyperlinear profile of groups
• A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities

Cited by in corpus (18)

• Universal Limitations on Quantum Key Distribution over a Network
• Entanglement-Enabled Communication
• Entanglement-assisted capacity regions and protocol designs for quantum multiple-access channels
• Quantum Broadcast Channels with Cooperating Decoders: An Information-Theoretic Perspective on Quantum Repeaters
• On entanglement assistance to a noiseless classical channel
• Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
• Non-Local Network Coding in Interference Channels
• Multiple-Access Channel Coding with Non-Signaling Correlations
• On the separation of correlation-assisted sum capacities of multiple access channels
• Equivalence between face nonsignaling correlations, full nonlocality, all-versus-nothing proofs, and pseudotelepathy
• Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks
• The rank of contextuality
• Building Multiple Access Channels with a Single Particle
• Classical communication cost of a bipartite quantum channel assisted by non-signalling correlations
• Secure communication over generalised quantum multiple access channels
• Nonlocal and quantum advantages in network coding for multiple access channels
• Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?
• The Quantum Multiple-Access Channel with Cribbing Encoders