論文の概要: Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication
- arxiv url: http://arxiv.org/abs/2609.14658v1
- Date: Sun, 13 Sep 2026 16:55:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 12:40:38.835506
- Title: Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication
- Title（参考訳）: 量子SMPとワンウェイ通信のための励起漸近速度と指数強変換
- Abstract要約: fn$ のインスタンスあたりの最適な最悪の通信は [ Dparallel(f)=log|mathrmRow(f)|+log|mathrmCol(f)| に収束する。
また、同じしきい値が指数的強い逆を支配していることも証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function $f$ and fixed error $0\le\varepsilon<1$, we prove that the optimal worst-case communication per instance for $f^n$ converges to \[ D^\parallel(f)=\log|\mathrm{Row}(f)|+\log|\mathrm{Col}(f)|, \] where $\mathrm{Row}(f)$ and $\mathrm{Col}(f)$ are the sets of distinct rows and columns of the table $(f(x,y))_{x,y}$. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all $n$ outputs correctly to decay as $2^{-Ω(n)}$, even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is $(1-\varepsilon)D^\parallel(f)$. Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with $D^\parallel(f)$ replaced by $\log|\mathrm{Row}(f)|$. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.
- Abstract（参考訳）: 多数のインスタンスを共同で計算することで、インスタンスごとの通信を削減できる。
我々は、同時メッセージパッシング(SMP)モデルでそのような貯蓄が発生するか、量子メッセージや共有リソースにどのように依存するかを問う。
すべての有限総関数 $f$ と固定誤差 $0\le\varepsilon<1$ に対して、$f^n$ のインスタンスあたりの最適な最悪の通信は \[D^\parallel(f)=\log|\mathrm{Row}(f)|+\log|\mathrm{Col}(f)|, \] に収束する。
これは、共有絡みのない古典的および量子的SMPに対して、共有ランダム性の有無にかかわらず成り立つ。
このように、行と列のインデックスの送信は、境界誤差、合同計算、量子メッセージでさえ漸近的に最適である。
特に、共有ランダム性のない単一のインスタンスに対する量子フィンガープリントの指数的優位性は、漸近的な速度で消える。
我々はまた、同じしきい値が指数関数的な強い逆を支配していることを証明している: その下にある固定された最悪の通信速度は、固定積の入力分布の平均下でさえ、すべての$n$出力を正しく計算する確率を$2^{-Ω(n)}$として減衰させる。
共有ランダム性では、最適な通信レートは$(1-\varepsilon)D^\parallel(f)$である。
各送信者とレフェリーの間で共有される絡み合いは両者の利率を半減させる。
D^\parallel(f)$ は $\log|\mathrm{Row}(f)|$ に置き換えられる。
我々の証明はSMPを一方的な通信に還元し、量子ミニエントロピーに基づくサンプリングに計算を成功させる。
関連論文リスト
- On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
我々はtextscIndex Coordination の自然な $k$-party 一般化を通じて,多元的指数分離を確立する。
量子重ね合わせは、公共のランダム性によって得られる調整を効率的にシミュレートできないことを示し、この分離を任意の$k$に拡張する。
論文 参考訳（メタデータ） (2026-09-09T15:07:22Z) - Distributed Monogamy of Entanglement limits Quantum Channel Simulation [2.277447144331876]
分数拡張性を導入し、環境に漏れる量子相関のよりきめ細かな特徴を与える。
例えば、$AB_Bdots B_n$の任意の状態に対して、$B_i$s内の$k leq n/2$系のランダム部分集合からEPRペアを抽出する最大平均確率は、$k/n$である。
論文 参考訳（メタデータ） (2026-07-09T15:26:41Z) - Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。
離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
論文 参考訳（メタデータ） (2026-05-05T12:25:17Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - Quantum advantage in zero-error function computation with side information [10.0060346233449]
本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。
Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. Bob want to compute $f(X,Y)$ with zero error。
論文 参考訳（メタデータ） (2024-02-02T16:41:36Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Capacity Approaching Coding for Low Noise Interactive Quantum
Communication, Part I: Large Alphabets [15.078027648304115]
ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。
$mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。
我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
論文 参考訳（メタデータ） (2020-01-09T02:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。