Playing games with multiple access channels

The paper investigates how shared quantum entanglement affects the classical two-sender multiple access channel (MAC), and examines the computational complexity of characterizing MAC capacity regions. Classically, the MAC capacity region admits a single-letter characterization (Ahlswede and Liao), suggesting computability. However, the authors question whether this implies practical or efficient computability and whether quantum resources can alter classical capacities in multiuser settings (in contrast to point-to-point classical communication, where entanglement provides no advantage). The work aims to demonstrate: (i) entanglement-assisted advantages in classical MACs, (ii) the necessity of unbounded entanglement to attain ideal rates for bounded input alphabets in some MACs, (iii) undecidability of achieving perfect rates with finite-dimensional entanglement, and (iv) NP-hardness of deciding membership in a MAC’s unassisted capacity region.

The study builds on Shannon’s information theory and the classical MAC capacity region established via single-letter characterizations by Ahlswede (1971) and Liao (1972). It contrasts with single-sender scenarios where entanglement assistance does not improve classical capacity. Prior related constructions connect channels to nonlocal games (e.g., Quek and Shor for interference channels using CHSH; unpublished ideas by Nötzel and Winter). Quantum pseudo-telepathy games such as the magic square game provide separations between classical and quantum strategies. Linear system games (Cleve and Mittal) and results by Slofstra and Vidick show perfect quantum strategies may require unbounded entanglement; Slofstra further showed the set of quantum correlations is not closed, implying undecidability phenomena. Complexity-theoretic underpinnings leverage Håstad’s hardness results and PCP theorems to derive NP-hardness for approximating certain game outcomes, which translate to hardness of MAC capacity region membership.

• Channel-from-game construction: Define a classical two-sender MAC N_G from a nonlocal game G = (X1, X2, Y1, Y2, W). The senders’ inputs are (x1, y1) and (x2, y2); the output is the question pair (x1, x2). If the play (x1, y1, x2, y2) satisfies the winning condition W, the channel outputs (x1, x2) noiselessly; otherwise it outputs a uniformly random pair in X1 × X2. Formally, N_G((x1, y1), (x2, y2)) = (x1, x2) if win, else a uniform random element of X1 × X2.
• Capacity region framework: Use the standard MAC capacity constraints for product inputs AB on A × B: R1 ≤ I(A; Z|B), R2 ≤ I(B; Z|A), R1 + R2 ≤ I(AB; Z). Instantiate A = X1Y1, B = X2Y2 for N_G.
• Sum-rate bound via losing probability: Show I(X1Y1X2Y2; Z) = H(Z) − Pl (log|X1| + log|X2|), where Pl is the probability of losing G under the chosen product distribution and answering strategy. This yields Theorem 1: if G has no perfect strategy with the allowed resources, then R1 + R2 is strictly bounded away from log|X1| + log|X2|.
• Entanglement-assisted separation: Apply the framework to a pseudo-telepathy game with perfect quantum but imperfect classical strategies (magic square). Theorem 1 bounds classical sum rate below 2 log 3, whereas a perfect quantum strategy with shared entanglement achieves R1 = R2 = log 3.
• Unbounded entanglement requirement: Use linear system games G_LS. For a specific instance G_SV (Slofstra–Vidick), any finite local dimension d entails nonzero losing probability; thus the d-entanglement-assisted achievable region is bounded away from (log m, log n). As d → ∞, winning probability approaches 1, and achievable rates approach the ideal sum log m + log n.
• Undecidability: Slofstra showed undecidability of whether a linear system game admits a perfect finite-dimensional quantum strategy. Translating via N_G implies undecidability of whether the entanglement-assisted achievable region contains (log m, log n) for N_{G_LS}.
• NP-hardness (unassisted): Use a nonlocal game version G_H of 3SAT (Håstad). It is NP-hard to distinguish perfect completeness vs. maximal winning probability ≤ 1 − (1 − c)/n for constant c < 1. Map G_H to N_{G_H}. If perfect, senders achieve (log m, log n); otherwise Theorem 1 bounds the sum rate by log m + log n − Ω(1/n^3), yielding NP-hardness of deciding capacity region membership within inverse-cubic precision in n (output alphabet size).

• Theorem 1: If the underlying game G admits no perfect strategy under the available resources, the MAC N_G’s sum rate R1 + R2 is strictly less than log|X1| + log|X2| by a positive margin depending on the losing probability.
• Entanglement-assisted advantage: For the magic square game G_MS, classical strategies have winning probability at most 8/9, yielding an upper bound on the achievable sum rate of 3.13694, strictly below the maximum 2 log 3 ≈ 3.1699. With shared entanglement, a perfect quantum strategy achieves R1 = R2 = log 3, i.e., sum rate 2 log 3.
• Unbounded entanglement may be required: For a linear system game instance G_SV, any fixed finite local dimension d leads to a nonzero losing probability, so the d-entanglement-assisted achievable region for N_{G_SV} is bounded away from (log m, log n). As d increases, achievable rates converge to the ideal sum rate log m + log n, demonstrating that arbitrarily large entanglement can be necessary to realize optimal performance.
• Undecidability: For MACs derived from general linear system games N_{G_LS}, it is undecidable whether the entanglement-assisted achievable region includes (log m, log n) when restricting to finite-dimensional entanglement strategies.
• NP-hardness (unassisted): Determining whether a given rate pair (R1, R2) lies in the unassisted capacity region C(N) of a two-sender classical MAC is NP-hard to within an additive inverse-cubic precision in n (the output alphabet size), via reduction from Håstad’s hardness for a 3SAT-based nonlocal game.

The findings demonstrate a qualitative distinction between point-to-point classical communication (where entanglement assistance does not help) and multiuser MACs, where shared entanglement between senders can strictly enlarge the achievable rate region. The construction N_G ties channel noise directly to the players’ ability to win a nonlocal game, allowing rigorous conversion of game-theoretic limits into information-theoretic bounds. This yields explicit separations (e.g., magic square) and shows that optimal MAC performance can fundamentally hinge on access to arbitrarily large entangled states. On the computational side, despite a single-letter characterization for MAC capacity regions, deciding membership in a capacity region is in general computationally intractable (NP-hard), challenging the notion that single-letter formulas ensure efficient computability. The undecidability result for finite-dimensional entanglement-assisted perfect rates further underscores the profound complexity of entanglement-assisted multiuser communication.

The paper establishes that (i) shared entanglement between senders can strictly increase the achievable rates of a classical MAC, (ii) certain MACs require unbounded entanglement to achieve ideal rates, (iii) determining whether finite-dimensional entanglement suffices to achieve perfect rates is undecidable for a class of channels derived from linear system games, and (iv) deciding membership in the unassisted capacity region of a MAC is NP-hard to within inverse-cubic precision. These results reshape understanding of MACs by coupling nonlocal game performance to channel behavior and by exposing inherent computational barriers. Future research directions include: tightening analytical bounds on sum rates (as numerical evidence suggests larger separations than current theorems guarantee); characterizing the full entanglement-assisted capacity region under general parallel and multipartite strategies (likely requiring regularization and connected to parallel repetition for quantum nonlocal games); exploring scenarios with entanglement shared among senders and the receiver; and developing tight, efficiently computable outer bounds (e.g., via convex relaxations of the rank-1 optimization underlying MAC capacity).

• The sum-rate upper bounds (e.g., Theorem 1) may be loose; numerical investigations suggest larger separations than currently proven.
• Analysis focuses on entanglement shared only between the two senders; potential assistance involving the receiver is not treated.
• The entanglement-assisted achievable region considered arises from measuring identical copies of a single entangled state; more general multipartite or parallel strategies are not fully characterized and may require regularization.
• Results rely on MACs constructed from specific nonlocal games; conclusions about general MACs beyond this construction are indirect.
• Computational hardness and undecidability results are asymptotic/complexity-theoretic and do not yield practical algorithms for arbitrary MACs, further motivating approximation methods.