An official website of the United States government
Linear computation broadcast (LCBC) refers to a setting with d dimensional data stored at a central server, where K users, 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 a d-dimensional vector with elements in a finite field Fpn where pn is 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 to K = 3 users. Since LCBC includes index coding as a special case, large K settings 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 (all cases), by focusing on the generic setting (almost all cases) this work shows that the generic capacity of the symmetric LCBC (where every user has m′ dimensions of side-information and m dimensions of demand) for large number of users (K ≥ d suffices) is Cg = 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 large n, among all LCBC instances with the given parameters p, K, d, m, m′. Relative to baseline schemes of random coding or separate transmissions, Cg shows an extremal gain by a factor of K as 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.
more »
« less
This content will become publicly available on October 1, 2026
On the Capacity of Vector Linear Computation Over a Noiseless Quantum Multiple-Access Channel With Entangled Transmitters
Network function computation is an active topic in network coding, with much recent progress for linear (over a finite field) computations over broadcast (LCBC) and multiple access (LCMAC) channels. Over a quantum multiple access channel (QMAC) with quantum-entanglement shared among transmitters, the linear computation problem (LC-QMAC) is non-trivial even when the channel is noiseless, because of the challenge of optimally exploiting transmit-side entanglement through distributed coding. Given an arbitrary Fd linear function, f(W1,···,WK) = V1W1 +V2W2 +···+VKWK ∈Fm×1 d , the LC- QMAC problem seeks the optimal communication cost (minimum number of qudits ∆1,··· ,∆K that need to be sent by transmitters Alice1, Alice2, ···, AliceK, respectively, to the receiver, Bob, per computation instance) over a noise-free QMAC, when the input data streams Wk ∈Fmk ×1 d ,k ∈[K], originate at the corresponding transmitters, who share quantum entanglement in advance. As our main result, we fully solve this problem for K = 3 transmitters (K ≥4 settings remain open). Coding schemes based on the N-sum box protocol (along with time-sharing and batch-processing) are shown to be information theoretically optimal in all cases. As an example, in the symmetric case where rk(V1) = rk(V2) = rk(V3) ≜ r1, rk([V1,V2]) = rk([V2,V3]) = rk([V3,V1]) ≜ r2, and rk([V1,V2,V3]) ≜ r3 (rk= rank), the minimum total-download cost is max{1.5r1 + 0.75(r3−r2),r3}.
more »
« less
- Award ID(s):
- 2221379
- PAR ID:
- 10651106
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- IEEE Transactions on Quantum Engineering
- Volume:
- 6
- ISSN:
- 2689-1808
- Page Range / eLocation ID:
- 1 to 20
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The K User Linear Computation Broadcast (LCBC) problem is comprised of d dimensional data (from Fq), 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 Fq, 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.more » « less
-
We derive a family of optimal protocols, in the sense of saturating the quantum Cramér-Rao bound, for measuring a linear combination of d field amplitudes with quantum sensor networks, a key subprotocol of general quantum sensor network applications. We demonstrate how to select different protocols from this family under various constraints. Focusing primarily on entanglement-based constraints, we prove the surprising result that highly entangled states are not necessary to achieve optimality in many cases. Specifically, we prove necessary and sufficient conditions for the existence of optimal protocols using at most k-partite entanglement. We prove that the protocols which satisfy these conditions use the minimum amount of entanglement possible, even when given access to arbitrary controls and ancillas. Our protocols require some amount of time-dependent control, and we show that a related class of time-independent protocols fail to achieve optimal scaling for generic functions.more » « less
-
The optimal quantum communication cost of com- puting a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC). K classical messages comprised of finite-field symbols are distributed across S servers, who also share quantum entanglement in advance. Each server s ∈ [S] manipulates its quantum subsystem Qs according to its own available classical messages and sends Qs to the receiver who then computes the sum of the messages based on a joint quantum measurement. The download cost from Server s ∈ [S] is the logarithm of the dimension of Qs. 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. The main focus is on the symmetric setting with K = 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 precisely C = max ˚min ˚2(α−β) S−2β S , S , α−β S . The capacity with arbitrary levels of prior entanglement (∆0) between the S data-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.more » « less
-
We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for discrete quantum measurement systems with limited classical common randomness. The main coding theorem provides the achievable rate region of a lossy measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an i.i.d. predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination state via an entanglement-breaking channel with limited communication rate and common randomness.more » « less
