An official website of the United States government
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
N -Sum Box: An Abstraction for Linear Computation Over Many-to-One Quantum Networks
Linear computations over quantum many-to-one communication networks offer opportunities for communica- tion 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 × 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.
more »
« less
- Award ID(s):
- 2221379
- PAR ID:
- 10651101
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- IEEE Transactions on Information Theory
- Volume:
- 71
- Issue:
- 2
- ISSN:
- 0018-9448
- Page Range / eLocation ID:
- 1121 to 1139
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In the problem of cache-aided Multiuser Private Information Retrieval (MuPIR), a set of Ku cache-aided users wish to download their desired messages from a set of N distributed non-colluding databases each holding a library of K independent messages. The communication load of this problem is defined as the total number of bits downloaded (normalized by the message length) by the users. The goal is to find the optimal memory-load trade-off under the constraint of user demand privacy, which ensures that any individual database learns nothing about the demands of the users. In this paper, for the MuPIR problem with K = 2 messages, K u = 2 users and N ≥ 2 databases, we provide achievability for the memory-load pairs (N-1/2N, N+1/N) and(2(N-1)/2N-1,N+1/2N-1) by constructing specific achievable schemes based on the novel idea of Private Cacheaided Interference Alignment (PCIA). We prove that the proposed scheme is optimal if the cache placement is uncoded (i.e., users directly cache a subset of the library bits). Computer-aided investigation also shows that the proposed schemes are optimal in general when N = 2, 3.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
-
In the problem of cache-aided Multiuser Private Information Retrieval (MuPIR), a set of K u cache-aided users wish to download their desired messages from a set of N distributed non-colluding databases each holding a library of K independent messages. The communication load of this problem is defined as the total number of bits downloaded (normalized by the message length) by the users. The goal is to find the optimal memory-load trade-off under the constraint of user demand privacy, which ensures that any individual database learns nothing about the demands of the users. In this paper, for the MuPIR problem with K=2 messages, Ku=2 users and N≥2 databases, we provide achievability for the memory-load pairs (N−12N,N+1N) and (2(N−1)2N−1,N+12N−1) by constructing specific achievable schemes based on the novel idea of Private Cache-aided Interference Alignment (PCIA). We prove that the proposed scheme is optimal if the cache placement is uncoded (i.e., users directly cache a subset of the library bits). Computer-aided investigation also shows that the proposed schemes are optimal in general when N=2,3.more » « less
-
A communication-efficient protocol is introduced over a many-to-one quantum network for Q-E-B-MDS-X-TPIR, i.e., quantum private information retrieval with MDS-X-secure storage and T-private queries. The protocol is resilient to any set of up to E unresponsive servers (erased servers or stragglers) and any set of up to B Byzantine servers. The underlying coding scheme incorporates an enhanced version of a Cross Subspace Alignment (CSA) code, namely a Modified CSA (MCSA) code, into the framework of CSS codes. The error- correcting capabilities of CSS codes are leveraged to encode the dimensions that carry desired computation results from the MCSA code into the error space of the CSS code, while the undesired interference terms are aligned into the stabilized code space. The challenge is to do this efficiently while also correcting quantum erasures and Byzantine errors. The protocol achieves superdense coding gain over comparable classical baselines for Q-E-B-MDS-X-TPIR, recovers as special cases the state of art results for various other quantum PIR settings previously studied in the literature, and paves the way for applications in quantum coded distributed computation, where CSA code structures are important for communication efficiency, while security and resilience to stragglers and Byzantine servers are critical.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1109/TIT.2024.3514921
