Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2304.07561

$N$-Sum Box: An Abstraction for Linear Computation over Many-to-one Quantum Networks

Matteo Allaix, Yuxiang Lu, Yuhang Yao, Tefjol Pllaha, Camilla Hollanti, Jafar, Syed

Published Apr 15, 2023• 0 citations
arXivHTMLPDF

Abstract

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 \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.

DOI
10.48550/arxiv.2304.07561

Related papers

N-Sum Box: An Abstraction for Linear Computation Over Many-to-One Quantum Networks

Matteo Allaix, Yuxiang Lu, Yuhang Yao +3 more

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.

IEEE Transactions on Information Theory•Dec 11, 2024•8 citations

N-Sum Box: An Abstraction for Linear Computation over Many-to-one Quantum Networks

Matteo Allaix, Yuxiang Lu, Yuhang Yao +3 more

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.

Globecom•Dec 4, 2023•16 citations

Precoding-based protocols for entanglement assisted linear computation over a quantum many-to-one network

Ruoyu Meng, Aditya Ramamoorthy

In this work, we consider the problem of computing a linear combination over a noiseless quantum many-to-one network. There are $k$ senders, Alice$_1$, $\ldots$, Alice$_k$, and a single receiver, Bob. Each Alice$_i$ has a data vector $W_i \in \mathbb{F}^{m_i}$, where $\mathbb{F}$ is a finite field. Bob wants to compute the linear combination $Y = V_1 W_1 + V_2 W_2 + \cdots + V_k W_k \in \mathbb{F}^m$, where $V_i$ is an $m \times m_i$ matrix over $\mathbb{F}$. The senders transmit quantum states to Bob through a noiseless many-to-one quantum network, but they are not allowed to communicate with each other. The senders share entanglement among themselves, while Bob does not share this entanglement. They encode their classical information $W_i$, $i=1,\ldots,k$, into their local subsystems and transmit them to Bob so that he can recover $Y$ through a quantum measurement and subsequent post-processing. The N-Sum Box protocol proposed by Allaix et al. (2025) considers this problem under certain constraints on the linear combination and the distribution of the data vectors among the senders. We present protocols that support the computation of a more general class of linear transformations by giving the senders access to more qudits and allowing them to judiciously precode their input symbols. The communication cost of our schemes is at most that of the best-known prior results in this area and is strictly lower in certain cases. Finally, we demonstrate that the communication cost is subadditive across instances. Specifically, we identify two linear functions for which the total cost of computing them individually is strictly larger than the cost of computing them jointly.

cs.ITCross-listedarXiv:2607.13756•Jul 16, 2026•0 citations

Quantum Cross Subspace Alignment Codes via the N-sum Box Abstraction

Yuxiang Lu, Syed A. Jafar

Cross-subspace alignment (CSA) codes are used in various private information retrieval (PIR) schemes (e.g., with secure storage) and in secure distributed batch matrix multiplication (SDBMM). Using a recently developed$N$-sum box abstraction of a quantum multiple-access channel (QMAC), we translate CSA schemes over classical multiple-access channels into efficient quantum CSA schemes over a QMAC, achieving maximal superdense coding gain. Because of the$N$-sum box abstraction, the underlying problem of coding to exploit quantum entanglements for CSA schemes, becomes conceptually equivalent to that of designing a channel matrix for a MIMO MAC subject to given structural constraints imposed by the$N$-sum box abstraction, such that the resulting MIMO MAC is able to implement the functionality of a CSA scheme (encoding/decoding) over-the-air. Applications include Quantum PIR with secure and MDS-coded storage, as well as Quantum SDBMM.

arXiv:2304.14676•Asilomar Conference on Signals, Systems and Computers (ACSSC)•Oct 29, 2023•10 citations

On the Capacity of Vector Linear Computation Over a Noiseless Quantum Multiple-Access Channel With Entangled Transmitters

Yuhang Yao, Syed A. Jafar

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 linear function of data streams defined in a finite field$\mathbb {F}_{d}$, the LC-QMAC problem seeks the optimal communication cost (minimum number of qudits that need to be sent by the transmitters to the receiver, per computation instance) over a noise-free QMAC, when the independent input data streams 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\geq 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.

arXiv:2407.01498•IEEE Transactions on Quantum Engineering•Jan 1, 2025•2 citations

The Capacity of Classical Summation over a Quantum MAC with Arbitrarily Replicated Inputs

Yuhang Yao, Syed A. Jafar

The problem of entanglement-assisted summation over a quantum multiple access channel ($\Sigma$-QMAC) is intro-duced, involving$S$servers,$K$classical$(\mathbb{F}_{d})$data streams that are replicated arbitrarily across various subsets of servers, and a receiver who wishes to compute the sum of the$K$data streams. Independent of the data, entangled quantum systems$\mathcal{Q}_{1}, \mathcal{Q}_{2}, \cdots, \mathcal{Q}_{S}$are prepared in advance and distributed to the corresponding servers. Each server$s, s\in[S]$locally manipulates its quantum system$\mathcal{Q}_{s}$according to its classical data and sends$\mathcal{Q}_{s}$to the receiver. The total communication cost is$\log_{d}\vert \mathcal{Q}_{1}\vert +\log_{d}\vert \mathcal{Q}_{2}\vert +\cdots+\log_{d}\vert \mathcal{Q}_{S}\vert$qudits, where$\vert \mathcal{Q}_{s}$denotes the dimension of$\mathcal{Q}_{s}$. Based on a measurement of the composite system$\mathcal{Q}_{1}\mathcal{Q}_{2}\cdots \mathcal{Q}_{S}$, the receiver must recover the desired sum. The rate thus achieved is defined as the number of dits$(\mathbf{F}_{d}$symbols) of the desired sum computed by the receiver per qudit (d-dimsional quantum system) of download. The capacity$C$is the supremum of the set of all achievable rates. As the main result of this work, the precise capacity of$\Sigma$-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, \mathbf{F}_{d}$and 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.

Globecom•Dec 4, 2023•5 citations
NNN-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 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 "NNN-sum box", a black box generalization of a two-sum protocol of Song \emph{et al.} with recent applications to NNN-server private information retrieval. The NNN-sum box has a communication cost of NNN qudits and classical output of a vector of NNN qqq-ary digits linearly dependent (via an N×2NN \times 2NN×2N transfer matrix) on 2N2N2N classical inputs distributed among NNN 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 NNN-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 ofN qN~qN q-ary digits linearly dependent (via anN×2NN \times 2NN×2Ntransfer matrix) on2N2N2Nclassical 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 toNNN-server private information retrieval. The N- sum box has a communication cost ofNNNqudits and classical output of a vector ofNNNq-ary digits linearly dependent (via an N x 2N transfer matrix) on 2N classical inputs distributed amongNNNtransmitters. 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.
In this work, we consider the problem of computing a linear combination over a noiseless quantum many-to-one network. There are kkk senders, Alice1_11​, …\ldots…, Alicek_kk​, and a single receiver, Bob. Each Alicei_ii​ has a data vector Wi∈FmiW_i \in \mathbb{F}^{m_i}Wi​∈Fmi​, where F\mathbb{F}F is a finite field. Bob wants to compute the linear combination Y=V1W1+V2W2+⋯+VkWk∈FmY = V_1 W_1 + V_2 W_2 + \cdots + V_k W_k \in \mathbb{F}^mY=V1​W1​+V2​W2​+⋯+Vk​Wk​∈Fm, where ViV_iVi​ is an m×mim \times m_im×mi​ matrix over F\mathbb{F}F. The senders transmit quantum states to Bob through a noiseless many-to-one quantum network, but they are not allowed to communicate with each other. The senders share entanglement among themselves, while Bob does not share this entanglement. They encode their classical information WiW_iWi​, i=1,…,ki=1,\ldots,ki=1,…,k, into their local subsystems and transmit them to Bob so that he can recover YYY through a quantum measurement and subsequent post-processing. The N-Sum Box protocol proposed by Allaix et al. (2025) considers this problem under certain constraints on the linear combination and the distribution of the data vectors among the senders. We present protocols that support the computation of a more general class of linear transformations by giving the senders access to more qudits and allowing them to judiciously precode their input symbols. The communication cost of our schemes is at most that of the best-known prior results in this area and is strictly lower in certain cases. Finally, we demonstrate that the communication cost is subadditive across instances. Specifically, we identify two linear functions for which the total cost of computing them individually is strictly larger than the cost of computing them jointly.
Cross-subspace alignment (CSA) codes are used in various private information retrieval (PIR) schemes (e.g., with secure storage) and in secure distributed batch matrix multiplication (SDBMM). Using a recently developedNNN-sum box abstraction of a quantum multiple-access channel (QMAC), we translate CSA schemes over classical multiple-access channels into efficient quantum CSA schemes over a QMAC, achieving maximal superdense coding gain. Because of theNNN-sum box abstraction, the underlying problem of coding to exploit quantum entanglements for CSA schemes, becomes conceptually equivalent to that of designing a channel matrix for a MIMO MAC subject to given structural constraints imposed by theNNN-sum box abstraction, such that the resulting MIMO MAC is able to implement the functionality of a CSA scheme (encoding/decoding) over-the-air. Applications include Quantum PIR with secure and MDS-coded storage, as well as Quantum SDBMM.
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 linear function of data streams defined in a finite fieldFd\mathbb {F}_{d}Fd​, the LC-QMAC problem seeks the optimal communication cost (minimum number of qudits that need to be sent by the transmitters to the receiver, per computation instance) over a noise-free QMAC, when the independent input data streams originate at the corresponding transmitters, who share quantum entanglement in advance. As our main result, we fully solve this problem forK=3K=3K=3transmitters (K≥4K\geq 4K≥4settings remain open). Coding schemes based on theNNN-sum box protocol (along with time-sharing and batch-processing) are shown to be information theoretically optimal in all cases.
The problem of entanglement-assisted summation over a quantum multiple access channel (Σ\SigmaΣ-QMAC) is intro-duced, involvingSSSservers,KKKclassical(Fd)(\mathbb{F}_{d})(Fd​)data streams that are replicated arbitrarily across various subsets of servers, and a receiver who wishes to compute the sum of theKKKdata streams. Independent of the data, entangled quantum systemsQ1,Q2,⋯ ,QS\mathcal{Q}_{1}, \mathcal{Q}_{2}, \cdots, \mathcal{Q}_{S}Q1​,Q2​,⋯,QS​are prepared in advance and distributed to the corresponding servers. Each servers,s∈[S]s, s\in[S]s,s∈[S]locally manipulates its quantum systemQs\mathcal{Q}_{s}Qs​according to its classical data and sendsQs\mathcal{Q}_{s}Qs​to the receiver. The total communication cost islog⁡d∣Q1∣+log⁡d∣Q2∣+⋯+log⁡d∣QS∣\log_{d}\vert \mathcal{Q}_{1}\vert +\log_{d}\vert \mathcal{Q}_{2}\vert +\cdots+\log_{d}\vert \mathcal{Q}_{S}\vertlogd​∣Q1​∣+logd​∣Q2​∣+⋯+logd​∣QS​∣qudits, where∣Qs\vert \mathcal{Q}_{s}∣Qs​denotes the dimension ofQs\mathcal{Q}_{s}Qs​. Based on a measurement of the composite systemQ1Q2⋯QS\mathcal{Q}_{1}\mathcal{Q}_{2}\cdots \mathcal{Q}_{S}Q1​Q2​⋯QS​, the receiver must recover the desired sum. The rate thus achieved is defined as the number of dits(Fd(\mathbf{F}_{d}(Fd​symbols) of the desired sum computed by the receiver per qudit (d-dimsional quantum system) of download. The capacityCCCis the supremum of the set of all achievable rates. As the main result of this work, the precise capacity ofΣ\SigmaΣ-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 (anyS,K,FdS, K, \mathbf{F}_{d}S,K,Fd​and any data replication pattern) provided that the entanglement-assisted capacity does not exceed 1 dit/qudit (Holevo bound). Coding schemes based on a recentNNN-sum box abstraction are sufficient to achieve capacity.