skip to main content


Title: 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.

 
more » « less
Award ID(s):
1652560 1734006
NSF-PAR ID:
10153547
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Nature Publishing Group
Date Published:
Journal Name:
Nature Communications
Volume:
11
Issue:
1
ISSN:
2041-1723
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Abstract We solve the entanglement-assisted (EA) classical capacity region of quantum multiple-access channels (MACs) with an arbitrary number of senders. As an example, we consider the bosonic thermal-loss MAC and solve the one-shot capacity region enabled by an entanglement source composed of sender-receiver pairwise two-mode squeezed vacuum states. The EA capacity region is strictly larger than the capacity region without entanglement-assistance. With two-mode squeezed vacuum states as the source and phase modulation as the encoding, we also design practical receiver protocols to realize the entanglement advantages. Four practical receiver designs, based on optical parametric amplifiers, are given and analyzed. In the parameter region of a large noise background, the receivers can enable a simultaneous rate advantage of 82.0% for each sender. Due to teleportation and superdense coding, our results for EA classical communication can be directly extended to EA quantum communication at half of the rates. Our work provides a unique and practical network communication scenario where entanglement can be beneficial. 
    more » « less
  2. We consider evacuation of a group of n ≥ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2√2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR ∈ [2+√5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR ∈ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3. 
    more » « less
  3. Bosonic channels describe quantum-mechanically many practical communication links such as optical, microwave, and radiofrequency. We investigate the maximum rates for the bosonic multiple access channel (MAC) in the presence of thermal noise added by the environment and when the transmitters utilize Gaussian state inputs. We develop an outer bound for the capacity region for the thermal-noise lossy bosonic MAC. We additionally find that the use of coherent states at the transmitters is capacity-achieving in the limits of high and low mean input photon numbers. Furthermore, we verify that coherent states are capacity-achieving for the sum rate of the channel. In the non-asymptotic regime, when a global mean photon-number constraint is imposed on the transmitters, coherent states are the optimal Gaussian state. Surprisingly however, the use of single-mode squeezed states can increase the capacity over that afforded by coherent state encoding when each transmitter is photon number constrained individually. 
    more » « less
  4. A new class of structured codes called quasi group codes (QGCs) is introduced. A QGC is a subset of a group code. In contrast with the group codes, QGCs are not closed under group addition. The parameters of the QGC can be chosen, such that the size of C C is equal to any number between C and C 2 . We analyze the performance of a specific class of QGCs. This class of QGCs is constructed by assigning single-letter distributions to the indices of the codewords in a group code. Then, the QGC is defined as the set of codewords whose index is in the typical set corresponding to these singleletter distributions. The asymptotic performance limits of this class of QGCs are characterized using single-letter information quantities. Corresponding covering and packing bounds are derived. It is shown that the point-to-point channel capacity and optimal rate-distortion function are achievable using QGCs. Coding strategies based on QGCs are introduced for three fundamental multi-terminal problems: the Körner-Marton problem for modulo prime-power sums, computation over the multiple access channel (MAC), and MAC with distributed states. For each problem, a single-letter achievable rate-region is derived. It is shown, through examples, that the coding strategies improve upon the previous strategies based on the unstructured codes, linear codes, and group codes. Index Terms— Quasi structure 
    more » « less
  5. We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for discrete quantum measurement systems with limited classical common randomness. The main coding theorem provides the achievable rate region of a lossy measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an i.i.d. predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination state via an entanglement-breaking channel with limited communication rate and common randomness. 
    more » « less