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.20073 · IEEE Communications Letters

On the Capacity of Secure K-User Product Computation Over a Quantum MAC

Yuxiang Lu, Yuhang Yao, Syed A. Jafar

Published Sep 1, 2023• 7 citations
arXivHTMLPDF

Abstract

Inspired by recent work by Christensen and Popovski on secure 2-user product computation for finite-fields of prime-order over a quantum multiple access channel, the generalization to$K$users and arbitrary finite fields is explored. Asymptotically optimal (capacity-achieving for large alphabet) schemes are proposed. Additionally, the capacity of modulo-$d$($d\geq 2$) secure$K$-sum computation is shown to be$2/K$computations/qudit, generalizing a result of Nishimura and Kawachi beyond binary, and improving upon it for odd$K$.

DOI
10.1109/lcomm.2023.3311368

Related papers

Secure Modulo Sum via Multiple Access Channel

Masahito Hayashi

We discuss secure computation of modular sum when multiple access channel from distinct players$A_{1}, \ldots, A_{c}$to a third party (Receiver) is given. Then, we define the secure modulo sum capacity as the supremum of the transmission rate of modulo sum without information leakage of other information. We derive its useful lower bound, which is numerically calculated under a realistic model that can be realizable as a Gaussian multiple access channel (MAC).

arXiv:1812.10862•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•6 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

On secure computation over the binary modulo-2 adder multiple-access wiretap channel

Mario Goldenbaum, Holger Boche, H. Vincent Poor

In this paper, the problem of securely computing a function over the binary modulo-2 adder multiple-access wiretap channel is considered. The problem involves a legitimate receiver that wishes to reliably and efficiently compute a function of distributed binary sources while an eavesdropper has to be kept ignorant of them. In order to characterize the corresponding fundamental limit, the notion of secrecy computation-capacity is introduced. Although determining the secrecy computation-capacity is challenging for arbitrary functions, it surprisingly turns out that if the function perfectly matches the algebraic structure of the channel and the joint source distribution fulfills certain conditions, the secrecy computation-capacity equals the computation capacity, which is the supremum of all achievable computation rates without secrecy constraints. Unlike the case of securely transmitting messages, no additional randomness is needed at the encoders nor does the legitimate receiver need any advantage over the eavesdropper. The results therefore show that the problem of securely computing a function over a multiple-access wiretap channel may significantly differ from the one of securely communicating messages.

arXiv:1603.07227•IEEE Information Theory Workshop (ITW)•Sep 1, 2016•11 citations

Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets

Debbie Leung, Ashwin Nayak, Ala Shayeghi +3 more

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.

arXiv:2001.02818•IEEE Transactions on Information Theory•Jun 8, 2021•2 citations

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
Inspired by recent work by Christensen and Popovski on secure 2-user product computation for finite-fields of prime-order over a quantum multiple access channel, the generalization toKKKusers and arbitrary finite fields is explored. Asymptotically optimal (capacity-achieving for large alphabet) schemes are proposed. Additionally, the capacity of modulo-ddd(d≥2d\geq 2d≥2) secureKKK-sum computation is shown to be2/K2/K2/Kcomputations/qudit, generalizing a result of Nishimura and Kawachi beyond binary, and improving upon it for oddKKK.
We discuss secure computation of modular sum when multiple access channel from distinct playersA1,…,AcA_{1}, \ldots, A_{c}A1​,…,Ac​to a third party (Receiver) is given. Then, we define the secure modulo sum capacity as the supremum of the transmission rate of modulo sum without information leakage of other information. We derive its useful lower bound, which is numerically calculated under a realistic model that can be realizable as a Gaussian multiple access channel (MAC).
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.
In this paper, the problem of securely computing a function over the binary modulo-2 adder multiple-access wiretap channel is considered. The problem involves a legitimate receiver that wishes to reliably and efficiently compute a function of distributed binary sources while an eavesdropper has to be kept ignorant of them. In order to characterize the corresponding fundamental limit, the notion of secrecy computation-capacity is introduced. Although determining the secrecy computation-capacity is challenging for arbitrary functions, it surprisingly turns out that if the function perfectly matches the algebraic structure of the channel and the joint source distribution fulfills certain conditions, the secrecy computation-capacity equals the computation capacity, which is the supremum of all achievable computation rates without secrecy constraints. Unlike the case of securely transmitting messages, no additional randomness is needed at the encoders nor does the legitimate receiver need any advantage over the eavesdropper. The results therefore show that the problem of securely computing a function over a multiple-access wiretap channel may significantly differ from the one of securely communicating messages.
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.
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.