論文の概要: Quantum Entanglement Halves the Oblivious Update Bandwidth

• arxiv url: http://arxiv.org/abs/2605.19248v1
• Date: Tue, 19 May 2026 01:42:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.062529
• Title: Quantum Entanglement Halves the Oblivious Update Bandwidth
• Title（参考訳）: 量子エンタングルメント、帯域幅を拡大
• Authors: Sagar Dubey,
• Abstract要約: 私たちは、$(n,k)$ MDS-coded distributed storage over $mathbbF_q$ with per-node storage $$ symbolsと考える。 1つのメッセージシンボルが変更され、ヘルパーも古いノードも、どれを知らない場合、古典的な下限は$k log q$ bitsである。 我々は、$k$ヘルパーが事前の量子エンタングルメントを共有するとき、更新帯域幅が$lceil /2 rceil cdot k log q$ bits-等価であることを証明した。
• 参考スコア（独自算出の注目度）: 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$.
• Abstract（参考訳）: 我々は、$(n,k)$ MDS-coded distributed storage over $\mathbb{F}_q$ with per-node storage $α$ symbols。 1つのメッセージシンボルが変化し、ヘルパーも古いノードもそれを知らない場合、古典的な下限は$αk \log_2 q$ bitsである。 我々は、k$の接触ヘルパーが事前の量子エンタングルメントを共有するとき、更新帯域幅が$\lceil α/2 \cdot k \log_2 q$ bits-equivalentであり、2つの還元に近づいていることを証明した。 $α= 2$の場合、a $[[k, k-2]]_q$ CSSコードは、ヘルパー毎に1つのquditで帯域幅$k \log_2 q$を達成する。 一般的な$α$に対して、a $[[\lceil α/2 \rceil k, \lceil α/2 \rceil k - α]]_q$ CSSコードは、ヘルパーごとの$\lceil α/2 \rceil$ quditsとのバウンドを達成する。 スタルノードは送信された全てのキューディットを保持し、従って絡み合ったパートナーを保持するので、各ヘルパーのチャネルは、次元$D$に対して少なくとも$D^2$の区別可能な信号をサポートする。 この結果は、十分大きな素数$q$を持つすべての$(n,k)$対に対して成り立つ。

関連論文リスト

• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression [0.0]
  Algebraic Replay Engineは、ポインターレスDSSとインデックスなしストリーミングとともに、一定の大きさのフィールド上の一定度マップを持つ。 S(b)=O(b+t/b)$は、残余乗法的ポリログ因子を持たない$O(sqrtt)$空間を与える。
  論文  参考訳（メタデータ） (2025-08-20T16:27:53Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Asynchronous Approximate Agreement with Quadratic Communication [35.73648103944158]
  非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。 Abraham, Amit and Dolev [OPODIS '04] はこの問題を最適なレジリエンス $t fracn3$ で $mathbbR$ で解く。 これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
  論文  参考訳（メタデータ） (2024-08-10T09:03:06Z)
• Block Circulant Codes with Application to Decentralized Systems [12.014314088945968]
  我々は,分散消去復号化をサポートするブロック循環符号のファミリ[n,k,d]を開発する。 このコードは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的だ。
  論文  参考訳（メタデータ） (2024-06-18T00:22:20Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
  共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。 我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
  論文  参考訳（メタデータ） (2023-01-01T08:30:35Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。