Quantum Entanglement Halves the Oblivious Update Bandwidth
This work provides a fundamental quantum advantage for a practical distributed storage problem, reducing communication costs by half for oblivious updates.
The paper proves that quantum entanglement halves the oblivious update bandwidth in MDS-coded distributed storage, achieving a factor of 2 reduction from the classical lower bound of αk log₂ q bits to ⌈α/2⌉·k log₂ q bits, with explicit CSS code constructions achieving the bound.
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$.