An open question recently posed by Fawzi and Ferme [IEEE Transactions on Information Theory 2024], asks whether non-signaling (NS) assistance can increase the capacity of a broadcast channel (BC). We answer this question in the affirmative, by showing that for a certainK-receiver BC model, called Coordinated Multipoint broadcast (CoMP BC) that arises naturally in wireless networks, NS-assistance provides multiplicative gains in both capacity and degrees of freedom (DoF), even achievingK-fold improvements in extremal cases. Somewhat surprisingly, this is shown to be true even for 2-receiver broadcast channels that are semi-deterministic and/or degraded. In a CoMP BC,Bsingle-antenna transmitters, supported by a backhaul that allows them to share data, act as oneB-antenna transmitter, to send independent messages toKreceivers, each equipped with a single receive antenna. A fixed and globally known connectivity matrix specifies for each transmit antenna, the subset of receivers that are connected to (have a non-zero channel coefficient to) that antenna. Besides the connectivity, there is no channel state information at the transmitter. The receivers have perfect channel knowledge. We show that NS-assistance has no DoF advantage in a fully connected CoMP BC. The DoF region is fully characterized for a class of connectivity patterns associated with tree graphs, for which the classical sum-DoF value is shown to be the number of leaf nodes, while the NS-assisted sum-DoF value is the total number of all (non-root) nodes. For arbitrary connectivity patterns, the sum-capacity with NS-assistance is bounded above and below by the min-rank and triangle number of the connectivity matrix, respectively, leading to matching bounds in many cases, e.g., if min(B,K) ≤ 6. While translations to Gaussian settings are demonstrated, for simplicity most of our results are presented under noise-free, finite-field (Fq) models. Converse proofs for classical DoF are found by adapting the Aligned Images bounds to the finite field model. Converse bounds for NS-assisted DoF/capacity extend the same-marginals property to the BC with NS-assistance available to all parties. Beyond the BC setting, even stronger (unbounded) gains in capacity due to NS-assistance are established for certain ‘communication with side-information’ settings, such as the fading dirty paper channel.

This work explores the potential for improvement, due to non-signaling (NS) assistance, in the degrees of freedom (DoF) of a wireless network. The focus is on a$K$-user MISO BC, i.e., a broadcast channel where a transmitter, equipped with$K$antennas, sends independent messages to$K$receivers, each equipped with a single receive antenna. The network has triangular connectivity, so Receiver$k, k\in \{1, 2,\ldots, K\}$, sees in superposition with the signal sent from the$k^{tk}$transmit antenna, a linear combination of signals sent from the first$k$- 1 antennas, with random channel fading coefficients whose values are unknown to the transmitter but known to the receiver. Prior work has shown that such a MISO BC has$K$DoF with perfect channel state information at the transmitter (CSIT), but the DoF collapse to 1 under limited CSIT. The latter corresponds to the setting considered in this work. The main discovery is that NS assistance can increase the DoF of such a$K$-user wireless network, from 1 to$K$, fully compensating for limited CSIT. For simplicity, the result is presented here in a noise-free, finite-field$(\mathrm{F}_{q}$) model, where NS assistance enables a$K$-fold increase in Shannon capacity as$q\rightarrow\infty$.

Entanglement is known to significantly improve the performance (separately) of communication and detection schemes that utilize quantum resources. This work explores the simultaneous utility of quantum entanglement for (joint) communication and detection schemes, over channels that are convex combinations of identity, depolarization and erasure operators, both with perfect and imperfect entanglement assistance. The channel state is binary, rapidly time-varying and unknown to the transmitter. While the communication is delay-tolerant, allowing the use of arbitrarily long codewords to ensure reliable decoding, the channel state detection is required to be instantaneous. The detector is neither co-located with the transmitter, nor able to wait for the decoding in order to learn the transmitted waveform. The results of this work appear in the form of communication-rate vs instantaneous-detection-error tradeoffs, with and without quantum entanglement. Despite the challenges that place the two tasks at odds with each other, the results indicate that quantum entanglement can indeed be simultaneously and significantly beneficial for joint communication and instantaneous detection.

Linear computations over quantum many-to-one communication networks offer opportunities for communication cost improvements through schemes that exploit quantum entanglement among transmitters to achieve superdense coding gains, combined with classical techniques such as interference alignment. The problem becomes much more broadly accessible if suitable abstractions can be found for the underlying quantum functionality via classical black box models. This work formalizes such an abstraction in the form of an “N-sum box”, a black box generalization of a two-sum protocol of Song et al. with recent applications to N-server private information retrieval. The N-sum box has a communication cost of N qudits and classical output of a vector of$N~q$-ary digits linearly dependent (via an$N \times 2N$transfer matrix) on$2N$classical inputs distributed among N transmitters. We characterize which transfer matrices are feasible by our construction, both with and without the possibility of additional locally invertible classical operations at the transmitters and receivers. Furthermore, we provide a sample application to Cross-Subspace Alignment (CSA) schemes to obtain efficient instances of Quantum Private Information Retrieval (QPIR) and Quantum Secure Distributed Batch Matrix Multiplication (QSDBMM). We first describe N-sum boxes based on maximal stabilizers and we then consider non-maximal-stabilizer-based constructions to obtain an instance of Quantum Symmetric Private Information Retrieval.

The optimal quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).Kclassical messages comprised of finite-field symbols are distributed acrossSservers, who also share quantum entanglement in advance. Each servers∈ [S] manipulates its quantum subsystemQsaccording to its own available classical messages and sendsQsto the receiver who then computes the sum of the messages based on a joint quantum measurement. The download cost from Servers∈ [S] is the logarithm of the dimension ofQs. The rateRis defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. The main focus is on the symmetric setting withK= (Sα) messages where each message is replicated among a unique subset of α servers, and the answers from any β servers may be erased. If no entanglement is initially available to the receiver, then we show that the capacity (maximal rate) is preciselyC= max { min { 2(α−β)/S,S−2β/S}, α−β/S}. The capacity with arbitrary levels of prior entanglement (Δ0) between theSdata-servers and the receiver is also characterized, by including an auxiliary server (Server 0) that has no classical data, so that the communication cost from Server 0 is a proxy for the amount of receiver-side entanglement that is available in advance. The challenge on the converse side resides in the optimal application of the weak monotonicity property, while the achievability combines ideas from classical network coding and treating qudits as classical dits, as well as new constructions based on the N-sum box abstraction that rely on absolutely maximally entangled quantum states.

The quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).$K$- messages are distributed across$S$servers so that each server knows a subset of the messages. Each server$\mathrm{s}\in[S]$sends a quantum subsystem$\mathcal{Q}_{s}$to the receiver who computes the sum of the messages. The download cost from Server$s\in[S]$is the logarithm of the dimension of$\mathcal{Q}_{s}$. The rate$R$: is defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. In the symmetric setting with$K=\left(_{\alpha}^{S}\right)$messages where each message is replicated among a unique subset of$\alpha$servers, and the answers from any$\beta$servers may be erased, the rate achieved is$R=\max \left\{\min \left\{\frac{2(\alpha-\beta)}{S}, 1-\frac{2 \beta}{S}\right\}, \frac{\alpha-\beta}{S}\right\}$.

Linear computation broadcast (LCBC) refers to a setting withddimensional data stored at a central server, whereKusers, each with some prior linear side-information, wish to compute various linear combinations of the data. For each computation instance, the data is represented as ad-dimensional vector with elements in a finite field Fpnwherepnis a power of a prime. The computation is to be performed many times, and the goal is to determine the minimum amount of information per computation instance that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost per computation instance is the capacity of LCBC. The capacity is known for up toK= 3 users. Since LCBC includes index coding as a special case, largeKsettings of LCBC are at least as hard as the index coding problem. As such the general LCBC problem is beyond our reach and we do not pursue it. Instead of the general setting (allcases), by focusing on thegenericsetting (almost allcases) this work shows that the generic capacity of the symmetric LCBC (where every user hasm’ dimensions of side-information andmdimensions of demand) for large number of users (K≥dsuffices) isCg= 1/Δg, where Δg= min { max{0,d-m′},dm/m+m′}, is the broadcast cost that is both achievable and unbeatable asymptotically almost surely for largen, among all LCBC instances with the given parametersp,K,d,m,m′. Relative to baseline schemes of random coding or separate transmissions,Cgshows an extremal gain by a factor ofKas a function of number of users, and by a factor of ≈d/4 as a function of data dimensions, when optimized over remaining parameters. For arbitrary number of users, the generic capacity of the symmetric LCBC is characterized within a factor of 2.

The K User Linear Computation Broadcast (LCBC) problem is comprised of d dimensional data (from$\mathbb {F}_{q}$), that is fully available to a central server, and K users, who require various linear computations of the data, and have prior knowledge of various linear functions of the data as side-information. The optimal broadcast cost is the minimum number of q-ary symbols to be broadcast by the server per computation instance, for every user to retrieve its desired computation. The reciprocal of the optimal broadcast cost is called the capacity. The main contribution of this paper is the exact capacity characterization for the$K=3$user LCBC for all cases, i.e., for arbitrary finite fields$\mathbb {F}_{q}$, arbitrary data dimension d, and arbitrary linear side-informations and demands at each user. A remarkable aspect of the converse (impossibility result) is that unlike the 2 user LCBC whose capacity was determined previously, the entropic formulation (where the entropies of demands and side-informations are specified, but not their functional forms) is insufficient to obtain a tight converse for the 3 user LCBC. Instead, the converse exploits functional submodularity. Notable aspects of achievability include sufficiency of vector linear coding schemes, subspace decompositions that parallel those found previously by Yao Wang in degrees of freedom (DoF) studies of wireless broadcast networks, and efficiency tradeoffs that lead to a constrained waterfilling solution. Random coding arguments are invoked to resolve compatibility issues that arise as each user has a different view of the subspace decomposition, conditioned on its own side-information.

The Σ-QMAC problem is introduced, involvingSservers,Kclassical (Fd) data streams, andTindependent quantum systems. Data stream Wk,k∈ [K] is replicated at a subset of servers W(k) ⊂ [S], and quantum system Qt,t∈ [T] is distributed among a subset of servers ε(t) ⊂ [S] such that Servers∈ ε(t) receives subsystem Qt,sof Qt= (Qt,s)s∈ε(t). Servers manipulate their quantum subsystems according to their data and send the subsystems to a receiver. The total download cost is Σt∈[T]Σs∈ε(t)logd|Qt,s| qudits, where |Q| is the dimension of Q. The states and measurements of (Qt)t∈[T]are required to be separable acrosst∈ [T] throughout, but for eacht∈ [T], thesubsystemsof Qtcan be prepared initially in an arbitrary (independent of data) entangled state, manipulated arbitrarily by the respective servers, and measured jointly by the receiver. From the measurements, the receiver must recover the sum of all data streams. Rate is defined as the number of dits (Fdsymbols) of the desired sum computed per qudit of download. The capacity of Σ-QMAC, i.e., the supremum of achievable rates is characterized for arbitrary data and entanglement distributions W, ε. For example, in the symmetric setting withK= (Sα) data-streams, each replicated among a distinct α-subset of [S], andT= (Sβ) quantum systems, each distributed among a distinct β-subset of [S], the capacity of the Σ-QMAC is 1/βTΣmin(α,β)γ=(α+β−S)+ min(β, 2γ) · (αγ) · (S−αβ−γ). Coding based on the N-sum box abstraction is optimal in every case. Notably, for everyS≠ 3 there exists an instance of the Σ-QMAC whereS-party entanglement is necessary to achieve the fully entangled capacity.

Linear computations over quantum many-to-one communication networks offer opportunities for communication cost improvements through schemes that exploit quantum entanglement among transmitters to achieve superdense coding gains, combined with classical techniques such as interference alignment. The problem becomes much more broadly accessible if suitable abstractions can be found for the underlying quantum functionality via classical black box models. This work formalizes such an abstraction in the form of an “N-sum box”, a black box generalization of a two-sum protocol of Song et al. with recent applications to$N$-server private information retrieval. The N- sum box has a communication cost of$N$qudits and classical output of a vector of$N$q-ary digits linearly dependent (via an N x 2N transfer matrix) on 2N classical inputs distributed among$N$transmitters. We characterize which transfer matrices are feasible by our construction, both with and without the possibility of additional locally invertible classical operations at the transmitters and receivers.

The problem of entanglement-assisted summation over a quantum multiple access channel ($\Sigma$-QMAC) is intro-duced, involving$S$servers,$K$classical$(\mathbb{F}_{d})$data streams that are replicated arbitrarily across various subsets of servers, and a receiver who wishes to compute the sum of the$K$data streams. Independent of the data, entangled quantum systems$\mathcal{Q}_{1}, \mathcal{Q}_{2}, \cdots, \mathcal{Q}_{S}$are prepared in advance and distributed to the corresponding servers. Each server$s, s\in[S]$locally manipulates its quantum system$\mathcal{Q}_{s}$according to its classical data and sends$\mathcal{Q}_{s}$to the receiver. The total communication cost is$\log_{d}\vert \mathcal{Q}_{1}\vert +\log_{d}\vert \mathcal{Q}_{2}\vert +\cdots+\log_{d}\vert \mathcal{Q}_{S}\vert$qudits, where$\vert \mathcal{Q}_{s}$denotes the dimension of$\mathcal{Q}_{s}$. Based on a measurement of the composite system$\mathcal{Q}_{1}\mathcal{Q}_{2}\cdots \mathcal{Q}_{S}$, the receiver must recover the desired sum. The rate thus achieved is defined as the number of dits$(\mathbf{F}_{d}$symbols) of the desired sum computed by the receiver per qudit (d-dimsional quantum system) of download. The capacity$C$is the supremum of the set of all achievable rates. As the main result of this work, the precise capacity of$\Sigma$-QMAC is obtained, from which it follows that quantum entanglements allow a factor of 2 gain in capacity (superdense coding gain) relative to capacity with no entanglements, in all cases (any$S, K, \mathbf{F}_{d}$and any data replication pattern) provided that the entanglement-assisted capacity does not exceed 1 dit/qudit (Holevo bound). Coding schemes based on a recent$N$-sum box abstraction are sufficient to achieve capacity.

The symmetric linear (over$\mathbb{F}_{p^{n}}$) computation broadcast (LCBC) problem considered in this work refers to a setting with$d$dimensional data stored at a central server, where$K$users, each with some$m^{\prime}$dimensional prior linear side-information, wish to retrieve various$m$dimensional linear combinations of the data. The goal is to determine the minimum amount of (potentially non-linear) coded information that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost is the capacity of LCBC. The capacity has been found previously for up to$K=3$users. Since LCBC includes index coding as a special case, LCBC settings with large number of users are at least as hard as the index coding problem. Instead of the general setting (all instances), here we make progress by focusing on the generic setting (almost all instances). For the LCBC with$d=4$dimensional data, and 1 dimensional demands and side-information$(m=m^{\prime}=1)$, we establish the generic capacity$C_{g}=\max(1/2,1/K)$, for any number of users$K$. This is the information theoretic capacity of almost all LCBC instances with$d=4, m=1, m^{\prime}=1$as$n\rightarrow\infty$for any field characteristic$p$and any number of users$K^{1}$

Introduced by Sadeh et al., the K-star-graph private information retrieval (PIR) problem, so-labeled because the storage graph is a star-graph with K leaf nodes, is comprised of K messages that are stored separately (one-each) at K dedicated servers, and a universal server that stores all K messages, for a total of K + 1 servers. While it is one of the simplest PIR settings to describe, the capacity CKof K-star-graph PIR is open for K ≥ 4. We study the critical K = 4 setting, for which prior work establishes the bounds 2/5 ≤ C4≤ 3/7. As our main contribution, we characterize the exact capacity of 4-star-graph PIR as C4= 5/12, thus improving upon both the prior lower-bound as well as the prior upper-bound. The main technical challenge resides in the new converse bound, whose non-trivial structure is deduced indirectly from the achievable schemes that emerge from the study of a finer tradeoff between the download costs from the dedicated servers versus the universal server. A sharp characterization of this tradeoff is also obtained for K = 4.

The linear computation broadcast (LCBC) problem studied in this work is comprised of a d dimensional data vector X that is stored at a server, and 3 users, such that the kthuser, k ∈ [1 : 3], has 1 dimensional demand Wk= XTvkand 1 dimensional side-information ${\text{W}}_k^\prime{\text{ = }}{{\text{X}}^T}{\text{v}}_k^\prime$, that are arbitrary linear combinations of the data vector over a finite field ${\mathbb{F}_q}$. The optimal broadcast cost Δ* is the minimum amount of information that the server must broadcast in order to satisfy all three users' demands. The main result of this work is the exact characterization of Δ*, which is shown to only take one of the values: 0, 1, 1.5, 2, 3 in all cases. In contrast to the 2 user setting previously studied by Sun and Jafar, it turns out that in the 3 user LCBC, scalar linear coding is insufficient to construct optimal achievable schemes, and the entropic formulation (where the entropies of all subsets of $\left\{ {{{\mathbf{W}}_1},{{\mathbf{W}}_2},{{\mathbf{W}}_3},{\mathbf{W}}_1^\prime,{\mathbf{W}}_2^\prime,{\mathbf{W}}_3^\prime} \right\}$ are specified, but not their functional forms) is insufficient to obtain a tight converse. Instead, we need vector coding and functional submodularity, especially in those cases where Δ*= 1.5. Remarkably, for a given dimensional specification d, while Δ*can take different values depending on the realizations of ${{\mathbf{v}}_k},{\mathbf{v}}_k^\prime$, almost all realizations over a large field yield the same Δ*as a function of d, which happens to be 0, 1, 1.5, 2, 2, 3 for d = 1, 2, 3, 4, 5, 6+, respectively.