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:2605.19248

Quantum Entanglement Halves the Oblivious Update Bandwidth

Sagar Dubey

quant-phcs.ITSubmitted May 19, 2026• Announced May 20, 2026• 0 citations
v1 · May 19, 2026v2 · Jun 22, 2026
arXivHTMLPDF

Abstract

We consider $(n,k)$ MDS-coded distributed storage over $\mathbb{F}_q$ with per-node storage $α$ symbols. For the oblivious update problem, where a single message symbol changes and neither helpers nor the stale node know which, the classical lower bound is $αk \log_2 q$ bits. We prove that when the $k$ contacted helpers share prior quantum entanglement, the update bandwidth is $\lceil α/2 \rceil \cdot k \log_2 q$ bits-equivalent, a factor approaching 2 reduction. For $α= 2$, a $[[k, k-2]]_q$ CSS code achieves bandwidth $k \log_2 q$ with one qudit per helper. For general $α$, a $[[\lceil α/2 \rceil k, \lceil α/2 \rceil k - α]]_q$ CSS code achieves the bound with $\lceil α/2 \rceil$ qudits per helper. The matching converse uses the superdense coding bound: the stale node holds all transmitted qudits and hence the entangled partners, so each helper's channel supports at most $D^2$ distinguishable signals for dimension $D$. The result holds for all $(n,k)$ pairs with sufficiently large prime $q$.

Related papers

Breaking the Storage-Bandwidth Tradeoff in Distributed Storage with Quantum Entanglement

Lei Hu, Mohamed Nomeir, Alptug Aytekin +1 more

This work investigates the use of quantum resources in distributed storage systems. Consider an $(n,k,d)$ distributed storage system in which a file is stored across $n$ nodes such that any $k$ nodes suffice to reconstruct the file. When a node fails, any $d$ helper nodes transmit information to a newcomer to rebuild the system. In contrast to the classical repair, where helper nodes transmit classical bits, we allow them to send classical information over quantum channels to the newcomer. The newcomer then generates its storage by performing appropriate measurements on the received quantum states. In this setting, we fully characterize the fundamental tradeoff between storage and repair bandwidth (total communication cost). Compared to classical systems, the optimal storage--bandwidth tradeoff can be significantly improved with the enhancement of quantum entanglement shared only among the surviving nodes, particularly at the minimum-storage regenerating point. Remarkably, we show that when $d \geq 2k-2$, there exists an operating point at which \textit{both storage and repair bandwidth are simultaneously minimized}. This phenomenon breaks the tradeoff in the classical setting and reveals a fundamentally new regime enabled by quantum communication.

cs.ITCross-listedarXiv:2601.10676•IEEE International Symposium on Information Theory (ISIT)•Jan 16, 2026•0 citations

Simultaneously Minimizing Storage and Bandwidth Under Exact Repair With Quantum Entanglement

Lei Hu, Mohamed Nomeir, Alptug Aytekin +1 more

We study exact-regenerating codes for entanglement-assisted distributed storage systems. Consider an $(n,k,d,α,β_{\mathsf{q}},B)$ distributed system that stores a file of $B$ classical symbols across $n$ nodes with each node storing $α$ symbols. A data collector can recover the file by accessing any $k$ nodes. When a node fails, any $d$ surviving nodes share an entangled state, and each of them transmits a quantum system of $β_{\mathsf{q}}$ qudits to a newcomer. The newcomer then performs a measurement on the received quantum systems to generate its storage. Recent work [1] showed that, under functional repair where the regenerated content may differ from that of the failed node, there exists a unique optimal regenerating point that \emph{simultaneously minimizes both storage $α$ and repair bandwidth $d β_{\mathsf{q}}$} when $d \geq 2k-2$. In this paper, we show that, under \emph{exact repair}, where the newcomer reproduces exactly the same content as the failed node, this optimal point remains achievable. Our construction builds on the classical product-matrix framework and the Calderbank-Shor-Steane (CSS)-based stabilizer formalism.

cs.ITCross-listedarXiv:2605.12455•May 13, 2026•0 citations

Entanglement Cost of Erasure Correction in Quantum MDS Codes

Kaushik Senthoor

In distributed quantum storage, physical qubits of a code will be stored across the network. When qubits in one of the nodes are lost i.e. when the node is erased, the remaining nodes need to communicate with a new node to replace the lost qubits. Here, we look at the problem of how much entanglement cost is needed to perform such a distributed quantum erasure correction. We focus on distributed quantum storage based on quantum maximum distance separable (MDS) codes. We derive lower bounds on the entanglement cost when the quantum network used for the erasure correction has a star topology. We show that the simple method of downloading the non-erased qudits and performing operations at a single node is optimal when the minimal number of non-erased nodes are accessed. It remains to be seen what the entanglement cost will be when a non-minimal number of non-erased nodes are accessed. The techniques used in this work can be developed further to study the entanglement cost of quantum erasure correction in more general code families and network topologies.

arXiv:2505.20284•May 26, 2025•0 citations

Entanglement-Assisted Quantum Locally Recoverable Codes: Characterizations, Bounds, and Constructions

Yang Li, San Ling, Zhenliang Lu +2 more

Quantum locally recoverable codes (qLRCs) allow a single qudit erasure to be corrected by accessing only a small number of other qudits. Standard CSS and Hermitian constructions, however, impose dual-containing or self-orthogonal constraints on the underlying classical codes, thereby restricting the well-structured classical LRCs (cLRCs) that can be used to construct qLRCs. To relax these constraints, we introduce entanglement-assisted quantum locally recoverable codes (EAQLRCs) by assuming that halves of the pre-shared maximally entangled pairs are noiseless. We characterize sufficient support conditions on extended stabilizers under which entanglement-assisted stabilizer codes have locality $r$ and derive a CSS-like construction from two classical codes without imposing the ordinary dual-containing condition. We further establish an upper bound on locality and a Singleton-like bound for arbitrary CSS-like EAQLRCs, and characterize the pure codes attaining equality in the latter bound. These results yield a general framework for constructing optimal pure EAQLRCs from pairs of cLRCs. Applying this framework to $\ell$-intersection pairs of MDS codes and block parity-check matrices, we obtain two families of optimal pure CSS-like EAQLRCs with flexible parameters and nontrivial localities. To the best of our knowledge, these represent the first explicit families of EAQLRCs.

arXiv:2607.27091•Jul 29, 2026•0 citations

On communication over an entanglement-assisted quantum channel

A. Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•10 citations

On communication over an entanglement-assisted quantum channel. (arXiv:quant-ph/0206122v1 CROSS LISTED)

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

•Mar 21, 2018•0 citations
We consider (n,k)(n,k)(n,k) MDS-coded distributed storage over Fq\mathbb{F}_qFq​ with per-node storage ααα symbols. For the oblivious update problem, where a single message symbol changes and neither helpers nor the stale node know which, the classical lower bound is αklog⁡2qαk \log_2 qαklog2​q bits. We prove that when the kkk contacted helpers share prior quantum entanglement, the update bandwidth is ⌈α/2⌉⋅klog⁡2q\lceil α/2 \rceil \cdot k \log_2 q⌈α/2⌉⋅klog2​q bits-equivalent, a factor approaching 2 reduction. For α=2α= 2α=2, a [[k,k−2]]q[[k, k-2]]_q[[k,k−2]]q​ CSS code achieves bandwidth klog⁡2qk \log_2 qklog2​q with one qudit per helper. For general ααα, a [[⌈α/2⌉k,⌈α/2⌉k−α]]q[[\lceil α/2 \rceil k, \lceil α/2 \rceil k - α]]_q[[⌈α/2⌉k,⌈α/2⌉k−α]]q​ CSS code achieves the bound with ⌈α/2⌉\lceil α/2 \rceil⌈α/2⌉ qudits per helper. The matching converse uses the superdense coding bound: the stale node holds all transmitted qudits and hence the entangled partners, so each helper's channel supports at most D2D^2D2 distinguishable signals for dimension DDD. The result holds for all (n,k)(n,k)(n,k) pairs with sufficiently large prime qqq.
This work investigates the use of quantum resources in distributed storage systems. Consider an (n,k,d)(n,k,d)(n,k,d) distributed storage system in which a file is stored across nnn nodes such that any kkk nodes suffice to reconstruct the file. When a node fails, any ddd helper nodes transmit information to a newcomer to rebuild the system. In contrast to the classical repair, where helper nodes transmit classical bits, we allow them to send classical information over quantum channels to the newcomer. The newcomer then generates its storage by performing appropriate measurements on the received quantum states. In this setting, we fully characterize the fundamental tradeoff between storage and repair bandwidth (total communication cost). Compared to classical systems, the optimal storage--bandwidth tradeoff can be significantly improved with the enhancement of quantum entanglement shared only among the surviving nodes, particularly at the minimum-storage regenerating point. Remarkably, we show that when d≥2k−2d \geq 2k-2d≥2k−2, there exists an operating point at which \textit{both storage and repair bandwidth are simultaneously minimized}. This phenomenon breaks the tradeoff in the classical setting and reveals a fundamentally new regime enabled by quantum communication.
We study exact-regenerating codes for entanglement-assisted distributed storage systems. Consider an (n,k,d,α,βq,B)(n,k,d,α,β_{\mathsf{q}},B)(n,k,d,α,βq​,B) distributed system that stores a file of BBB classical symbols across nnn nodes with each node storing ααα symbols. A data collector can recover the file by accessing any kkk nodes. When a node fails, any ddd surviving nodes share an entangled state, and each of them transmits a quantum system of βqβ_{\mathsf{q}}βq​ qudits to a newcomer. The newcomer then performs a measurement on the received quantum systems to generate its storage. Recent work [1] showed that, under functional repair where the regenerated content may differ from that of the failed node, there exists a unique optimal regenerating point that \emph{simultaneously minimizes both storage ααα and repair bandwidth dβqd β_{\mathsf{q}}dβq​} when d≥2k−2d \geq 2k-2d≥2k−2. In this paper, we show that, under \emph{exact repair}, where the newcomer reproduces exactly the same content as the failed node, this optimal point remains achievable. Our construction builds on the classical product-matrix framework and the Calderbank-Shor-Steane (CSS)-based stabilizer formalism.
In distributed quantum storage, physical qubits of a code will be stored across the network. When qubits in one of the nodes are lost i.e. when the node is erased, the remaining nodes need to communicate with a new node to replace the lost qubits. Here, we look at the problem of how much entanglement cost is needed to perform such a distributed quantum erasure correction. We focus on distributed quantum storage based on quantum maximum distance separable (MDS) codes. We derive lower bounds on the entanglement cost when the quantum network used for the erasure correction has a star topology. We show that the simple method of downloading the non-erased qudits and performing operations at a single node is optimal when the minimal number of non-erased nodes are accessed. It remains to be seen what the entanglement cost will be when a non-minimal number of non-erased nodes are accessed. The techniques used in this work can be developed further to study the entanglement cost of quantum erasure correction in more general code families and network topologies.
Quantum locally recoverable codes (qLRCs) allow a single qudit erasure to be corrected by accessing only a small number of other qudits. Standard CSS and Hermitian constructions, however, impose dual-containing or self-orthogonal constraints on the underlying classical codes, thereby restricting the well-structured classical LRCs (cLRCs) that can be used to construct qLRCs. To relax these constraints, we introduce entanglement-assisted quantum locally recoverable codes (EAQLRCs) by assuming that halves of the pre-shared maximally entangled pairs are noiseless. We characterize sufficient support conditions on extended stabilizers under which entanglement-assisted stabilizer codes have locality rrr and derive a CSS-like construction from two classical codes without imposing the ordinary dual-containing condition. We further establish an upper bound on locality and a Singleton-like bound for arbitrary CSS-like EAQLRCs, and characterize the pure codes attaining equality in the latter bound. These results yield a general framework for constructing optimal pure EAQLRCs from pairs of cLRCs. Applying this framework to ℓ\ellℓ-intersection pairs of MDS codes and block parity-check matrices, we obtain two families of optimal pure CSS-like EAQLRCs with flexible parameters and nontrivial localities. To the best of our knowledge, these represent the first explicit families of EAQLRCs.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.