Quantum Entanglement Halves the Oblivious Update Bandwidth
Sagar Dubey, [0.5em] Stony Brook University, Stony Brook, NY 11794, USA · 2026
Read Quantum Entanglement Halves the Oblivious Update Bandwidth by Sagar Dubey, [0.5em] Stony Brook University, Stony Brook, NY 11794, USA (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19248.txt.
Introduction
Sagar Dubey shows entanglement nearly halves bandwidth for oblivious updates in MDS-coded storage. In the oblivious update problem, one symbol changes unknown to helpers and node, and the classical bound is alpha k log base 2 of q bits. With entanglement, bandwidth falls to ceiling of alpha over 2 times k log base 2 of q, a factor approaching 2. For alpha 2, a CSS code reaches bandwidth with one qudit per helper. A converse uses the superdense coding bound, and the result holds for all n and k with large prime q.
Catalog record
| CREATOR | Sagar Dubey, [0.5em] Stony Brook University, Stony Brook, NY 11794, USA |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34588 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19248
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Entanglement Halves the Oblivious Update Bandwidth Sagar Dubey, [0.5em] Stony Brook University, Stony Brook, NY 11794, USA Abstract We consider ( n , k ) (n,k) MDS-coded distributed storage over 𝔽 q \mathbb{F}_{q} with per-node storage α \alpha 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 \alpha k\log_{2}q bits. We prove that when the k k contacted helpers share prior quantum entanglement, the update bandwidth is ⌈ α / 2 ⌉ ⋅ k log 2 q \lceil\alpha/2\rceil\cdot k\log_{2}q bits-equivalent—a factor approaching 2 2 reduction. For α = 2 \alpha=2 , a [ [ k , k − 2 ] ] q [[k,k{-}2]]_{q} CSS code achieves bandwidth k log 2 q k\log_{2}q with one qudit per helper. For general α \alpha , a [ [ ⌈ α / 2 ⌉ k , ⌈ α / 2 ⌉ k − α ] ] q [[\lceil\alpha/2\rceil k,\;\lceil\alpha/2\rceil k-\alpha]]_{q} CSS code achieves the bound with ⌈ α / 2 ⌉ \lceil\alpha/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 D^{2} distinguishable signals for dimension D D . The result holds for all ( n , k ) (n,k) pairs with sufficiently large prime q q . 1 Introduction Distributed storage systems encode files across n nodes so that any k nodes suffice for reconstruction. When the stored content changes, stale nodes must update their coded shares. The oblivious update model of Nakkiran, Shah, and Rashmi [ 13 ] considers the setting where a single message symbol changes, and neither the helpers nor the stale node know which symbol was modified. They showed that for (n,k) MDS codes over \mathbb{F}_{q} , the stale node must download at least 2k\log_{2}q bits from k updated helpers—a per-helper cost of 2\log_{2}q . Recent work by Hu, Nomeir, Aytekin, and Ulukus [ 9 , 8 ] demonstrated that shared quantum entanglement among helper nodes can halve the repair bandwidth in distributed storage at the minimum-storage regenerating (MSR) point. Their mechanism uses CSS (Calderbank-Shor-Steane) stabilizer codes: helpers encode classical data into qudits via Pauli operators, and the receiver extracts linear combinations through stabilizer measurements. Each qudit carries two classical symbols (one via the X -syndrome, one via the Z -syndrome), achieving a factor-of-two improvement over classical repair. Our contribution. We extend the entanglement advantage from repair to the oblivious update setting, resolving the problem completely for all storage regimes: Theorem 1 (Main result) . Let \mathcal{C} be an (n,k) MDS code over \mathbb{F}_{q} with per-node storage \alpha\geq 2 and prime q>\lceil\alpha/2\rceil\cdot k . The optimal entanglement-assisted oblivious update bandwidth with d_{u}=k helpers, restricted to protocols where each helper transmits integer-dimension qudits (i.e., D_{i}=q^{\beta_{q,i}} ), is: \gamma_{u}^{q}=\lceil\alpha/2\rceil\cdot k\log_{2}q\quad\text{bits-equivalent}, achieved by each helper transmitting \lceil\alpha/2\rceil qudits of dimension q . For \alpha=2 , this is exactly half the classical lower bound [ 13 ] . The result is tight: we prove a universal converse (Theorem 5 ) via the superdense coding bound showing \log_{2}D_{i}\geq(\alpha/2)\log_{2}q per helper, and a matching achievability (Theorem 6 ) using higher-dimensional CSS codes. We present the \alpha=2 case in detail (Sections 4 – 6 ), where one qudit per helper suffices, and then extend to general \alpha in Section 7 . Key insight. The factor-of-two improvement arises because, once all k helpers transmit their qudits, the stale node holds all parts of the originally entangled state. From any single helper’s viewpoint, the stale node possesses both the transmitted qudit and the entangled partners—exactly the superdense coding configuration. Each dimension- q qudit thus conveys 2\log_{2}q bits of classical information, matching the 2\log_{2}q -bit per-helper classical requirement with half the channel resources. Related work. The information-theoretic foundations of regenerating codes were laid by Dimakis et al. [ 4 ] , with exact-repair constructions by Rashmi, Shah, and Kumar [ 15 ] . The update problem in coded storage was initiated by Anthapadmanabhan, Soljanin, and Vishwanath [ 1 ] , with subsequent work by Rawat et al. [ 16 ] , Han et al. [ 6 ] , and Li et al. [ 10 ] on update-efficient regenerating codes and update bandwidth, while Mazumdar, Chandar, and Wornell [ 12 ] established update-efficiency limits for capacity-approaching codes. The NSR oblivious update model [ 13 ] is the direct predecessor of our work. Vithana and Ulukus [ 19 , 20 ] studied the private read-update-write (PRUW) problem, which adds privacy constraints to the update setting; our obliviousness requirement is distinct (helpers lack knowledge of the change location, rather than hiding it from a curious server). On the quantum side, superdense coding [ 3 , 21 ] and entanglement-assisted classical capacity [ 2 ] underpin the factor-of-two mechanism. Hsieh, Devetak, and Winter [ 7 ] characterized entanglement-assisted multiple-access channels, which is the relevant capacity framework when multiple helpers jointly transmit. Sun and Jafar [ 18 ] studied the capacity of distributed quantum storage, and Senthoor [ 17 ] analyzed entanglement costs of erasure correction in quantum MDS codes. Paper organization. Section 2 formulates the problem. Section 3 reviews the classical baseline. Section 4 presents the (3,2) example. Section 5 gives the general construction. Section 6 proves the converse. Section 7 discusses the mechanism, scope, and extensions. Section 8 concludes. 2 Problem Formulation 2.1 Storage Code Consider an (n,k) MDS code over a prime field \mathbb{F}_{q} with per-node storage \alpha\geq 2 symbols (file size B=\alpha k ). A file \mathbf{m}=(m_{1},\ldots,m_{B})\in\mathbb{F}_{q}^{B} is stored across n nodes, where node i stores \Gamma_{i}\mathbf{m}\in\mathbb{F}_{q}^{\alpha} . The generator matrices \Gamma_{i}\in\mathbb{F}_{q}^{\alpha\times B} satisfy the MDS property: for any k nodes \{i_{1},\ldots,i_{k}\} , the stacked matrix [\Gamma_{i_{1}};\ldots;\Gamma_{i_{k}}]\in\mathbb{F}_{q}^{B\times B} is invertible over \mathbb{F}_{q} . (An \alpha -interleaved Reed-Solomon construction satisfies this for any q\geq n .) The running example in Sections 4 – 6 uses \alpha=2 ; the general case is treated in Section 7 . 2.2 Oblivious Update Problem A single symbol of \mathbf{m} is modified: \mathbf{m}^{\prime}=\mathbf{m}+\delta\mathbf{e}_{j} for some j\in[B] and \delta\in\mathbb{F}_{q}\setminus\{0\} (or \mathbf{m}^{\prime}=\mathbf{m} for no change). A stale node s stores the outdated value \Gamma_{s}\mathbf{m} and must compute the updated value \Gamma_{s}\mathbf{m}^{\prime} . Definition 1 (Oblivious update protocol) . The stale node contacts d_{u}=k updated helpers h_{1},\ldots,h_{k} . Each helper h_{i} knows only its own updated storage \Gamma_{h_{i}}\mathbf{m}^{\prime} (not j , \delta , or the old \mathbf{m} ). The helpers transmit information to the stale node, which uses its side information \Gamma_{s}\mathbf{m} to compute \Gamma_{s}\mathbf{m}^{\prime} . The protocol is oblivious : each helper’s encoding depends only on its current data, independent of which symbol changed. 2.3 Entanglement-Assisted Model Following Hu et al. [ 9 ] , we consider the helper-side shared entanglement model: • Prior to the update, the k helpers share a pre-distributed entangled state |\Psi\rangle\in\mathcal{H}_{1}\otimes\cdots\otimes\mathcal{H}_{k} (each \mathcal{H}_{i} of dimension q^{\beta_{q}} ). • Each helper applies a local encoding operation (depending on its classical data \Gamma_{h_{i}}\mathbf{m}^{\prime} ) to its subsystem. • Each helper transmits its (encoded) quantum subsystem to the stale node. • The stale node performs a joint measurement on all received qudits, using