pith. sign in

arxiv: 2605.19248 · v1 · pith:Q3USAXTOnew · submitted 2026-05-19 · 🪐 quant-ph · cs.IT· math.IT

Quantum Entanglement Halves the Oblivious Update Bandwidth

Sagar Dubey This is my paper

Pith reviewed 2026-05-20 06:34 UTC · model grok-4.3

classification 🪐 quant-ph cs.ITmath.IT
keywords quantum entanglementdistributed storageMDS codesoblivious updatesuperdense codingCSS codesbandwidth reductionquantum communication
0
0 comments X

The pith

Quantum entanglement among storage helpers reduces oblivious update bandwidth by nearly half.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In distributed storage systems that use MDS codes over a finite field, changing one data symbol requires the system to communicate without revealing which symbol changed. Classically this needs at least α k log₂ q bits of communication. The paper shows that if the k helper nodes share prior quantum entanglement, the required communication drops to ⌈α/2⌉ k log₂ q bits-equivalent. The savings arise because each helper sends only ⌈α/2⌉ qudits that exploit superdense coding to carry twice the classical information. A reader would care because this quantum-assisted method could cut communication costs in large-scale coded storage systems that must stay reliable while handling frequent small updates.

Core claim

For an (n,k) MDS-coded distributed storage system over F_q with per-node storage α symbols, the oblivious update problem has classical communication cost α k log₂ q bits. When the k contacted helpers share prior quantum entanglement, a [[⌈α/2⌉ k, ⌈α/2⌉ k - α]]_q CSS code lets each helper transmit ⌈α/2⌉ qudits and achieves total bandwidth ⌈α/2⌉ · k log₂ q bits-equivalent. The matching converse follows from the superdense coding bound: the stale node receives all transmitted qudits and therefore holds their entangled partners, so each helper's channel supports at most D² distinguishable signals. The result holds for every (n,k) pair whenever q is a sufficiently large prime.

What carries the argument

CSS quantum codes together with the superdense coding bound, which lets each entangled qudit pair convey two classical symbols and thereby halves the number of qudits that must be sent for the oblivious update.

If this is right

  • For α = 2 the construction uses a [[k, k-2]]_q CSS code and reduces bandwidth to exactly k log₂ q with one qudit per helper.
  • For general α the same approach scales by sending ⌈α/2⌉ qudits per helper using the larger CSS code of length ⌈α/2⌉ k.
  • The bandwidth reduction applies to every (n,k) MDS storage system once q is large enough for the codes.
  • No further asymptotic improvement beyond the factor-of-two reduction is possible once the superdense coding limit is applied.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same entanglement-sharing idea could be tested in other maintenance tasks such as node repair or data migration in coded systems.
  • Partial or noisy entanglement would likely yield intermediate savings between the classical and ideal quantum bounds.
  • The protocol suggests a route to hybrid quantum-classical maintenance layers in future distributed storage infrastructure.

Load-bearing premise

The k contacted helpers must already share quantum entanglement and the field size q must be large enough for the required CSS codes to exist.

What would settle it

An explicit small-parameter example with prime q where the stale node, holding the entangled partner qudits, can distinguish more than D² possible update messages from each helper's D-dimensional transmission would show that the superdense coding bound does not limit the protocol as claimed.

read the original abstract

We consider $(n,k)$ MDS-coded distributed storage over $\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 $\alpha k \log_2 q$ bits. We prove that when the $k$ contacted helpers share prior quantum entanglement, the update bandwidth is $\lceil \alpha/2 \rceil \cdot k \log_2 q$ bits-equivalent, a factor approaching 2 reduction. For $\alpha = 2$, a $[[k, k-2]]_q$ CSS code achieves bandwidth $k \log_2 q$ with one qudit per helper. For general $\alpha$, a $[[\lceil \alpha/2 \rceil k, \lceil \alpha/2 \rceil k - \alpha]]_q$ CSS code achieves the bound with $\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$ distinguishable signals for dimension $D$. The result holds for all $(n,k)$ pairs with sufficiently large prime $q$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper considers (n,k) MDS-coded distributed storage over F_q with per-node storage α symbols and studies the oblivious update problem (single symbol change, unknown to helpers and stale node). Classically the bandwidth lower bound is α k log₂ q bits. The central claim is that prior quantum entanglement among the k contacted helpers reduces the bandwidth to ⌈α/2⌉ · k log₂ q bits-equivalent. Achievability is shown via CSS codes: a [[k,k-2]]_q code for α=2 (one qudit per helper) and a [[⌈α/2⌉k, ⌈α/2⌉k-α]]_q code for general α (⌈α/2⌉ qudits per helper). The matching converse invokes the superdense-coding bound, asserting that the stale node holds the transmitted qudits and therefore the entangled partners, limiting each helper's channel to at most D² distinguishable signals.

Significance. If the entanglement setup and bound application are made fully consistent, the result supplies a clean factor-of-two improvement in update communication for distributed storage by importing standard quantum coding tools (CSS codes and superdense coding). The construction is parameter-free once q is large enough for the required CSS codes to exist, and the converse is derived from an information-theoretic capacity bound rather than an ad-hoc argument; both are strengths that would be noted in a positive assessment.

major comments (1)
  1. [Abstract / Converse argument] Abstract and converse paragraph: the phrasing 'the k contacted helpers share prior quantum entanglement' is inconsistent with the converse claim that 'the stale node holds all transmitted qudits and hence the entangled partners.' If entanglement resides only among the helpers, the stale node lacks the partner qudits and the superdense-coding capacity bound (each channel supports at most D² signals) does not apply directly. This mismatch is load-bearing for the claimed tightness of the lower bound and must be resolved by an explicit statement of the entanglement graph (e.g., whether the stale node is pre-entangled with the helpers or receives the partners via the update transmissions).
minor comments (2)
  1. [Abstract] The phrase 'bits-equivalent' is used without a precise definition relating qudit transmissions to classical bits; a short clarifying sentence or footnote would improve readability.
  2. [Achievability construction] The existence statement 'for sufficiently large prime q' is repeated but never quantified; a brief remark on the minimal q required for the CSS code parameters would be helpful.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying an inconsistency in the description of the entanglement setup. We address this point directly below and will revise the manuscript to improve clarity while preserving the technical content.

read point-by-point responses

  1. Referee: Abstract / Converse argument] Abstract and converse paragraph: the phrasing 'the k contacted helpers share prior quantum entanglement' is inconsistent with the converse claim that 'the stale node holds all transmitted qudits and hence the entangled partners.' If entanglement resides only among the helpers, the stale node lacks the partner qudits and the superdense-coding capacity bound (each channel supports at most D² signals) does not apply directly. This mismatch is load-bearing for the claimed tightness of the lower bound and must be resolved by an explicit statement of the entanglement graph (e.g., whether the stale node is pre-entangled with the helpers or receives the partners via the update transmissions).

    Authors: We appreciate the referee's observation on the phrasing inconsistency. The intended model is that each helper shares prior entanglement with the stale node (rather than the helpers being entangled exclusively among themselves). Under this configuration the stale node holds the partner qudits from the outset and receives the transmitted qudits, so the superdense-coding bound applies and each helper's channel supports at most D² distinguishable signals. The current wording in the abstract and converse paragraph is imprecise on this point. We will revise both locations to state explicitly that the prior entanglement is between the helpers and the stale node, thereby removing the ambiguity and confirming the applicability of the bound. This clarification does not change the achievability constructions or the information-theoretic argument. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses independent quantum bounds and code constructions

full rationale

The paper derives the halved bandwidth via an explicit CSS quantum code construction for the achievable scheme and invokes the standard superdense coding capacity bound for the matching converse. Both steps rest on externally established results from quantum information theory and algebraic coding theory rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equation or claim reduces by construction to the target bandwidth figure; the argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claim rests on standard domain assumptions from coding theory and quantum information with no free parameters fitted to data and no new invented entities.

axioms (3)
  • domain assumption MDS codes exist over F_q for sufficiently large prime q
    The storage scheme and code constructions presuppose the existence of MDS codes in the finite field.
  • domain assumption CSS quantum codes with the stated parameters can be constructed
    Achievability relies on the existence and properties of the [[k, k-2]]_q and [[⌈α/2⌉k, ⌈α/2⌉k - α]]_q CSS codes.
  • standard math Superdense coding bound limits distinguishable signals to D² per qudit
    The converse invokes the superdense coding capacity bound from quantum information theory.

pith-pipeline@v0.9.0 · 5770 in / 1471 out tokens · 78591 ms · 2026-05-20T06:34:16.985979+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 2 internal anchors

  1. [1]

    Shah, and K

    Preetum Nakkiran, Nihar B. Shah, and K. V. Rashmi. Fundamental limits on communication for oblivious updates in storage networks. InIEEE Global Communications Conference (GLOBECOM), 2014

    work page 2014

  2. [2]

    Simultaneously Minimizing Storage and Bandwidth Under Exact Repair With Quantum Entanglement

    Lei Hu, Mohamed Nomeir, Alptug Aytekin, and Sennur Ulukus. Simultaneously minimizing storage and bandwidth under exact repair with quantum entanglement.arXiv preprint arXiv:2605.12455, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  3. [3]

    Breaking the storage-bandwidth tradeoff in distributed storage with quantum entanglement.arXiv preprint arXiv:2601.10676, 2026

    Lei Hu, Mohamed Nomeir, Alptug Aytekin, and Sennur Ulukus. Breaking the storage-bandwidth tradeoff in distributed storage with quantum entanglement.arXiv preprint arXiv:2601.10676, 2026

    work page arXiv 2026

  4. [4]

    Dimakis, P

    Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan Ram- chandran. Network coding for distributed storage systems.IEEE Transactions on Information Theory, 56(9):4539–4551, 2010

    work page 2010

  5. [5]

    K. V. Rashmi, Nihar B. Shah, and P. Vijay Kumar. Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction.IEEE Transactions on Information Theory, 57(8):5227–5239, 2011

    work page 2011

  6. [6]

    Prasanth Anthapadmanabhan, Emina Soljanin, and Sriram Vishwanath

    N. Prasanth Anthapadmanabhan, Emina Soljanin, and Sriram Vishwanath. Update-efficient codes for erasure correction. In48th Annual Allerton Conference on Communication, Control, and Computing, pages 376–382, 2010. 9

    work page 2010

  7. [7]

    Update efficient codes for distributed storage

    Ankit Singh Rawat, Sriram Vishwanath, Abhishek Bhowmick, and Emina Soljanin. Update efficient codes for distributed storage. InIEEE International Symposium on Information Theory (ISIT), pages 1457–1461, 2011

    work page 2011

  8. [8]

    Update-Efficient Regenerating Codes with Minimum Per-Node Storage

    Yunghsiang S. Han, Hong-Ta Pai, Rong Zheng, and Pramod K. Varshney. Update-efficient regenerating codes with minimum per-node storage.arXiv preprint arXiv:1301.2497, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  9. [9]

    Han, and Hanxu Hou

    Zhengrui Li, Sian-Jheng Lin, Po-Ning Chen, Yunghsiang S. Han, and Hanxu Hou. Update bandwidth for distributed storage.arXiv preprint arXiv:2005.11894, 2020

    work page arXiv 2005

  10. [10]

    Arya Mazumdar, Venkat Chandar, and Gregory W. Wornell. Update-efficiency and local repairability limits for capacity approaching codes.IEEE Journal on Selected Areas in Communications, 32(4):976–988, 2014

    work page 2014

  11. [11]

    Private read update write (PRUW) with storage constrained databases.arXiv preprint arXiv:2202.03400, 2022

    Sajani Vithana and Sennur Ulukus. Private read update write (PRUW) with storage constrained databases.arXiv preprint arXiv:2202.03400, 2022

    work page arXiv 2022

  12. [12]

    Sajani Vithana and Sennur Ulukus. Private read update write (PRUW) in federated submodel learning (FSL): Communication efficient schemes with and without sparsification.IEEE Journal on Selected Areas in Communications, 41(7):2226–2242, 2023

    work page 2023

  13. [13]

    Bennett and Stephen J

    Charles H. Bennett and Stephen J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states.Physical Review Letters, 69(20):2881–2884, 1992

    work page 1992

  14. [14]

    Reinhard F. Werner. All teleportation and dense coding schemes.Journal of Physics A: Mathematical and General, 34(35):7081–7094, 2001

    work page 2001

  15. [15]

    Bennett, Peter W

    Charles H. Bennett, Peter W. Shor, John A. Smolin, and Ashish V. Thapliyal. Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem.IEEE Transactions on Information Theory, 48(10):2637–2655, 2002

    work page 2002

  16. [16]

    Entanglement-assisted capacity of quantum multiple access channels.IEEE Transactions on Information Theory, 54(7):3078–3090, 2008

    Min-Hsiu Hsieh, Igor Devetak, and Andreas Winter. Entanglement-assisted capacity of quantum multiple access channels.IEEE Transactions on Information Theory, 54(7):3078–3090, 2008

    work page 2008

  17. [17]

    Hua Sun and Syed A. Jafar. On the capacity of distributed quantum storage.arXiv preprint arXiv:2510.10568, 2025

    work page arXiv 2025

  18. [18]

    Entanglement cost of erasure correction in quantum MDS codes.arXiv preprint arXiv:2505.20284, 2025

    Kaushik Senthoor. Entanglement cost of erasure correction in quantum MDS codes.arXiv preprint arXiv:2505.20284, 2025

    work page arXiv 2025

  19. [19]

    PhD thesis, California Institute of Technology, 1997

    Daniel Gottesman.Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997

    work page 1997

  20. [20]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition, 2010

    work page 2010

  21. [21]

    Jessie MacWilliams and Neil J

    F. Jessie MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977. 10

    work page 1977