Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2304.10792 · Physical Review A

Nonlocal and quantum advantages in network coding for multiple access channels

Jiyoung Yun, Seung-Hyun Nam, Hyun-Young Park, Ashutosh Rai, Si-Hyeon Lee, Joonwoo Bae

Published Apr 1, 2026• 3 citations
arXivHTMLPDF

Abstract

In this work, we consider two-sender, one-receiver communication over a discrete memoryless multiple-access channel without feedback, where two senders may cooperate on channel coding by using preshared resources, such as shared randomness, quantum states and measurements, or nonlocal correlations. We present the capacity region when senders employ cooperative encoding with quantum and nonlocal resources, extending beyond shared randomness, and derive a sum rate that serves as a lower bound to the sum capacity; the lower bound is computable by exploiting specific strategies. We also compute the sum capacities for two instances. One is when senders apply local resources for cooperative encoding. The other is when senders exploit nonclassical resources for encoding against channels constructed by referring to nonlocal games; in this way, correlated noise other than independent errors occurs on code words. Comparing the exact sum capacities and lower bounds, we show that nonlocal and quantum resources for cooperative encoding enable higher sum capacities over local ones. The Clauser-Horne-Shimony-Holt and magic square games are considered for constructing multiple-access channels, and we demonstrate the usefulness of nonlocal and quantum resources to achieve higher-sum capacities.

DOI
10.1103/b4q8-bzcq

Related papers

Multiple-Access Channel Coding With Non-Signaling Correlations

Omar Fawzi, Paul Fermé

We address the problem of coding for classical multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of classical point-to-point channels. However, it was recently observed that one can construct MACs from two-player nonlocal games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity. In this work, we make several contributions towards understanding the capacity region for MACs with the assistance of non-signaling correlations between the parties. We develop a linear program computing the optimal success probability for coding over$n$copies of a MAC$W$with size growing polynomially in$n$. Solving this linear program allows us to achieve inner bounds for MACs. Applying this method to the binary adder channel, we show that using non-signaling assistance, the sum-rate$\frac {\log _{2}(72)}{4} \simeq 1.5425$can be reached even with zero error, which beats the maximum sum-rate capacity of 1.5 in the unassisted case. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity. Complementing these achievability results, we give an outer bound on the non-signaling assisted capacity region that has the same expression as the unassisted region except that the channel inputs are not required to be independent. Finally, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.

arXiv:2206.10968•IEEE Transactions on Information Theory•Aug 8, 2023•13 citations

Nonlocal Network Coding in Interference Channels

Jiyoung Yun, Ashutosh Rai, Joonwoo Bae

In a network, a channel introduces correlations to the parties that aim to establish a communication protocol. We present a framework of nonlocal network coding by exploiting a Bell scenario and show the usefulness of nonlocal and quantum resources in network coding. Two-sender and two-receiver interference channels are considered, for which network coding is characterized by two-input and four-outcome Bell scenarios. It is shown that nonsignaling correlations lead to strictly higher channel capacities than quantum correlations in general. This also holds true for quantum and local correlations: network coding with quantum resources shows a strictly higher channel capacity than local ones. It turns out, however, that more nonlocality does not necessarily imply a higher channel capacity. The framework can be generally applied to network communication protocols.

arXiv:2003.11867•Physical Review Letters•Oct 8, 2020•13 citations

On the Separation of Correlation-Assisted Sum Capacities of Multiple Access Channels

Akshay Seshadri, Felix Leditzky, Vikesh Siddhu +1 more

The capacity of a channel characterizes the maximum rate at which information can be transmitted through the channel asymptotically faithfully. For a channel with multiple senders and a single receiver, computing its sum capacity is possible in theory, but challenging in practice because of the nonconvex optimization involved. To address this challenge, we investigate three topics in our study. In the first part, we study the sum capacity of a family of multiple access channels (MACs) obtained from nonlocal games. For any MAC in this family, we obtain an upper bound on the sum rate that depends only on the properties of the game when allowing assistance from an arbitrary set of correlations between the senders. This approach can be used to prove separations between sum capacities when the senders are allowed to share different sets of correlations, such as classical, quantum or no-signalling correlations. We also construct a specific nonlocal game to show that the approach of bounding the sum capacity by relaxing the nonconvex optimization can give arbitrarily loose bounds. Owing to this result, in the second part, we study algorithms for non-convex optimization of a class of functions we call Lipschitz-like functions. This class includes entropic quantities, and hence these results may be of independent interest in information theory. Subsequently, in the third part, we show that one can use these techniques to compute the sum capacity of an arbitrary two-sender MACs to a fixed additive precision in quasi-polynomial time. We showcase our method by efficiently computing the sum capacity of a family of two-sender MACs for which one of the input alphabets has size two. Furthermore, we demonstrate with an example that our algorithm may compute the sum capacity to a higher precision than using the convex relaxation.

arXiv:2205.13538•IEEE Transactions on Information Theory•May 15, 2023•11 citations

Beating the Sum-Rate Capacity of the Binary Adder Channel with Non-Signaling Correlations

Omar Fawzi, Paul Fermé

We address the problem of coding for multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity.Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of $\frac{{{{\log }_2}(72)}}{4} \simeq 1.5425$ can be reached with zero error, which beats the maximum classical sum-rate capacity of $\frac{3}{2}$.In order to achieve this, we show that efficient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a finite number of copies of a multiple-access channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•10 citations

Non-local network coding in interference channels

Jiyoung Yun, Ashutosh Rai, Joonwoo Bae

Network information theory establishes communication protocols among multiple senders and multiple receivers in the presence of correlations introduce noise over a network. We here present a framework of non-local network coding of multiple senders whereby network communication capacities improve over their classical counterparts. The framework exploits a Bell scenario and shows the usefulness of non-local and quantum resources in network information theory. Two-sender and two-receiver interference channels are considered in particular, for which network coding is characterized by two-input and four-outcome Bell scenarios. Resources for the network coding are classified It is shown that non-signaling (quantum) correlations lead to strictly higher channel capacities in general than quantum (local) correlations. It is also shown that, however, more non-locality does not necessarily imply a higher channel capacity. The framework can be generally applied to network communication protocols.

Quantum Communications and Quantum Imaging•Jul 30, 2021•0 citations

Enhancing Sum Capacity via Quantum and No-Signaling Cooperation Between Transmitters

Seung-Hyun Nam, Hyun-Young Park, Jiyoung Yun +3 more

We consider communication over discrete memoryless interference channels or multiple access channels without feedback, where transmitters exploit classical, quantum, or no-signaling cooperation. Previous works have shown that, for channels associated with pseudo-telepathy games, quantum or no-signaling cooperation can increase the sum capacity. However, a full characterization of channels admitting such an improvement remains open. Motivated by common features of previously studied examples, we propose a broader class of game-induced channels. In these channels, each input is a question-answer pair from a nonlocal game. When the inputs satisfy the game's winning condition, the channel has lower conditional output uncertainty, and the channel decomposes into parallel weakly symmetric subchannels with a unique capacity-achieving input distribution. We show that, for this class, quantum or no-signaling cooperation strictly increases the sum capacity whenever the associated game is a quantum or no-signaling pseudo-telepathy game, respectively. The proposed class recovers several previously studied channels and includes new examples.

arXiv:2509.08219•IEEE Journal on Selected Areas in Communications•Jan 1, 2026•0 citations
In this work, we consider two-sender, one-receiver communication over a discrete memoryless multiple-access channel without feedback, where two senders may cooperate on channel coding by using preshared resources, such as shared randomness, quantum states and measurements, or nonlocal correlations. We present the capacity region when senders employ cooperative encoding with quantum and nonlocal resources, extending beyond shared randomness, and derive a sum rate that serves as a lower bound to the sum capacity; the lower bound is computable by exploiting specific strategies. We also compute the sum capacities for two instances. One is when senders apply local resources for cooperative encoding. The other is when senders exploit nonclassical resources for encoding against channels constructed by referring to nonlocal games; in this way, correlated noise other than independent errors occurs on code words. Comparing the exact sum capacities and lower bounds, we show that nonlocal and quantum resources for cooperative encoding enable higher sum capacities over local ones. The Clauser-Horne-Shimony-Holt and magic square games are considered for constructing multiple-access channels, and we demonstrate the usefulness of nonlocal and quantum resources to achieve higher-sum capacities.
We address the problem of coding for classical multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of classical point-to-point channels. However, it was recently observed that one can construct MACs from two-player nonlocal games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity. In this work, we make several contributions towards understanding the capacity region for MACs with the assistance of non-signaling correlations between the parties. We develop a linear program computing the optimal success probability for coding overnnncopies of a MACWWWwith size growing polynomially innnn. Solving this linear program allows us to achieve inner bounds for MACs. Applying this method to the binary adder channel, we show that using non-signaling assistance, the sum-ratelog⁡2(72)4≃1.5425\frac {\log _{2}(72)}{4} \simeq 1.54254log2​(72)​≃1.5425can be reached even with zero error, which beats the maximum sum-rate capacity of 1.5 in the unassisted case. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity. Complementing these achievability results, we give an outer bound on the non-signaling assisted capacity region that has the same expression as the unassisted region except that the channel inputs are not required to be independent. Finally, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.
In a network, a channel introduces correlations to the parties that aim to establish a communication protocol. We present a framework of nonlocal network coding by exploiting a Bell scenario and show the usefulness of nonlocal and quantum resources in network coding. Two-sender and two-receiver interference channels are considered, for which network coding is characterized by two-input and four-outcome Bell scenarios. It is shown that nonsignaling correlations lead to strictly higher channel capacities than quantum correlations in general. This also holds true for quantum and local correlations: network coding with quantum resources shows a strictly higher channel capacity than local ones. It turns out, however, that more nonlocality does not necessarily imply a higher channel capacity. The framework can be generally applied to network communication protocols.
The capacity of a channel characterizes the maximum rate at which information can be transmitted through the channel asymptotically faithfully. For a channel with multiple senders and a single receiver, computing its sum capacity is possible in theory, but challenging in practice because of the nonconvex optimization involved. To address this challenge, we investigate three topics in our study. In the first part, we study the sum capacity of a family of multiple access channels (MACs) obtained from nonlocal games. For any MAC in this family, we obtain an upper bound on the sum rate that depends only on the properties of the game when allowing assistance from an arbitrary set of correlations between the senders. This approach can be used to prove separations between sum capacities when the senders are allowed to share different sets of correlations, such as classical, quantum or no-signalling correlations. We also construct a specific nonlocal game to show that the approach of bounding the sum capacity by relaxing the nonconvex optimization can give arbitrarily loose bounds. Owing to this result, in the second part, we study algorithms for non-convex optimization of a class of functions we call Lipschitz-like functions. This class includes entropic quantities, and hence these results may be of independent interest in information theory. Subsequently, in the third part, we show that one can use these techniques to compute the sum capacity of an arbitrary two-sender MACs to a fixed additive precision in quasi-polynomial time. We showcase our method by efficiently computing the sum capacity of a family of two-sender MACs for which one of the input alphabets has size two. Furthermore, we demonstrate with an example that our algorithm may compute the sum capacity to a higher precision than using the convex relaxation.
We address the problem of coding for multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity.Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of log⁡2(72)4≃1.5425\frac{{{{\log }_2}(72)}}{4} \simeq 1.54254log2​(72)​≃1.5425 can be reached with zero error, which beats the maximum classical sum-rate capacity of 32\frac{3}{2}23​.In order to achieve this, we show that efficient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a finite number of copies of a multiple-access channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.
Network information theory establishes communication protocols among multiple senders and multiple receivers in the presence of correlations introduce noise over a network. We here present a framework of non-local network coding of multiple senders whereby network communication capacities improve over their classical counterparts. The framework exploits a Bell scenario and shows the usefulness of non-local and quantum resources in network information theory. Two-sender and two-receiver interference channels are considered in particular, for which network coding is characterized by two-input and four-outcome Bell scenarios. Resources for the network coding are classified It is shown that non-signaling (quantum) correlations lead to strictly higher channel capacities in general than quantum (local) correlations. It is also shown that, however, more non-locality does not necessarily imply a higher channel capacity. The framework can be generally applied to network communication protocols.
We consider communication over discrete memoryless interference channels or multiple access channels without feedback, where transmitters exploit classical, quantum, or no-signaling cooperation. Previous works have shown that, for channels associated with pseudo-telepathy games, quantum or no-signaling cooperation can increase the sum capacity. However, a full characterization of channels admitting such an improvement remains open. Motivated by common features of previously studied examples, we propose a broader class of game-induced channels. In these channels, each input is a question-answer pair from a nonlocal game. When the inputs satisfy the game's winning condition, the channel has lower conditional output uncertainty, and the channel decomposes into parallel weakly symmetric subchannels with a unique capacity-achieving input distribution. We show that, for this class, quantum or no-signaling cooperation strictly increases the sum capacity whenever the associated game is a quantum or no-signaling pseudo-telepathy game, respectively. The proposed class recovers several previously studied channels and includes new examples.