arXiv:2501.16296 · IEEE Information Theory Workshop (ITW)

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

Lei Hu, Mohamed W. Nomeir, Alptug Aytekin, Yu Shi, Şennur Ulukuş, Saikat Guha

Published Sep 29, 2025• 2 citations

Abstract

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.

DOI: 10.1109/itw62417.2025.11240308

Related papers

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

Ruoyu Meng, Aditya Ramamoorthy

cs.ITCross-listedarXiv:2607.13756Jul 16, 20260 citations

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

Yuhang Yao, Syed A. Jafar

arXiv:2407.01498IEEE Transactions on Quantum EngineeringJan 1, 20252 citations

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

Yuhang Yao, Syed A. Jafar

GlobecomDec 4, 20235 citations

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

Yuhang Yao, Syed A. Jafar

arXiv:2305.03122IEEE Transactions on Information TheoryMay 6, 202411 citations

Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound

Soham Ghosh, Evagoras Stylianou, Holger Boche

arXiv:2410.04130Oct 5, 20240 citations

Entanglement-assisted quantum error-correcting codes over arbitrary finite fields

Carlos Galindo, Fernando Hernando, Ryutaroh Matsumoto +1 more

Abstract We prove that the known formulae for computing the optimal number of maximally entangled pairs required for entanglement-assisted quantum error-correcting codes (EAQECCs) over the binary field hold for codes over arbitrary finite fields as well. We also give a Gilbert–Varshamov bound for EAQECCs and constructions of EAQECCs coming from punctured self-orthogonal linear codes which are valid for any finite field.

arXiv:1812.05312Quantum Information ProcessingMar 4, 2019108 citations

arXiv:2501.16296 · IEEE Information Theory Workshop (ITW)

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

Lei Hu, Mohamed W. Nomeir, Alptug Aytekin, Yu Shi, Şennur Ulukuş, Saikat Guha

Published Sep 29, 2025• 2 citations

arXiv HTML PDF

Abstract

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

DOI: 10.1109/itw62417.2025.11240308

Related papers

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.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.13756Jul 16, 20260 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.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.01498IEEE Transactions on Quantum EngineeringJan 1, 20252 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.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.

GlobecomDec 4, 20235 citations

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

Yuhang Yao, Syed A. Jafar

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

arXiv:2305.03122IEEE Transactions on Information TheoryMay 6, 202411 citations

Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound

Soham Ghosh, Evagoras Stylianou, Holger Boche

We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ \frac{k}{n} = \frac{1}{3} $. For higher rates, our EAQECC also meets the Singleton bound, although with increased entanglement requirements. Additionally, we demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs. The complexity of our encoding protocol for $k$ -qudits with $q$ levels is $\mathcal{O}(k \log_{\frac{q}{q-1}}(k))$ , excluding the complexity of encoding and decoding the classical MDS code. While this complexity remains linear in $k$ for systems of reasonable size, it increases significantly for larger-levelled systems, highlighting the need for further research into complexity reduction.We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ \frac{k}{n} = \frac{1}{3} $. For higher rates, our EAQECC also meets the Singleton bound, although with increased entanglement requirements. Additionally, we demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs. The complexity of our encoding protocol for $k$-qudits with $q$ levels is $\mathcal{O}(k \log_{\frac{q}{q-1}}(k))$, excluding the complexity of encoding and decoding the classical MDS code. While this complexity remains linear in $k$ for systems of reasonable size, it increases significantly for larger-levelled systems, highlighting the need for further research into complexity reduction.

arXiv:2410.04130Oct 5, 20240 citations

Entanglement-assisted quantum error-correcting codes over arbitrary finite fields

Carlos Galindo, Fernando Hernando, Ryutaroh Matsumoto +1 more

arXiv:1812.05312Quantum Information ProcessingMar 4, 2019108 citations

{\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}

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.

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

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.

[n,k,d]_q

code can be transformed into an EAQECC with parameters

[[n,k,d;2k]]_q

using

2k

pre-shared maximally entangled pairs. The complexity of our encoding protocol for

k

-qudits with

q

levels is

\mathcal{O}(k \log_{\frac{q}{q-1}}(k))

, excluding the complexity of encoding and decoding the classical MDS code. While this complexity remains linear in

k

for systems of reasonable size, it increases significantly for larger-levelled systems, highlighting the need for further research into complexity reduction.