Quantum Entanglement Halves the Oblivious Update Bandwidth

• URL: http://arxiv.org/abs/2605.19248v1
• Date: Tue, 19 May 2026 01:42:48 GMT
• Title: Quantum Entanglement Halves the Oblivious Update Bandwidth
• Abstract summary: We consider $(n,k)$ MDS-coded distributed storage over $mathbbF_q$ with per-node storage $$ symbols.<n>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 q$ bits.<n>We prove that when the $k$ helpers share prior quantum entanglement, the update bandwidth is $lceil /2 rceil cdot k log q$ bits-equivalent.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  We introduce ordered-angle coding for binary-unanimity testing among $n$ transformation-only users in a serial quantum architecture.<n>Bell entanglement is not required for the additive algebra, but it keeps the traveler locally maximally mixed in every honest trial.
  arXiv  Detail & Related papers  (2026-09-04T18:28:01Z)
• Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding [26.296743455346604]
  Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM)<n>We study the $T$ count of sparse QROM, in which only $s$ of the $2n$ addresses store nonzero data.<n>Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits.
  arXiv  Detail & Related papers  (2026-07-30T14:18:29Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression [0.0]
  Algebraic Replay Engine with constant-degree maps over a constant-size field, together with pointerless DFS and index-free streaming, ensures constant-size per-level tokens.<n>$S(b)=O(b+t/b)$ gives $O(sqrtt)$ space with no residual multiplicative polylog factors.
  arXiv  Detail & Related papers  (2025-08-20T16:27:53Z)
• Non-representable quantum measures [55.2480439325792]
  Grade-$d$ measures on a $sigma$-algebra $mathcalAsubseteq 2X$ over a set $X$ are generalizations of measures satisfying one of a hierarchy of weak additivity-type conditions.<n>Every signed polymeasure $lambda$ on $(X,mathcalA)d$ produces a grade-$d$ measure as its diagonal $widetildelambda(A):=lambda(A,cdots,A)$.
  arXiv  Detail & Related papers  (2025-08-20T00:47:24Z)
• On estimating the quantum $\ell_α$ distance [2.637436382971936]
  We develop an efficient rank-independent quantum estimator for $mathrmT_alpha(rho_0,rho_1)$ with time complexity.<n>Our algorithm reveals a dichotomy in the computational complexity of the Quantum State Distinguishability Problem with Schatten $alpha$-norm (QSD$_alpha$)<n>The hardness results follow from reductions based on new rank-dependent inequalities for the quantum $ell_alpha$ distance with $1leq alpha leq infty$, which are of independent interest.
  arXiv  Detail & Related papers  (2025-05-01T11:15:20Z)
• Linear Programming Bounds on $k$-Uniform States [13.489334588619041]
  The existence of $k$-uniform states has been a widely studied problem due to their applications in several quantum information tasks.<n>We establish several improved non-existence results and bounds on $k$-uniform states.
  arXiv  Detail & Related papers  (2025-03-04T02:53:55Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Asynchronous Approximate Agreement with Quadratic Communication [35.73648103944158]
  We consider an asynchronous network of $n$ message-sending parties, up to $t$ of which are byzantine.<n>In their seminal work, Abraham, Amit and Dolev [OPODIS '04] solve this problem in $mathbbR$ with the optimal resilience $t fracn3$.<n>This takes $Theta(n2)$ messages per reliable broadcast, or $Theta(n3)$ messages per iteration.
  arXiv  Detail & Related papers  (2024-08-10T09:03:06Z)
• Block Circulant Codes with Application to Decentralized Systems [12.014314088945968]
  We develop a family of $[n,k,d]$ block circulant codes that support distributed erasure decoding.<n>The code is ideal for use in protocols that address the data availability problem in blockchain networks.
  arXiv  Detail & Related papers  (2024-06-18T00:22:20Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
  We focus on the quantum communication complexity of functions of the form $f circ G = f(G)mathrmQCC_mathrmE(G)) when the parties are allowed to use shared entanglement. We show that the same statement holds emphwithout shared entanglement, which generalizes their result.
  arXiv  Detail & Related papers  (2023-01-01T08:30:35Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions. For tensor train decomposition, we give a bicriteria $(1 + eps)$-approximation algorithm with a small bicriteria rank and $O(q cdot nnz(A))$ running time. In addition, we extend our algorithm to tensor networks with arbitrary graphs.
  arXiv  Detail & Related papers  (2022-07-15T11:55:09Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.