Search for: All records

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. 

Motivated by an open problem and a conjecture, this work studies the problem of single server private information retrieval with private coded side information (PIR-PCSI) that was recently introduced by Heidarzadeh et al. The goal of PIR-PCSI is to allow a user to efficiently retrieve a desired message Wθ, which is one of K independent messages that are stored at a server, while utilizing private side information of a linear combination of a uniformly chosen size-M subset (S ⊂ [K]) of messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond to the constraints that θ is generated uniformly from [K]\S, and S, respectively. In each case, (θ, S) must be kept private from the server. The capacity is defined as the supremum over message and field sizes, of achievable rates (number of bits of desired message retrieved per bit of download) and is characterized by Heidarzadeh et al. for PIR-PCSI-I in general, and for PIR- PCSI-II for M > (K + 1)/2 as (K − M + 1)−1. For 2 ≤ M ≤ (K + 1)/2 the capacity of PIR-PCSI-II remains open, and it is conjectured that even in this case the capacity is (K − M + 1)−1. We show the capacity of PIR-PCSI-II is equal to 2/K for 2 ≤ M ≤ K+1, which is strictly larger 2 than the conjectured value, and does not depend on M within this parameter regime. Remarkably, half the side-information is found to be redundant. We also characterize the infimum capacity (infimum over fields instead of supremum), and the capacity with private coefficients. The results are generalized to PIR-PCSI-I (θ ∈ [K] \ S) and PIR-PCSI (θ ∈ [K]) settings. 

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.