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 \emph{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.
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×2Ntransfer matrix) on
2Nclassical 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
Nqudits and classical output of a vector of
Nq-ary digits linearly dependent (via an N x 2N transfer matrix) on 2N classical inputs distributed among
Ntransmitters. 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 (
Σ-QMAC) is intro-duced, involving
Sservers,
Kclassical
(Fd)data streams that are replicated arbitrarily across various subsets of servers, and a receiver who wishes to compute the sum of the
Kdata streams. Independent of the data, entangled quantum systems
Q1,Q2,⋯,QSare prepared in advance and distributed to the corresponding servers. Each server
s,s∈[S]locally manipulates its quantum system
Qsaccording to its classical data and sends
Qsto the receiver. The total communication cost is
logd∣Q1∣+logd∣Q2∣+⋯+logd∣QS∣qudits, where
∣Qsdenotes the dimension of
Qs. Based on a measurement of the composite system
Q1Q2⋯QS, the receiver must recover the desired sum. The rate thus achieved is defined as the number of dits
(Fdsymbols) of the desired sum computed by the receiver per qudit (d-dimsional quantum system) of download. The capacity
Cis the supremum of the set of all achievable rates. As the main result of this work, the precise capacity of
Σ-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,Fdand 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.
To compute a summation
(Σ)of independent classical data streams from multiple servers over a quantum multiple access channel (QMAC), every server must directly send its quantum system containing multiple qudits to the user. Previous work
Σ-QMAC in [1] considers that the servers are entangled. In this work, the maximum rate, defined as the maximum number of dits of the sum computed per qudit transmitted, is derived, and a quantum coding scheme is designed to achieve it. In practice, a server is not always directly connected to the user, necessitating a relay between them for connectivity. Motivated by this, we consider a two-layer quantum MAC (2QMAC) model, where a user is connected to a layer of mirrors, and one of the mirrors (acting as a relay) is connected to a layer of servers. Quantum systems within the same layer are entangled, whereas quantum systems across different layers are independent. In
Σ−2QMAC, deriving the maximum rates of two layers simultaneously is challenging since the rates of the two layers affect each other. To address this, we first derive the maximum rate of the first layer by neglecting the second layer. Second, to relate the rates of the two layers, we derive the maximum rate of the second layer for a given feasible rate (less than the maximum rate) of the first layer. In addition, a joint coding scheme based on the
N-sum box abstraction is designed to achieve the maximum rate of the second layer.
Building on recent constructions of Quantum Cross Subspace Alignment (QCSA) codes, this work develops a coding scheme for QEXSTPIR, i.e., classical private information retrieval with X -secure storage and
T-private queries, over a quantum multiple access channel, that is resilient to any set of up to
Eerased servers (equivalently known as unresponsive servers, or stragglers). The scheme is accordingly labeled QECSA, with the ‘
E,indicating resilience to erased servers. The novelty of QECSA lies in achieving efficient E-straggler resilience on top of existing QCSA codes that already achieve X-secure storage, T- private queries, and distributed superdense coding gains for communication efficient decoding. The QECSA code structure may be broadly useful for problems such as quantum coded secure distributed computation, where security, straggler resilience, and distributed superdense coding gains are simultaneously required.