論文の概要: Optimal entanglement-assisted source coding under a balanced-difference promise
- arxiv url: http://arxiv.org/abs/2609.15757v1
- Date: Mon, 14 Sep 2026 15:43:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 07:15:06.476058
- Title: Optimal entanglement-assisted source coding under a balanced-difference promise
- Title（参考訳）: バランスディファレンス約束の下での最適絡み合わせ支援音源符号化
- Abstract要約: 絡み合いは、コーディングタスクに必要なコミュニケーションを減らすことができるが、その限界を理解するためには、達成可能な最小コストの確立が不可欠である。
我々は、Aliceが単語を受信し、Bobはその単語を含む無秩序な候補のペアを知っているゼロエラーソースコーディングタスクでこの問題に対処する。
我々は、$(q-1)ell$が偶数であるとき、そのタスクに正確に$n$メッセージが必要であることを証明している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits. We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it. Alice does not know the pair and must enable Bob to identify her word without error using shared entanglement and one classical message. The candidates satisfy a balanced-difference promise: for words in $\mathbb{Z}_q^n$ with $n=q\ell$, each residue modulo $q$ occurs exactly $\ell$ times in their coordinatewise difference. For all integers $q\geq2$ and $\ell\geq1$, we prove that the task requires exactly $n$ messages when $(q-1)\ell$ is even and two messages when it is odd. These minima allow arbitrary finite-dimensional shared states independent of the inputs and arbitrary local measurements. In even parity, this establishes optimality of an existing entanglement-assisted protocol. In odd parity, an explicit deterministic protocol achieves the optimum of one bit without entanglement. Our proof combines Fourier analysis with a combinatorial counting argument to determine the smallest eigenvalue of the associated graphs. In even parity, this resolves the spectral assertion of Cao et al.'s Conjecture 6.3 for balanced cyclic generalized Hadamard graphs. Together with an explicit odd-parity bipartition, this determines the quantum chromatic number as $n$ in even parity and $2$ in odd parity, where the classical chromatic number is also $2$. All lemmas, theorems, and corollaries are formalized and verified in Lean.
- Abstract（参考訳）: 絡み合いは、コーディングタスクに必要なコミュニケーションを減らすことができるが、その限界を理解するためには、達成可能な最小コストの確立が不可欠である。
我々は、Aliceが単語を受信し、Bobはその単語を含む無秩序な候補のペアを知っているゼロエラーソースコーディングタスクでこの問題に対処する。
アリスはペアを知らないので、ボブは共通の絡み合いと1つの古典的なメッセージを使って間違いなしに単語を識別できなければならない。
例えば、$\mathbb{Z}_q^n$ と $n=q\ell$ の単語の場合、各残基の modulo $q$ は座標差で正確に $\ell$ times となる。
すべての整数 $q\geq2$ と $\ell\geq1$ に対して、$(q-1)\ell$ が偶数であるとき、そのタスクが正確に$n$メッセージを必要としていることを証明します。
これらのミニマは入力と任意の局所測定から独立して任意の有限次元共有状態を可能にする。
たとえ同等であっても、既存の絡み合い支援プロトコルの最適性を確立する。
奇数のパリティにおいて、明示的な決定論的プロトコルは、絡み合わずに1ビットの最適性を達成する。
我々の証明はフーリエ解析と組合せ数論とを組み合わせて、関連するグラフの最小固有値を決定する。
たとえパリティであっても、これは、平衡された巡回一般化アダマールグラフに対するCao et al の Conjecture 6.3 のスペクトルアサーションを解消する。
明示的な奇数-パリティ分割と合わせて、量子色数は偶数で$n$、奇数で$2$と決定される。
すべての補題、定理、結論はLeanで形式化され、検証されます。
関連論文リスト
- On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
我々はtextscIndex Coordination の自然な $k$-party 一般化を通じて,多元的指数分離を確立する。
量子重ね合わせは、公共のランダム性によって得られる調整を効率的にシミュレートできないことを示し、この分離を任意の$k$に拡張する。
論文 参考訳（メタデータ） (2026-09-09T15:07:22Z) - Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。
加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
論文 参考訳（メタデータ） (2026-09-04T18:28:01Z) - Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening [26.60272178029048]
我々は,少なくとも$-を達成するためのプロトコルを,2$mathcal O(CC_(G))/2$の通信ビットのみを用いて示す。
本研究の結果は,マルチエージェント情報集約文学における先行研究で要求される仮定を厳格に弱めることに留意する。
論文 参考訳（メタデータ） (2026-08-05T18:34:19Z) - The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - Quantum Search With Generalized Wildcards [0.4310167974376404]
我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。
以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
論文 参考訳（メタデータ） (2025-11-06T18:55:05Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳（メタデータ） (2024-04-16T00:56:36Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Tight Bounds for the Randomized and Quantum Communication Complexities
of Equality with Small Error [1.6522364074260811]
誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。
任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
論文 参考訳（メタデータ） (2021-07-25T13:52:42Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。