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.

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.

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. In this work, a flexible and robust private information retrieval (PIR) scheme based on binary non-maximum distance separable (non-MDS) codes is considered. This combines previous works on PIR schemes based on transitive non-MDS codes on one hand, and PIR from MDS-coded Byzantine and nonresponsive servers on the other hand. More specifically, a PIR scheme employing binary Reed–Muller (RM) codes tolerant to colluding, Byzantine, and non-responsive servers is constructed, and bounds for the achievable rates are derived under certain conditions. The construction of such schemes turns out to be much more involved than for MDS codes. Namely, the binary query vectors have to be selected with great care to hit the desired information sets, which is technically challenging as will be shown.

In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollantiet al.and the stabilizer QPIR scheme by Songet al.by employing (weakly) self-dual Reed–Solomon codes.

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both with and without collusion. QPIR over [n, k] maximum distance separable (MDS) coded servers was recently considered by Allaix et al., but the collusion was essentially restricted to t = n -$k$servers in the sense that a smaller$t$would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers$t$with 1 ≤$t$≤$n$- k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed-Solomon (GRS) star product codes.

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by downloading quantum systems from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any [n, k]-MDS code and t-collusion with t = n - k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts.