Playing games with multiple access channels

Felix Leditzky, Mohammad A. Alhejji, Joshua Levin, Graeme Smith

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number1497
JournalNature communications
Volume11
Issue number1
DOIs
StatePublished - Dec 1 2020
Externally publishedYes

ASJC Scopus subject areas

  • Chemistry(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Physics and Astronomy(all)

Fingerprint Dive into the research topics of 'Playing games with multiple access channels'. Together they form a unique fingerprint.

Cite this