論文の概要: 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（参考訳）: 量子エンタングルメント、帯域幅を拡大
• 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)$対に対して成り立つ。

関連論文リスト

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。 加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
  論文  参考訳（メタデータ） (2026-09-04T18:28:01Z)
• Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding [26.296743455346604]
  多くの量子アルゴリズムは古典的なデータへのコヒーレントなアクセスを必要とし、しばしば量子読み取り専用メモリ(QROM)によってモデル化される。 スパースQROMの$T$数を調べ、$2n$アドレスの$s$だけが非ゼロデータを格納している。 我々の上界はマルチレベルハッシュ方式を使用し、下界はスパースQROMを減らし、適応的なClifford+$T$回路のカウント引数を使用する。
  論文  参考訳（メタデータ） (2026-07-30T14:18:29Z)
• 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)
• Non-representable quantum measures [55.2480439325792]
  次数-$d$測度 a $sigma$-algebra $mathcalAsubseteq 2X$ over a set $X$ は弱加法的型条件の階層の1つを満たす測度の一般化である。 署名されたすべてのpoly measure $lambda$ on $(X,mathcalA)d$は、その対角的な$widetildelambda(A):=lambda(A,cdots,A)$としてグレード$d$測度を生成する。
  論文  参考訳（メタデータ） (2025-08-20T00:47:24Z)
• On estimating the quantum $\ell_α$ distance [2.637436382971936]
  時間複雑性を持つ$mathrmT_alpha(rho_0,rho_1)$に対する効率的なランク独立量子推定器を開発した。 我々のアルゴリズムは、量子状態微分可能性問題の計算複雑性の2分法をSchatten $alpha$-norm (QSD$_alpha$)で明らかにしている。 この硬さは、1leq α leq infty$ の量子 $ell_alpha$ 距離に対する新しい階数依存の不等式に基づく還元の結果に続く。
  論文  参考訳（メタデータ） (2025-05-01T11:15:20Z)
• Linear Programming Bounds on $k$-Uniform States [13.489334588619041]
  k$一様状態の存在は、いくつかの量子情報タスクに応用されているため、広く研究されている問題である。 我々は、いくつかの改良された非存在結果と$k$-一様状態のバウンダリを確立する。
  論文  参考訳（メタデータ） (2025-03-04T02:53:55Z)
• 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-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• 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)

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

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