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:2305.03122 · IEEE Transactions on Information Theory

The Capacity of Classical Summation Over a Quantum MAC With Arbitrarily Distributed Inputs and Entanglements

Yuhang Yao, Syed A. Jafar

Published May 6, 2024• 11 citations
arXivHTMLPDF

Abstract

The Σ-QMAC problem is introduced, involvingSservers,Kclassical (Fd) data streams, andTindependent quantum systems. Data stream Wk,k∈ [K] is replicated at a subset of servers W(k) ⊂ [S], and quantum system Qt,t∈ [T] is distributed among a subset of servers ε(t) ⊂ [S] such that Servers∈ ε(t) receives subsystem Qt,sof Qt= (Qt,s)s∈ε(t). Servers manipulate their quantum subsystems according to their data and send the subsystems to a receiver. The total download cost is Σt∈[T]Σs∈ε(t)logd|Qt,s| qudits, where |Q| is the dimension of Q. The states and measurements of (Qt)t∈[T]are required to be separable acrosst∈ [T] throughout, but for eacht∈ [T], thesubsystemsof Qtcan be prepared initially in an arbitrary (independent of data) entangled state, manipulated arbitrarily by the respective servers, and measured jointly by the receiver. From the measurements, the receiver must recover the sum of all data streams. Rate is defined as the number of dits (Fdsymbols) of the desired sum computed per qudit of download. The capacity of Σ-QMAC, i.e., the supremum of achievable rates is characterized for arbitrary data and entanglement distributions W, ε. For example, in the symmetric setting withK= (Sα) data-streams, each replicated among a distinct α-subset of [S], andT= (Sβ) quantum systems, each distributed among a distinct β-subset of [S], the capacity of the Σ-QMAC is 1/βTΣmin(α,β)γ=(α+β−S)+ min(β, 2γ) · (αγ) · (S−αβ−γ). Coding based on the N-sum box abstraction is optimal in every case. Notably, for everyS≠ 3 there exists an instance of the Σ-QMAC whereS-party entanglement is necessary to achieve the fully entangled capacity.

DOI
10.1109/tit.2024.3397917

Related papers

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

Capacity of Summation Over a Symmetric Quantum Erasure MAC With Partially Replicated Inputs

Yuhang Yao, Syed A. Jafar

The optimal quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).Kclassical messages comprised of finite-field symbols are distributed acrossSservers, who also share quantum entanglement in advance. Each servers∈ [S] manipulates its quantum subsystemQsaccording to its own available classical messages and sendsQsto the receiver who then computes the sum of the messages based on a joint quantum measurement. The download cost from Servers∈ [S] is the logarithm of the dimension ofQs. The rateRis 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 withK= (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 preciselyC= max { min { 2(α−β)/S,S−2β/S}, α−β/S}. The capacity with arbitrary levels of prior entanglement (Δ0) between theSdata-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.

arXiv:2311.08386•IEEE Transactions on Information Theory•May 14, 2025•1 citation

Communication Efficiency of Summation Over a Two-Layer Quantum MAC

Huaming Mai, Wenkang Cen, Jinbei Zhang +1 more

To compute a summation$(\Sigma)$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$\Sigma$-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$\Sigma-2\text{QMAC}$, 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.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 24, 2024•1 citation

Communication Efficiency of Summation over a Quantum Erasure MAC with Replicated Inputs

Yuhang Yao, Syed A. Jafar

The quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).$K$- messages are distributed across$S$servers so that each server knows a subset of the messages. Each server$\mathrm{s}\in[S]$sends a quantum subsystem$\mathcal{Q}_{s}$to the receiver who computes the sum of the messages. The download cost from Server$s\in[S]$is the logarithm of the dimension of$\mathcal{Q}_{s}$. 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. In the symmetric setting with$K=\left(_{\alpha}^{S}\right)$messages where each message is replicated among a unique subset of$\alpha$servers, and the answers from any$\beta$servers may be erased, the rate achieved is$R=\max \left\{\min \left\{\frac{2(\alpha-\beta)}{S}, 1-\frac{2 \beta}{S}\right\}, \frac{\alpha-\beta}{S}\right\}$.

International Conference on Communications•Jun 9, 2024•1 citation

Entanglement-Assisted Coding for Arbitrary Linear Computations Over a Quantum MAC

Lei Hu, Mohamed W. Nomeir, Alptug Aytekin +3 more

We study a linear computation problem over a quantum multiple access channel (LC-QMAC), where S servers share an entangled state and separately store classical data streams W1,⋯,WSover a finite field ${\mathbb{F}_d}$. A user aims to compute K linear combinations of these data streams, represented as $Y = {{\mathbf{V}}_1}{W_1} + {{\mathbf{V}}_2}{W_2} + \cdot s + {{\mathbf{V}}_S}{W_S} \in \mathbb{F}_d^{K \times 1}$. To this end, each server encodes its classical information into its local quantum subsystem and transmits it to the user, who retrieves the desired computations via quantum measurements. In this work, we propose an achievable scheme for LC-QMAC based on the stabilizer formalism and the ideas from entanglement-assisted quantum error–correcting codes (EAQECC). Specifically, given any linear computation matrix, we construct a self-orthogonal matrix that can be implemented using the stabilizer formalism. Also, we apply precoding matrices to minimize the number of auxiliary qudits required. Our scheme achieves more computations per qudit, i.e., a higher computation rate, compared to the best-known methods in the literature, and attains the capacity in certain cases.

arXiv:2501.16296•IEEE Information Theory Workshop (ITW)•Sep 29, 2025•2 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
The Σ-QMAC problem is introduced, involvingSservers,Kclassical (Fd) data streams, andTindependent quantum systems. Data stream Wk,k∈ [K] is replicated at a subset of servers W(k) ⊂ [S], and quantum system Qt,t∈ [T] is distributed among a subset of servers ε(t) ⊂ [S] such that Servers∈ ε(t) receives subsystem Qt,sof Qt= (Qt,s)s∈ε(t). Servers manipulate their quantum subsystems according to their data and send the subsystems to a receiver. The total download cost is Σt∈[T]Σs∈ε(t)logd|Qt,s| qudits, where |Q| is the dimension of Q. The states and measurements of (Qt)t∈[T]are required to be separable acrosst∈ [T] throughout, but for eacht∈ [T], thesubsystemsof Qtcan be prepared initially in an arbitrary (independent of data) entangled state, manipulated arbitrarily by the respective servers, and measured jointly by the receiver. From the measurements, the receiver must recover the sum of all data streams. Rate is defined as the number of dits (Fdsymbols) of the desired sum computed per qudit of download. The capacity of Σ-QMAC, i.e., the supremum of achievable rates is characterized for arbitrary data and entanglement distributions W, ε. For example, in the symmetric setting withK= (Sα) data-streams, each replicated among a distinct α-subset of [S], andT= (Sβ) quantum systems, each distributed among a distinct β-subset of [S], the capacity of the Σ-QMAC is 1/βTΣmin(α,β)γ=(α+β−S)+ min(β, 2γ) · (αγ) · (S−αβ−γ). Coding based on the N-sum box abstraction is optimal in every case. Notably, for everyS≠ 3 there exists an instance of the Σ-QMAC whereS-party entanglement is necessary to achieve the fully entangled capacity.
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.
The optimal quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).Kclassical messages comprised of finite-field symbols are distributed acrossSservers, who also share quantum entanglement in advance. Each servers∈ [S] manipulates its quantum subsystemQsaccording to its own available classical messages and sendsQsto the receiver who then computes the sum of the messages based on a joint quantum measurement. The download cost from Servers∈ [S] is the logarithm of the dimension ofQs. The rateRis 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 withK= (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 preciselyC= max { min { 2(α−β)/S,S−2β/S}, α−β/S}. The capacity with arbitrary levels of prior entanglement (Δ0) between theSdata-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.
To compute a summation(Σ)(\Sigma)(Σ)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Σ\SigmaΣ-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\Sigma-2\text{QMAC}Σ−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 theNNN-sum box abstraction is designed to achieve the maximum rate of the second layer.
The quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).KKK- messages are distributed acrossSSSservers so that each server knows a subset of the messages. Each servers∈[S]\mathrm{s}\in[S]s∈[S]sends a quantum subsystemQs\mathcal{Q}_{s}Qs​to the receiver who computes the sum of the messages. The download cost from Servers∈[S]s\in[S]s∈[S]is the logarithm of the dimension ofQs\mathcal{Q}_{s}Qs​. The rateRRR: is defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. In the symmetric setting withK=(αS)K=\left(_{\alpha}^{S}\right)K=(αS​)messages where each message is replicated among a unique subset ofα\alphaαservers, and the answers from anyβ\betaβservers may be erased, the rate achieved isR=max⁡{min⁡{2(α−β)S,1−2βS},α−βS}R=\max \left\{\min \left\{\frac{2(\alpha-\beta)}{S}, 1-\frac{2 \beta}{S}\right\}, \frac{\alpha-\beta}{S}\right\}R=max{min{S2(α−β)​,1−S2β​},Sα−β​}.
We study a linear computation problem over a quantum multiple access channel (LC-QMAC), where S servers share an entangled state and separately store classical data streams W1,⋯,WSover a finite field Fd{\mathbb{F}_d}Fd​. A user aims to compute K linear combinations of these data streams, represented as Y=V1W1+V2W2+⋅s+VSWS∈FdK×1Y = {{\mathbf{V}}_1}{W_1} + {{\mathbf{V}}_2}{W_2} + \cdot s + {{\mathbf{V}}_S}{W_S} \in \mathbb{F}_d^{K \times 1}Y=V1​W1​+V2​W2​+⋅s+VS​WS​∈FdK×1​. To this end, each server encodes its classical information into its local quantum subsystem and transmits it to the user, who retrieves the desired computations via quantum measurements. In this work, we propose an achievable scheme for LC-QMAC based on the stabilizer formalism and the ideas from entanglement-assisted quantum error–correcting codes (EAQECC). Specifically, given any linear computation matrix, we construct a self-orthogonal matrix that can be implemented using the stabilizer formalism. Also, we apply precoding matrices to minimize the number of auxiliary qudits required. Our scheme achieves more computations per qudit, i.e., a higher computation rate, compared to the best-known methods in the literature, and attains the capacity in certain cases.
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.