1 Introduction↩︎

With continued progress toward a quantum internet [1]–[3] likely to make quantum resources increasingly accessible, it is important to understand how these technologies might transform modern society. One promising avenue lies in using distributed quantum resources to substantially enhance the capacity¹ of classical communication networks.

Quantum entanglement is a resource that can be shared among the communication nodes in advance, i.e., prior to the beginning of communication. It is a static (non-signaling) resource [4], i.e., it does not by itself allow any communication. However, it expands the scope of encoding and decoding schemes that can be employed over the classical channel. The transmitting nodes may perform input-dependent local measurements on their respective quantum systems, and determine the symbols to be transmitted on the classical channel based on the classical outcomes of those measurements. Entangled quantum systems can generate non-local correlations in the measurement outcomes. These are correlations that cannot be achieved by classical means such as shared classical randomness. It is natural to explore what capacity gains, if any, are possible from such non-local correlations, i.e., from quantum entanglement assistance, in classical communication networks.

Despite substantial progress [5]–[15], the answer to this question is not yet well understood. The picture that has emerged thus far is not very optimistic. As shown by Bennett et al. [5], in a point-to-point channel there is no capacity gain from quantum entanglement assistance. Among multiuser settings, perhaps the multiple access channel (MAC) has received the most attention [6]–[12]. Although capacity gains from quantum entanglement assistance have been shown in MACs by leveraging pseudotelepathy games [6], [7], the magnitude of the gains found thus far is rather modest, not exceeding \(6\%\) [8]. Beyond the MAC setting the understanding is even more limited. For example, no capacity gain due to quantum entanglement assistance has yet been found for classical broadcast channels [14], [15]. This raises the question: can quantum entanglement assistance ever produce large gains in the Shannon capacity of classical communication networks?

To address this question, we focus on entanglement-assisted multiple access channels with causal channel state information at the transmitters (CSIT). The motivation for studying this setting comes from our recent work in [13], which explores the capacity of point-to-point channels with causal CSIT, and finds examples with capacity gains of up to \(12/\pi^2\approx 21\%\), due to quantum entanglement assistance. The presence of causal CSIT thus appears to be a key that can unlock capacity advantages from quantum entanglement assistance even in scenarios where no such advantage exists otherwise [5]. Moreover, causal CSIT is itself a well-motivated assumption in many practical settings, such as wireless uplinks and cognitive radio applications, where transmitters possess partial knowledge of the channel state based on their local interference environment [16].

The main contribution of this work is the discovery of exponential, unbounded and robust gains in capacity for various classical \(K\)-user multiple access channels with causal CSIT, due to quantum entanglement assistance. It is shown (Proposition 3) that in the presence of causal CSIT, quantum entanglement assistance provides a multiplicative capacity advantage that grows exponentially with the number of users \(K\) for certain classical \(K\)-user multiple access channels with fixed size (binary) alphabet for inputs, outputs and states. Similarly, for certain multiple access channels, in the presence of causal CSIT, quantum entanglement assistance is shown (Proposition 6) to provide a multiplicative capacity advantage that is unbounded as the state alphabet size grows, while the number of users \((K=3)\) and the input and output alphabet (binary) are held fixed.

For these gains in capacity, it is sufficient to have entanglement assistance only at the transmitters, as illustrated in Figure 1. For example, one of the channels that we consider (see Definition 4) is a classical binary additive MAC with a state-dependent additive interference term, \[\begin{align} Y=X_1\oplus X_2\oplus\dots\oplus X_K\oplus Z(S_1,S_2,\ldots,S_K).\label{eq:intmit} \end{align}\tag{1}\] Here \(S_k\) and \(X_k\) denote, respectively, the channel state information symbol and channel input symbol corresponding to Transmitter \(k\). \(Y\) is the channel output, \(Z(S_1,S_2,\ldots, S_K)\) is the state-dependent interference observed at the receiver, and \(\oplus\) is binary addition (all symbols are binary). This is a generalization, from a point-to-point setting to a MAC, of the channel model of [17]. Similar models have also been formulated in the studies of wireless networks [16]. For the particular interference structure chosen in our example (inspired by the Mermin-GHZ game [18]), we show that the sum-capacity with entanglement assistance provided only to the transmitters is \(1\) (bit/channel-use), whereas the capacity without entanglement assistance is only \(O(2^{-K})\), decaying exponentially in the number of users \(K\).

Given the claims of exponential or unbounded gains, it is natural to ask whether this advantage remains significant in finite-sized regimes, or if constant pre-factors make it practically inaccessible. The answer turns out to be surprisingly positive. Even with a moderate number of users and small alphabet sizes, the gains are substantial. For instance, in the setting of 1 , we observe (Figure 4) multiplicative capacity gains exceeding factors of \(21\) and \(88\) for \(K = 5\) and \(K = 7\) users, respectively.

An intuitive insight into the large quantum advantage can be found in the challenge of distributed interference suppression that is apparent in problem formulation 1 through the inclusion of \(Z\). Efficient channel utilization requires mitigating interference \(Z\) as much as possible based on the available CSIT, while also simultaneously using the channel for communication. How well the interference can be mitigated by distributed transmitters depends on how well the structure of the channel matches the structure of the interference (i.e., how the channel state depends on the CSIT). For example, with a linear channel as in 1 , a linear interference term may be efficiently neutralized, but a non-linear \(Z\) can be much more challenging to suppress for classical coding schemes. On the other hand, it is well-known that quantum entanglement assistance, utilizing non-local correlations, can efficiently map certain non-linear distributed computations to linear ones [19]–[23]. This allows the quantum-assisted transmitters to suppress the non-linear interference \(Z\) to a greater extent, with much greater efficiency, while simultaneously communicating (in superposition) over the linear channel, all of which significantly amplifies the capacity advantage. It is also worth noting that while the magnitude of the gain depends on the structure of interference \(Z\), even generic structures are found to retain significant advantages from quantum entanglement assistance (see Propositions 2 and 5).

To further understand the significance of CSIT, consider the alternative — a discrete memoryless MAC without CSIT. Since any channel state information at the receiver can be simply treated as a channel output, a MAC without CSIT can be reduced to a MAC without state. A trivial classical coding scheme for such a channel is a time-sharing of \(K\) schemes, each optimized for a particular user, so that the sum-rate of the scheme is \(1/K\) times the sum of the individual maximum rates achievable by the \(K\) users. Recalling that quantum entanglement assistance cannot increase the capacity of a single-user channel [5], it is perhaps intuitively to be expected that quantum-assisted coding schemes may not achieve a multiplicative capacity advantage greater than a factor of \(K\). Indeed, this intuition turns out to be correct. We show (Theorem 3 in Appendix 8) that in any \(K\)-user classical multiple access channel model without state, a capacity improvement by a multiplicative factor greater than \(K\) is impossible from quantum entanglement assistance, even if the assistance is provided to all transmitters and the receiver — in fact an improvement by a factor greater than \(K\) is impossible even with non-signaling assistance (which subsumes quantum assistance as a special case) provided to all parties. Considering that the capacity improvements found thus far (for MAC without state) have been rather small (not exceeding \(6\%\) to our knowledge), a factor of \(K\) bound could be quite loose. However, even this potentially loose bound clearly rules out any exponential/unbounded gains for multiple access channel models without state. Thus, the presence of a channel state along with some CSIT, exemplified in 1 by the interference \(Z(S_1,S_2,\cdots, S_K)\) with \(S_k\) known to Transmitter \(k\), emerges as an essential enabling premise for exponential/unbounded gains in capacity from quantum entanglement assistance.

Finally, another natural question to ask is whether these large gains are robust — do they only materialize if all quantum systems and quantum operations are perfect, or do the gains persist even with noisy systems and operations? Here also, the answer is quite positive. The gains persist even with noisy quantum resources. For example, the entanglement-assisted coding scheme for channel model 1 which achieves an exponential capacity advantage in the number of users \(K\), consumes a \(K\) qubit (one qubit per transmitter) pre-shared GHZ state per channel use. We find (see Remark 4 and Appendix 9.3) that the exponential advantage persists even if each qubit independently depolarizes with probability \(\approx\) 30\(\%\).

In summary, the discoveries reported here stem from an intuitive hypothesis that the cascading benefits of entanglement-assisted distributed interference suppression could translate to significant capacity gains, particularly when applied to non-linear interference structures like those identified in the literature [19]–[23]. The magnitude of the advantage, its grounding in Shannon capacity (rather than more fragile notions such as zero-error capacity), and its resilience to substantial quantum noise collectively paint an optimistic picture. Together, these factors open promising avenues to search for concrete practical applications, even in the current NISQ era.

2 Problem Formulation↩︎

2.1 Basic definitions↩︎

\(\mathbb{N}\) denotes the set of positive integers. For \(n\in\mathbb{N}\), \([n]\) denotes the set \(\{1,2,\ldots, n\}\), and \(x^n\) denotes the tuple \((x_1,x_2,\ldots, x_n)\). For integers \(n_1, n_2\), let \([n_1:n_2]\) denote the set \(\{n_1,\dots,n_2\}\) if \(n_1\leq n_2\) and the empty set otherwise. Let \(\mathbb{R}\) and \(\mathbb{C}\) denote the sets of real and complex numbers, respectively, and let \(\mathbb{R}_+\) denote the set of nonnegative real numbers. We use \(H(X)\) and \(H(X\mid Y)\) to denote the entropy and the conditional entropy, respectively, and we use \(I(X;Y)\) and \(I(X;Y\mid Z)\) to denote the mutual information and conditional mutual information, respectively. \(\Pr(E)\) denotes the probability of an event \(E\), and \(\mathbb{E}[X]\) denotes the expectation of a random variable \(X\). We write \(a\oplus_m b \triangleq a+b \pmod m\), and omit the subscript \(m\) when \(m=2\). We write \(g(n)=o(f(n))\) if \(\lim_{n\to \infty}g(n)/f(n) = 0\). We write \(g(n)=O(f(n))\) and \(h(n) = \Omega(f(n))\) if, for all sufficiently large \(n\), there exists some constant \(c>0\) such that \(|g(n)|\leq c|f(n)|\), \(|h(n)|\geq c|f(n)|\). We write \(H_b(p)\) for the binary entropy function, i.e., \(H_b(p)=-p\log_2(p) - (1-p)\log_2 (1-p)\), with the convention that \(0\log_2 (0) = 0\).

Let \(\mathcal{H}_Q\) denote the Hilbert space associated with a quantum system \(Q\). For a composite quantum system \(Q_1Q_2\cdots Q_K\), the associated Hilbert space is given by the tensor product \(\mathcal{H}_{Q_1}\otimes \mathcal{H}_{Q_2} \otimes \cdots \otimes \mathcal{H}_{Q_K}\). The spaces of linear operators and density operators on \(\mathcal{H}_Q\) are denoted by \(\mathcal{L}(\mathcal{H}_Q)\) and \(\mathcal{D}(\mathcal{H}_Q)\), respectively. We write \(\mathop{\mathrm{Tr}}[\cdot]\) for the trace of an operator. A quantum instrument from input system \(Q\) to output system \(Q'\), with classical outcome \(X\in \mathcal{X}\), is a collection \(\mathcal{E} = \{\mathcal{E}_x\}_{x\in \mathcal{X}}\) of completely positive, trace non-increasing maps \(\mathcal{E}_x\colon \mathcal{L}(\mathcal{H}_Q) \to \mathcal{L}(\mathcal{H}_{Q'})\) such that \(\sum_{x\in \mathcal{X}}\mathcal{E}_x\) is trace-preserving. A positive operator-valued measurement (POVM) on quantum system \(Q\), with classical outcome \(X\in \mathcal{X}\) is a collection of positive semi-definite operators \(\mathcal{D} = \{D_{x}\}_{x\in \mathcal{X}}\) on \(\mathcal{H}_Q\) such that \(\sum_{x\in \mathcal{X}} D_x = I\), where \(I\) is the identity operator on \(\mathcal{H}_Q\).

2.2 \(K\)-user state-dependent multiple access channel↩︎

A (discrete memoryless) \(K\)-user state-dependent multiple access channel \((\mathsf{N}, \mathsf{P}_{\!S_1S_2\cdots S_K})\) is defined by the channel conditional distribution \(\mathsf{N}(y\mid x_1,x_2,\ldots, x_K, s_1,s_2,\ldots,s_K)\), and the state distribution \(\mathsf{P}_{\!S_1S_2\cdots S_K}(s_1,s_2,\ldots, s_K)\), for all \(y \in \mathcal{Y}\), \((x_1,x_2,\ldots, x_K)\in \mathcal{X}_1\times \mathcal{X}_2 \times \cdots \times \mathcal{X}_K\), and \((s_1,s_2,\ldots, s_K)\in \mathcal{S}_1\times \mathcal{S}_2 \times \cdots \times \mathcal{S}_K\), where \(\mathcal{Y}\), \(\mathcal{X}_k\), and \(\mathcal{S}_k\) are finite alphabets for each \(k\in [K]\). For each channel use, the channel states \((S_1,S_2,\ldots, S_K)\) are generated according to \(\mathsf{P}_{\!S_1S_2\cdots S_K}\), such that \(\Pr(S_k=s_k,\forall k\in [K]) = \mathsf{P}_{\!S_1S_2\cdots S_K}(s_1,s_2,\ldots, s_K)\). For each \(k\in [K]\), the \(k^{th}\) transmitter (user) observes \(S_k\), and chooses an input \(X_k \in \mathcal{X}_k\). The output \(Y\) of the channel is a random variable seen by the receiver, such that \(\Pr(Y=y\mid X_k =x_k, S_k=s_k, \forall k\in [K]) = \mathsf{N}(y\mid x_1,x_2,\ldots, x_K,s_1,s_2,\ldots, s_K)\).

For \(n\in \mathbb{N}\) uses of the channel, we use \(S_{k,i}, X_{k,i}\), and \(Y_i\) to denote the state \(S_k\), input \(X_k\), and the output \(Y\) associated with the \(i^{th}\) use of the channel. The states across different channel uses are independent, i.e., \(\Pr(S_k^{n}=s_k^n,\forall k\in [K])=\prod_{i=1}^n \Pr(S_{k,i}=s_{k,i},\forall k)\). The conditional probability of the outputs \(\Pr(Y^n=y^n\mid X_k^n=x_k^n, S_k^n=s_k^n,\forall k\in [K]) = \prod_{i=1}^n\Pr(Y_i=y_i\mid X_{k,i}=x_{k,i}, S_{k,i}=s_{k,i},\forall k\in [K])\).

In the following we formalize two classes of coding schemes, namely, the classical coding schemes, and the entanglement-assisted coding schemes, both using causal CSIT. We then define the achievable rates and the capacities associated with the two classes of coding schemes.

2.3 Classical coding schemes with causal CSIT↩︎

For \(M_1,M_2,\ldots, M_K, n \in \mathbb{N}\), a classical \((M_1,M_2,\ldots, M_K,n)\) coding scheme with causal CSIT is specified by a tuple \[\Big(\mathsf{P}_{\!J}, \big((\phi_{1}^{(i)}, \phi_{2}^{(i)},\ldots, \phi_{K}^{(i)} )\big)_{i\in [n]}, \psi\Big).\] For each \(k\in [K]\), Transmitter \(k\) sends a message of size \(M_k\) by using the channel \(n\) times. Specifically, for each \(k\in [K]\), an independent message \(W_k\), uniformly distributed in \([M_k]\), originates at Transmitter \(k\). The \(K\) transmitters and the receiver are allowed to share² a classical random variable \(J\) (independent of the messages) that takes values in \(\mathcal{J}\). The distribution of \(J\) is \(\mathsf{P}_{\!J}\). For \(i=1,2,\ldots, n\), and for each \(k\in [K]\), \(\phi_{k}^{(i)} \colon [M_k] \times (\mathcal{S}_k)^i \times \mathcal{J} \to \mathcal{X}_k\) specifies the encoder at Transmitter \(k\) for the \(i^{th}\) channel use, such that \(X_{k,i} = \phi_{k}^{(i)}(W_k, S_k^i, J)\). At the receiver, \(\psi\colon \mathcal{Y}^n\times \mathcal{J} \to [M_1]\times [M_2] \times \cdots \times [M_K]\) specifies the decoder, with decoded messages \((\widehat{W}_1,\widehat{W}_2,\ldots, \widehat{W}_K) = \psi(Y^n,J)\).

Let us define \(\mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_1,M_2,\ldots, M_K,n)\) as the set of all classical \((M_1,M_2,\ldots, M_K,n)\) coding schemes with causal CSIT.

2.4 Transmitter-side entanglement-assisted coding schemes with causal CSIT↩︎

With entanglement-assistance and causal CSIT available to the transmitters, an \((M_1,M_2,\ldots, M_K,n)\) coding scheme is specified by a tuple \[\Big(\rho,\big((\mathcal{E}^{(1,i)}, \mathcal{E}^{(2,i)},\ldots, \mathcal{E}^{(K,i)})\big)_{i\in [n]}, \psi \Big).\] Such a scheme allows the \(K\) transmitters to share in advance a \(K\)-partite (entangled) quantum system \(Q_1Q_2\cdots Q_K\) in the initial state \(\rho\in \mathcal{D}(\mathcal{H}_{Q_1}\otimes \mathcal{H}_{Q_2}\otimes \cdots \otimes \mathcal{H}_{Q_K})\) that is independent of the messages \((W_1,W_2,\ldots, W_K)\). For each \(k\in [K]\), \(Q_k\) denotes the quantum system with Transmitter \(k\). The scheme works as follows. For \(i=1,2,\ldots,n\), at the \(i^{th}\) channel use, and for each \(k\in [K]\), conditioned on \((W_k=w_k, S_k^{i}=s_k^{i}, X_k^{i-1}=x_k^{i-1})\), Transmitter \(k\) applies the encoding quantum instrument \(\mathcal{E}^{(k,i)} = \Big\{\mathcal{E}^{(k,i)}_{x_{k,i}\mid (w_k,s_k^{i},x_k^{i-1})}\Big\}_{x_{k,i}\in \mathcal{X}_k}\), and inputs the classical outcome \(X_{k,i}\) into the channel. After \(n\) uses of the channel, the receiver collects the channel outputs \(Y^n=(Y_1,Y_2,\ldots, Y_n)\) and applies the decoder \(\psi\colon \mathcal{Y}^n \to [M_1]\times [M_2] \times \cdots \times [M_K]\) to produce the decoded messages \((\widehat{W}_1,\widehat{W}_2,\ldots, \widehat{W}_K) = \psi(Y^n)\).

Let us define \(\mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }(M_1,M_2,\ldots, M_K,n)\) as the set of all transmitter-side entanglement-assisted \((M_1,M_2,\ldots, M_K,n)\) coding schemes with causal CSIT.

Henceforth, we omit the phrases “with causal CSIT," and”transmitter-side," as they are the default assumptions throughout the paper.

2.5 Probability of error, achievable rate and capacity↩︎

Given a coding scheme \(\Gamma\), the probability of error is defined as \(P_e(\Gamma) = \Pr\big( (\widehat{W}_1,\ldots,\widehat{W}_K)\neq (W_1,\ldots, W_K) \big)\). The explicit steps to find this value are derived in Appendix 5.

A rate tuple \((R_1,\ldots, R_K) \in \mathbb{R}_+^K\) is classically achievable if there exists a sequence of coding schemes \(\Gamma_n \in \mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_{1,n}, \ldots, M_{K,n},n)\) such that \(\lim_{n\to \infty} P_e(\Gamma_n) = 0\) and \(\lim_{n\to \infty}\log_2(M_{k,n})/n \geq R_k, \forall k\in [K]\). Similarly, \((R_1,\ldots, R_K) \in \mathbb{R}_+^K\) is achievable with entanglement assistance (EA) if the same conditions hold for a sequence of coding schemes \(\Gamma_n \in \mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }(M_{1,n}, \ldots, M_{K,n},n)\).

The classical (sum-rate) capacity \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }\) is defined as \[\sup\{R_1+\cdots +R_K\colon (R_1,\ldots, R_K)~ is classically achievable\}.\] The entanglement-assisted capacity is defined as \[\sup\{R_1+\cdots +R_K\colon (R_1,\ldots, R_K)~ is achievable with EA\}.\]

3 Results↩︎

3.1 Additive MAC with state-dependent interference↩︎

The main results of this paper are developed for the additive MAC with state-dependent interference channel model, defined as follows. See Fig. 2 for an illustration.

The goal of this work is to identify the capacity gain from entanglement assistance. To this end, the following theorem characterizes the classical capacity for any additive MAC with state-dependent interference.

The proof of Theorem 1 is presented in Appendix 6. Theorem 1 can be viewed as an extension of [17] to the MAC setting. The converse follows from a standard application of Fano’s inequality. The achievability can be interpreted as the following channel conversion strategy which tries to suppress the interference over each channel use. Specifically, for each \(k\in [K]\), Transmitter \(k\) sends \(X_k = X_k'\oplus_m t_k(S_k)\) for some \(X_k'\in \mathcal{X}_k\). The receiver sees \(Y = X_1'\oplus_m \cdots \oplus_m X_K'\oplus (t_1(S_1) \oplus_m \cdots \oplus_m t_K(S_K) \oplus Z)\). The term \((t_1(S_1) \oplus_m \cdots \oplus_m t_K(S_K) \oplus_m Z)\) is then viewed as the suppressed interference, which has entropy \(H_{\min}\) when minimized over all deterministic functions \(t_k \colon \mathcal{S}_k \to \mathcal{X}_k, \forall k\). By coding over the converted channel \((X_1',\ldots, X_K') \to Y\), the sum-rate \(\log_2(m) - H_{\min}\) is achievable. Note that the channel conversion idea only uses CSIT of the current channel, and therefore it only needs causal CSIT. We also observe that when \(H_{\min} = H(Z)\), the classical capacity with causal CSIT coincides with the classical capacity without CSIT.

We next extend the channel conversion idea to incorporate transmitter-side entanglement assistance. This is formalized in Theorem 2.

The proof is presented in Appendix 7.

3.2 2-user cases↩︎

As an introductory example to see how entanglement assistance can improve the capacity with causal CSIT, let us consider the cases with \(K=2\) users, and present the following example, namely Channel A1.

We have the following proposition regarding Channel A1.

Next, let us define a particular subset of \(2\)-user additive MACs with state-dependent interference, namely Class A as follows.

Without loss of generality, consider the channels in Class A for which \(\mathcal{S}_1=\mathcal{S}_2 = [L]\). For \(L\in \mathbb{N}\), suppose one randomly picks such a channel \(\mathsf{ch}_L\) by assigning to \(f(s_1,s_2)\) a value uniformly in \(\{0,1\}\), independently for each \((s_1,s_2)\in [L]^2\). Denote by \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{ch}_L)\) and \(C^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }(\mathsf{ch}_L)\) the classical capacity and the entanglement-assisted capacity associated with \(\mathsf{ch}_L\), respectively. We then have the following proposition.

The proof is presented in Appendix 10. It is based on a result by Ambainis et al. [20].

3.3 Exponential capacity gain in number of users \(K\) with fixed (binary) state alphabet↩︎

Now let us shift our focus to \(K\geq 3\) users, and present an example for which we witness an exponential (in \(K\)) gain in capacity from transmitter-side entanglement assistance. The examples in this section require only binary alphabet for the states.

Note that the integer sum \(S_1+S_2+\cdots+S_K\) yields an even number because of the correlation relationship, ensuring that \((S_1+S_2+\cdots +S_K)/2\) is an integer and then the mod 2 operation produces an output in \(\{0,1\}\). The particular structure of \(Z\) is inspired by the Mermin-GHZ game [18].

The next proposition establishes an exponential gain from quantum entanglement assistance.

The proof of Proposition 3 is presented in Section 9.1. We plot the values of \(C^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }/C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }\) for \(K\in [3:8]\) in Fig. 4. The following lemma may be useful in understanding the approximation in ?? .

While the correlation among channel states that is assumed in Channel B1 does simplify our analysis, allowing us to find the exact capacities in Proposition 3, it is not an essential requirement for an exponential advantage. Our next example will show that the exponential gain also exists for a channel where the channel states \((S_1,\ldots, S_K)\) are independent. See Definition 5, which defines such a channel Channel B2, and Proposition 4.

The proof of Proposition 4 is presented in Appendix 9.2.

Next, let us define a particular subset of additive MACs with state-dependent interference, namely Class \(B\) as follows.

Suppose one randomly picks a \(K\)-user channel \(\mathsf{ch}_K\) in Class B, by assigning \(G_i\) to a value uniformly in \(\{0,1\}\), independently for each \(i\in [0:K]\). Denote by \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{ch}_K)\) and \(C^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }(\mathsf{ch}_K)\) the classical capacity and the entanglement-assisted capacity for \(\mathsf{ch}_K\), respectively. We then have the following proposition.

The proof is presented in Appendix 10. It is based on the results by Ambainis et al. [21], [22].

3.4 Unbounded capacity gain for large state alphabet with fixed (\(K=3\)) number of users↩︎

The capacity gain factors we saw in Class B are bounded if \(K\) is fixed. One may wonder if the gain factor can be actually unbounded with finite number of users. We answer this question in the affirmative in the following proposition.

The proof is presented in Appendix 10. It is based on a result by Briët and Vidick [23]. We point out that the channels used to show the existence of the gain may have dependent channel states \((S_1,S_2,S_3)\).

The table below summarizes the multiplicative gains \(C^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }/C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }\) in the aforementioned channels (classes). Note that in all cases considered, the channel input and output alphabet are binary.

4 Conclusion↩︎

Exponential, unbounded and robust gains in capacity are established for various \(K\)-user multiple access channels with causal CSIT, due to quantum entanglement assistance provided to the transmitters. This points to a rich landscape of open questions for future work, including how the gains extend beyond the specific examples considered here, whether similar gains exist when the CSIT is strictly causal [24], non-causal [25], or mixed as in [26], and more generally beyond the MAC to other state-dependent communication networks with quantum entanglement assistance.

5 Probability of error of a coding scheme↩︎

Recall that we are given the \(K\)-user state-dependent MAC \((\mathsf{N}, \mathsf{P}_{\!S_1S_2\cdots S_K})\). For a coding scheme \(\Gamma\in \mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_1,\ldots, M_K,n) \cup \mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }(M_1,\ldots, M_K,n)\), the probability of error is \(P_e(\Gamma) = \Pr\big( (\widehat{W}_1,\ldots,\widehat{W}_K)\neq (W_1,\ldots, W_K) \big)\). In the following we derive an expression for \(1-P_e(\Gamma)\).

Let us use bold letters to denote the corresponding \(K\)-tuples. For example, let \({\boldsymbol{W}}\) represent the \(K\)-tuple \((W_1, W_2,\ldots, W_K)\). Then, \[\begin{align} &1-P_e(\Gamma) = \Pr \big( \widehat{\boldsymbol{W}} = {\boldsymbol{W}}\big) \\ &= \sum_{{\boldsymbol{w}}, {\boldsymbol{s}}^n} \Pr({\boldsymbol{W}} = {\boldsymbol{w}}) \Pr({\boldsymbol{S}}^n={\boldsymbol{s}}^n) \Pr\big( \widehat{\boldsymbol{W}} = {\boldsymbol{w}} \mid {\boldsymbol{W}}={\boldsymbol{w}}, {\boldsymbol{S}}^n={\boldsymbol{s}}^n\big) \label{eq:prob95error95first} \end{align}\tag{2}\] since \({\boldsymbol{W}} = (W_1,W_2,\ldots, W_K)\) is independent of \({\boldsymbol{S}}^n = (S_1^n,S_2^n,\ldots, S_K^n)\). Note that \(\Pr({\boldsymbol{W}}={\boldsymbol{w}}) = (M_1M_2\cdots M_K)^{-1}\) since the messages are generated independently uniform. Meanwhile, \(\Pr({\boldsymbol{S}}^n = {\boldsymbol{s}}^n) = \prod_{i=1}^n \mathsf{P}_{\!S_1S_2\cdots S_K}(s_{1,i},s_{2,i},\ldots, s_{K,i})\). Clearly, \(\Pr({\boldsymbol{W}} = {\boldsymbol{w}}) \Pr({\boldsymbol{S}}^n={\boldsymbol{s}}^n)\) does not depend on \(\Gamma\), and in the following we derive \(\Pr\big( \widehat{\boldsymbol{W}} = {\boldsymbol{w}} \mid {\boldsymbol{W}}={\boldsymbol{w}}, {\boldsymbol{S}}^n={\boldsymbol{s}}^n\big)\).

We simply write \(a\) for the event \(A=a\). Consider two cases.

If \(\Gamma = \big(\mathsf{P}_{\!J}, ((\phi_{1}^{(i)}, \phi_{2}^{(i)},\ldots, \phi_{K}^{(i)} ))_{i\in [n]}, \psi\big) \in \mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_1,M_2,\ldots, M_K,n)\) is a classical coding scheme with shared randomness \(J\) (which is independent of \(({\boldsymbol{W}}, {\boldsymbol{S}}^n)\), then \[\begin{align} &\Pr\big( \widehat{\boldsymbol{W}} = {\boldsymbol{w}} \mid {\boldsymbol{W}}={\boldsymbol{w}}, {\boldsymbol{S}}^n={\boldsymbol{s}}^n\big)\notag\\ &=\sum_{j\in \mathcal{J}}\mathsf{P}_{\!J}(j) \Pr\big( \widehat{\boldsymbol{W}} = {\boldsymbol{w}} \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n, j\big)\\ &=\sum_{j\in \mathcal{J}}\mathsf{P}_{\!J}(j) \sum_{y^n\colon \psi(y^n,j) = {\boldsymbol{w}} } \prod_{i=1}^n \mathsf{N}\Big(y_i \mid \phi_1^{(i)}(w_1,s_1^i,j),\ldots, \phi_K^{(i)}(w_K,s_K^i,j), s_{1,i},\ldots, s_{K,i}\Big) \label{eq:prob95error95classical} \end{align}\tag{3}\] To see the last step, note that for each \(k\in [K]\), \(i\in [n]\), and \(j\in \mathcal{J}\), \(\phi_k^{(i)}(w_k,s_k^i,j)\) is the input at Transmitter \(k\) for the \(i^{th}\) channel use, and the sum is taken over the subset of \(y^n\) for which the decoder \(\psi(y^n,j)\) outputs the correct messages \({\boldsymbol{w}}\).

If \(\Gamma = \big(\rho,((\mathcal{E}^{(1,i)}, \mathcal{E}^{(2,i)},\ldots, \mathcal{E}^{(K,i)}))_{i\in [n]}, \psi \big) \in \mathfrak{F}^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }(M_1,M_2,\ldots, M_K,n)\) is an entanglement-assisted coding scheme, then \[\begin{align} &\Pr\big(\widehat{\boldsymbol{W}}={\boldsymbol{w}} \mid {\boldsymbol{W}}={\boldsymbol{w}}, {\boldsymbol{S}}^n={\boldsymbol{s}}^n) \notag \\ &=\sum_{{\boldsymbol{x}}^n, y^n}\Pr\big(\widehat{\boldsymbol{W}}={\boldsymbol{w}}, {\boldsymbol{x}}^n, y^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n) \\ &=\sum_{{\boldsymbol{x}}^n, y^n}\Pr\big( {\boldsymbol{x}}^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n) \Pr(y^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n, {\boldsymbol{x}}^n) \Pr\big( \widehat{\boldsymbol{W}}={\boldsymbol{w}}\mid {\boldsymbol{w}}, {\boldsymbol{s}}^n, {\boldsymbol{x}}^n, y^n \big) \\ &=\sum_{{\boldsymbol{x}}^n}\Pr\big( {\boldsymbol{x}}^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n) \sum_{y^n\colon \psi(y^n)= {\boldsymbol{w}}} \prod_{i=1}^n \mathsf{N}(y_i\mid x_{1,i},\ldots, x_{k,i}, {\boldsymbol{s}}_{1,i}, \ldots, s_{K,i})\label{eq:prob95error95EA95intermediate951} \end{align}\tag{4}\] To justify the last step, first we note that since \(({\boldsymbol{W}}, {\boldsymbol{S}}^n) \leftrightarrow {\boldsymbol{X}}^n \leftrightarrow {\boldsymbol{Y}}^n\) form a Markov chain and the channel is memoryless, we have \(\Pr(y^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n, {\boldsymbol{x}}^n) = \Pr(y^n \mid {\boldsymbol{s}}^n, {\boldsymbol{x}}^n) = \prod_{i=1}^n \mathsf{N}(y_i\mid {\boldsymbol{x}}_i, {\boldsymbol{s}}_i)\). Then, note that \(\Pr\big( \widehat{\boldsymbol{W}}={\boldsymbol{w}}\mid {\boldsymbol{w}}, {\boldsymbol{s}}^n, {\boldsymbol{x}}^n, y^n \big) = 1\) if the decoded messages \(\phi(y^n)={\boldsymbol{w}}\), and it equals \(0\) otherwise.

The term \(\Pr\big( {\boldsymbol{x}}^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n \big)\) depends on the encoding quantum instruments. To state it explicitly, for each \(k\in [K]\), let \[\overline{\mathcal{E}}^{(k)}_{x_k^n\mid (w_k,s_k^n)} \triangleq \mathcal{E}_{x_{k,n}\mid (w_k,s_k^n,x_k^{n-1})}^{(k,n)} \circ \mathcal{E}_{x_{k,n-1}\mid (w_k,s_k^{n-1},x_k^{n-2})}^{(k,n-1)} \circ \cdots \circ \mathcal{E}_{x_{k,1}\mid (w_k, s_{k,1})}^{(k,1)}\] denote the overall encoding quantum instrument at Transmitter \(k\), conditioned on the message and the channel states across \(n\) channel uses, where \(\circ\) denotes the composition of two maps. Then \[\begin{align} \Pr\big( {\boldsymbol{x}}^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n \big) = \mathop{\mathrm{Tr}}\Big[ \big( \underbrace{\overline{\mathcal{E}}_{x_1^n\mid (w_1, s_1^n)}^{(1)} \otimes \cdots \otimes \overline{\mathcal{E}}_{x_K^n\mid (w_K,s_K^n)}^{(K)}\big)(\rho)}_{\triangleq \widetilde{\rho}_{{\boldsymbol{x}}^n, {\boldsymbol{w}}, {\boldsymbol{s}}^n} } \Big]. \end{align}\] Note that \(\widetilde{\rho}_{{\boldsymbol{x}}^n, {\boldsymbol{w}}, {\boldsymbol{s}}^n}\) is an unnormalized density operator. The normalized version is \(\widetilde{\rho}_{{\boldsymbol{x}}^n, {\boldsymbol{w}}, {\boldsymbol{s}}^n}/\Pr\big( {\boldsymbol{x}}^n \mid {\boldsymbol{w}}, {\boldsymbol{s}}^n \big)\).

In either case, plugging \(\Pr\big(\widehat{\boldsymbol{W}}={\boldsymbol{w}} \mid {\boldsymbol{W}}={\boldsymbol{w}}, {\boldsymbol{S}}^n={\boldsymbol{s}}^n)\) into 2 yields an explicit expression for \(1-P_e(\Gamma)\). 0◻

6 Proof of Theorem 1↩︎

7 Proof of Theorem 2↩︎

Given \(\rho\in \mathcal{D}(\mathcal{H}_{Q_1} \otimes \cdots \otimes \mathcal{H}_{Q_K})\), for each channel use, let the \(K\) transmitters share the entangled resource in the state \(\rho\), such that Transmitter \(k\) has \(Q_k\) for each \(k\in [K]\). For each \(k\in [K]\), Transmitter \(k\) measures \(Q_k\) on the POVM \(\mathcal{F}^{(k)}_{s_k} = \{F^{(k)}_{b_k\mid s_k}\}_{b_k\in [0:m-1]}\) when the channel state \(S_k=s_k\), and obtains the outcome \(B_k\). It then sends \(X_k=X_k'\oplus_m B_k\) for some \(X_k' \in \mathcal{X}_k\). The receiver sees \(Y = X_1\oplus_m \cdots \oplus_m X_k\oplus_m Z = X_1'\oplus_m \cdots \oplus_m X_k' \oplus_m ( B_1\oplus_m \cdots \oplus_m B_K \oplus_m Z)\). Denote \(Z'\triangleq ( B_1\oplus_m \cdots \oplus_m B_K \oplus_m Z)\). It follows that the converted channel \((X_1', \ldots, X_K') \to Y\) is another additive MAC with state-dependent interference term equal to \(Z'\). In the converted channel, if we set \(X_k'=0\) for \(k\in \{2,\ldots, K\}\), then we have a point-to-point channel (from Transmitter \(1\) to the receiver) with \(Y = X_1'\oplus_m Z'\). It follows from the direct coding theorem of a point-to-point channel that any rate \(R < I(X_1';X_1' \oplus_m Z') = H(X_1' \oplus_m Z') - H(X_1' \oplus_m Z' \mid X_1') = \log_2(m) - H(Z')\) is achievable for message \(W_1\), where \(X_1'\) is uniformly distributed over \([0:m-1]\). By symmetry and a standard time-division multiple access (TDMA) strategy, any rate tuple satisfying \(R_1+\cdots +R_K<\log_2(m)-H(Z')\) is achievable. 0◻

8 Theorem 3↩︎

In this section, let us consider \(K\)-user MACs without state, i.e., specified by their channel conditional distribution \(\mathsf{N}(y\mid x_1,x_2,\ldots, x_K)\). Fawzi and Fermé [10] studied the capacity for \(2\)-user MACs with non-signaling assistance (which strictly includes quantum entanglement assistance) for all parties (\(2\) transmitters and \(1\) receiver). Let us extend the setting to the \(K\)-user MACs, and denote the \((K+1)\)-partite non-signaling assisted (sum-rate) capacity as \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\). Clearly, \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} } \geq C^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} }\). We have the following theorem.

Therefore, for any \(K\)-user MAC without state, \(C^{\mathchoice {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} {\mathrm{\scriptscriptstyle EA}} } \leq C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\leq KC^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }\).

9 Proofs of Propositions 3, 4, and justification for Remark 4↩︎

9.1 Proof of Proposition 3↩︎

9.2 Proof of Proposition 4↩︎

For Channel B2, \(Z = \lceil (S_1+\cdots + S_K)/2 \rceil \pmod 2 = (S_1+\cdots + S_K+S_{0}) /2 \pmod 2\), where we defined \(S_0 \triangleq \bigoplus_{k=1}^K S_k\). To show that \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} } \leq 1-H_b(\tfrac{1}{2}+2^{\lceil (K+1)/2\rceil})\), note that for Channel B2, \(H_{\min} = \min_{t_1,\ldots, t_K}H(\bigoplus_{k=1}^K t_k(S_k) \oplus Z) \geq \min_{t_0,t_1,\ldots, t_K}H(\bigoplus_{k=0}^K t_k(S_k) \oplus Z) = H_b(\frac{1}{2}+2^{-\lceil {(K+1)}/2 \rceil})\), where the last step follows the same lines of the proof of the classical capacity of Channel B1 by considering \(K+1\) users. Therefore, \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }\leq 1-H_b(\frac{1}{2}+2^{-\lceil {(K+1)}/2 \rceil})\). We again have \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }=O(2^{-K})\) by Lemma 1.

With entanglement assistance, we again use the same channel conversion strategy. Note that conditioned on \(S_0=0\), which happens with probability \(1/2\), Channel B2 becomes Channel B1, so the interference term is completely canceled by the channel conversion strategy. Conditioned on \(S_0=1\), after the transmitters apply their conditional phase gates, the state of the qubits \(\ket{\Psi}\) is either equal to \(\frac{\sqrt{2}}{2}(\ket{0}^{\otimes K} + i \ket{1}^{\otimes K}) = \frac{1}{2}\big((1+i) \ket{\Phi^+} + (1-i) \ket{\Phi^-} \big)\), or equal to \(\frac{\sqrt{2}}{2}(\ket{0}^{\otimes K} - i \ket{1}^{\otimes K}) = \frac{1}{2}\big((1-i) \ket{\Phi^+} + (1+i) \ket{\Phi^-} \big)\). Note that in either case, \(\ket{\Psi}\) is in the span of \(\{\ket{\Phi^+}, \ket{\Phi^-}\}\). Also, for all cases where \(S_0=1\), we have \(|\braket{\Phi^+|\Psi}|^2 = |\braket{\Phi^-|\Psi}|^2 = 1/2\), regardless of the value of \(Z\). It follows that \(\Pr(B_1\oplus \cdots \oplus B_K \oplus Z = z \mid S_0=1) = 1/2, \forall z\in \{0,1\}\). Recall that \(Y = (X_1'\oplus \cdots \oplus X_K') \oplus (B_1\oplus\cdots \oplus B_K \oplus Z)\). Observe that conditioned on \(S_0=1\), the converted channel is completely noisy, in that the output is uniformly distributed over \(\{0,1\}\), regardless of the inputs \(X_1',\ldots, X_K'\). Overall, we have \(Y = X_1'\oplus \cdots \oplus X_K'\oplus Z'\) where \(Z'\) is an independent noise term with \(\Pr(Z'=0) = 3/4\) and \(\Pr(Z'=1) = 1/4\). Thus, any rate tuple satisfying \(R_1+\cdots+R_K<1-H_b(3/4)\) is achievable with entanglement assistance. 0◻

9.3 Justification for Remark 4 (Robustness)↩︎

The above entanglement-assisted scheme assumes that the qubits consumed for each channel use are in the perfect GHZ state \(\ket{\Phi^+}\). In contrast, suppose that each qubit (independently) has a probability \(1-\gamma\) of being completely depolarized, where \(\gamma \in [0,1]\). Consider any use of Channel B1 (or Channel B2). Let \(D\) denote the event that “at least one qubit in the GHZ state is depolarized," and let \(\overline{D}\) denote the complement of \(D\), i.e.,”all \(K\) qubits are intact." Then we have \(\Pr(D) = 1-\gamma^K\) and \(\Pr(\overline{D}) = \gamma^K\). It is not difficult to see that the depolarization of any qubit (say \(Q_k\)) causes \(B_k\) to be a random noise uniformly distributed over \(\{0,1\}\). It follows that \(\Pr(Y=X_1'\oplus \cdots \oplus X_K' \mid D) = \frac{1}{2}\). Thus, \(\Pr(Y=X_1'\oplus \cdots \oplus X_K') = \Pr(Y=X_1'\oplus \cdots \oplus X_K' \mid D)\Pr(D) + \Pr(Y=X_1'\oplus \cdots \oplus X_K' \mid \overline{D})\Pr(\overline{D}) = \frac{1}{2}(1-\gamma^{K})+\alpha \gamma^{K} = \frac{1}{2}+(\alpha-\frac{1}{2})\gamma^K\), where \(\alpha=1\) for Channel B1, and \(\alpha = \frac{3}{4}\) for Channel B2. Equivalently, write the converted channel as \(Y = X_1'\oplus \cdots \oplus X_K'\oplus Z'\) where \(Z'\) is an independent noise term with \(\Pr(Z'=0) = \frac{1}{2}+(\alpha-\frac{1}{2})\gamma^K\) and \(\Pr(Z'=1) = \frac{1}{2}-(\alpha-\frac{1}{2})\gamma^K\). Thus, any rate tuple satisfying \(R_1+\cdots+R_K<1-H_b\big(\frac{1}{2}+(\alpha-\frac{1}{2})\gamma^K\big)\) is achievable, via a binary symmetric channel (BSC) code for each message along with TDMA over this converted channel. The rate thus achieved is \(\Omega(\gamma^{2K})\) as \(K \to \infty\) by Lemma 1.

Recall from Proposition 3 and Proposition 4 that \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} } = O\big((\frac{1}{2})^K\big)\), we conclude that as long as \(\gamma^2 > \frac{1}{2}\), i.e., \(\gamma > \frac{\sqrt{2}}{2} \approx 70\%\), there is still an exponential capacity gain from entanglement assistance for Channel B1 and Channel B2, and to achieve such a gain it is sufficient (albeit not necessarily optimal) to directly apply the channel conversion strategy designed for the case of perfect entanglement. 0◻

10 Proofs of Propositions 2, 5 and 6↩︎

The proofs in this section require results on XOR games⁴ [20]–[23]. For our purpose, let us consider the following definition of XOR games in Definition 7.

Given an XOR game, we study the classical strategies and the entanglement-assisted (EA) strategies that win the game (with certain probability). The definitions for these strategies are given as follows.

Now, let us make a connection from any XOR game to an \((m=2)\) additive MACs with state-dependent interference. Given the XOR game \((\{\mathcal{A}_k\}_{k\in [K]},\mathsf{P}_{\!A_1\cdots A_K},f)\), consider the following additive MAC with state-dependent interference: the state \(S_k\) of the MAC is equal to \(A_k\) of the game, and the interference term \(Z\) is equal to \(f(S_1,\ldots, S_K)\). It follows that the channel has the form \[\begin{align} \label{eq:channel95from95XOR95game} Y = X_1\oplus X_2 \oplus \cdots \oplus X_K \oplus f(S_1,\ldots, S_K). \end{align}\tag{14}\] We then have the following lemmas.

We are now ready to prove Propositions 2, 5 and 6.

11 The CHSH strategy↩︎

Let us explain the CHSH strategy in the context of our channel conversion scheme. Recall that for each channel use, Transmitter \(1\) knows \(S_1\in \{0,1\}\) and Transmitter \(2\) knows \(S_2\in \{0,1\}\). The two transmitters share a pair of entangled qubits (namely, \(Q_1Q_2\)) in the state \(\ket{\Phi^+}_{Q_1Q_2} = \frac{1}{\sqrt{2}}\big(\ket{0}_{Q_1}\!\ket{0}_{Q_2}+\ket{1}_{Q_1}\!\ket{1}_{Q_2}\big) = \frac{1}{\sqrt{2}}\big(\ket{+}_{Q_1}\!\ket{+}_{Q_2}+\ket{-}_{Q_1}\!\ket{-}_{Q_2}\big)\), where \(\ket{+} \triangleq \frac{1}{\sqrt{2}}\big(\ket{0}+\ket{1}\big)\) and \(\ket{-} \triangleq \frac{1}{\sqrt{2}}\big(\ket{0}-\ket{1}\big)\). For \(\theta\in [0,2\pi)\), let \({\sf U}_\theta \triangleq \ket{+}\!\bra{+} + e^{i\theta} \ket{-} \! \bra{-}\) be a unitary operator. For each \(k\in \{1,2\}\), Transmitter \(k\) applies \({\sf U}_{\theta_k}\) on \(Q_k\), (\(\theta_k\) depends on \(S_k\) and is specified later). The state of the qubits after the operations is, \[\begin{align} \ket{\Psi}_{Q_1Q_2} &= \frac{1}{\sqrt{2}}\Big(\ket{+}_{Q_1}\!\ket{+}_{Q_2} + e^{i(\theta_1+\theta_2)}\ket{-}_{Q_1}\!\ket{-}_{Q_2}\Big) \\ &= \frac{1}{2\sqrt{2}}\big( 1+e^{i(\theta_1+\theta_2)} \big)\big(\ket{0}_{Q_1}\!\ket{0}_{Q_2} +\ket{1}_{Q_1}\!\ket{1}_{Q_2} \big) \notag \\ &~~~~+ \frac{1}{2\sqrt{2}}\big( 1-e^{i(\theta_1+\theta_2)} \big)\big(\ket{0}_{Q_1}\!\ket{1}_{Q_2} +\ket{1}_{Q_1}\!\ket{0}_{Q_2} \big) \end{align}\] For \(k\in \{1,2\}\), Transmitter \(k\) measures \(Q_k\) in the computational basis and obtains \(B_k \in \{0,1\}\) by mapping the state \(\ket{x}_{Q_k} \to x,\forall x\in \{0,1\}\). Conditioned on \((S_1,S_2)\), the probability of \(B_1\oplus B_2 = 0\) is then \(2 \times |\frac{1}{2\sqrt{2}}(1+e^{i(\theta_1+\theta_2)})|^2 = \cos^2\big(\frac{\theta_1+\theta_2}{2}\big)\), and the probability of \(B_1\oplus B_2 = 1\) is \(1-\cos^2\big(\frac{\theta_1+\theta_2}{2}\big) = \sin^2\big(\frac{\theta_1+\theta_2}{2}\big)\). Now, let \(\theta_1 = 0\) if \(S_1=0\); \(\theta_1 = \pi/2\) if \(S_1=1\). Let \(\theta_2 = -\pi/4\) if \(S_2=0\); \(\theta_2=\pi/4\) if \(S_2=1\). It can be then verified that \(\Pr(B_1\oplus B_2 = 0\mid S_1S_2=0) = \Pr(B_1\oplus B_2 = 1\mid S_1S_2=1) = \cos^2(\pi/8)\). Thus, \(\Pr(B_1\oplus B_2 \oplus S_1S_2=0) = \cos^2(\pi/8) = \frac{1}{2}+\frac{\sqrt{2}}{4}\). 0◻

References↩︎

---

1. Unless stated otherwise, ‘capacity’ in this work refers exclusively to Shannon capacity, i.e., the supremum of achievable (sum) rates under asymptotically vanishing probability of error as the code lengths approach infinity. Other notions like zero-error capacity, arguably much more fragile, are not considered.↩︎

2. In fact, classical shared randomness between the transmitters and the receiver cannot help to improve the optimal probability of (decoding) error (see Remark 5 in Section 5).↩︎

3. For a point-to-point channel with state, , the entanglement-assisted (in fact even non-signaling assisted) capacity is upper bounded by (see [29]), which evaluates to \(1\) in the example.↩︎

4. XOR games belong to a special class of non-local games, which serve as useful frameworks for studying quantum and general nonlocality.↩︎

5. The players may generate their answers using additional shared randomness; however, this cannot improve the optimal winning probability.↩︎