論文の概要: Algebra of Nonlocal Boxes and the Collapse of Communication Complexity
- arxiv url: http://arxiv.org/abs/2312.00725v1
- Date: Fri, 1 Dec 2023 17:00:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-04 13:46:14.662256
- Title: Algebra of Nonlocal Boxes and the Collapse of Communication Complexity
- Title（参考訳）: 非局所的ボックスの代数と通信複雑性の崩壊
- Authors: Pierre Botteron, Anne Broadbent, Reda Chhaibi, Ion Nechita, and
Cl\'ement Pellegrini
- Abstract要約: 非局所的なボックスを接続する配線の構造について検討する。
関連する連想度と可換性を示す。
これにより「箱の軌道」という概念が生まれる。
- 参考スコア（独自算出の注目度）: 2.423370951696279
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Communication complexity quantifies how difficult it is for two distant
computers to evaluate a function $f(X,Y)$ where the strings $X$ and $Y$ are
distributed to the first and second computer, respectively and under the
constraint of exchanging as few bits as possible. Surprisingly, some nonlocal
boxes, which are resources shared by the two computers, are so powerful that
they allow to collapse communication complexity, in the sense that any Boolean
function $f$ can be correctly estimated with the exchange of only one bit of
communication. The Popescu-Rohrlich (PR) box is an example of such a collapsing
resource, but a comprehensive description of the set of collapsing nonlocal
boxes remains elusive.
In this work, we carry out an algebraic study of the structure of wirings
connecting nonlocal boxes, thus defining the notion of the "product of boxes"
$\mathtt{P}\boxtimes\mathtt{Q}$, and we show related associativity and
commutativity results. This gives rise to the notion of the "orbit of a box",
unveiling surprising geometrical properties about the alignment and parallelism
of distilled boxes. The power of this new framework is that it allows to prove
previously-reported numerical intuitions concerning the best way to wire
consecutive boxes, and to numerically and analytically recover
recently-identified noisy PR boxes that collapse communication complexity for
different types of noise models.
- Abstract（参考訳）: 通信複雑性は、2つの遠いコンピュータが関数$f(X,Y)$を評価するのがいかに困難であるかを定量化し、文字列$X$と$Y$はそれぞれ第1のコンピュータと第2のコンピュータに分配される。
驚くべきことに、2つのコンピュータが共有するリソースであるいくつかの非ローカルボックスは、通信の複雑さを崩壊させることができるほど強力であり、ブール関数の$f$は1ビットの通信の交換で正確に推定できる。
popescu-rohrlich(pr)ボックスは、そのような崩壊するリソースの例であるが、崩壊する非局所的なボックスの集合の包括的記述は、いまだに解明されていない。
本研究では、非局所的ボックスを接続する配線の構造に関する代数的研究を行い、「ボックスの積」 $\mathtt{P}\boxtimes\matht{Q}$ の概念を定義し、関連する連想性と可換性を示す。
これにより「箱の軌道」の概念が生まれ、蒸留箱のアライメントと平行性に関する驚くべき幾何学的性質が明らかになる。
この新しいフレームワークのパワーは、連続するボックスをつなぐ最善の方法に関する事前報告された数値直観を証明し、様々なタイプのノイズモデルで通信の複雑さを崩壊させる最近特定されたノイズprボックスを数値的かつ分析的に復元することを可能にすることである。
関連論文リスト
- Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳（メタデータ） (2023-10-05T07:10:40Z) - CORE: Common Random Reconstruction for Distributed Optimization with
Provable Low Communication Complexity [110.50364486645852]
コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。
本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
論文 参考訳（メタデータ） (2023-09-23T08:45:27Z) - Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-08-31T12:22:40Z) - Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation [0.19090202146054183]
分散クリフラベル問題により誘導される関係のクラスに対する一方向ゼロエラー古典的および量子的通信複雑性について検討する。
ここでは、プレイヤーがリソースを共有しない場合に考慮された特定の関係のクラスについて、任意のグラフに対してCCRタスクに量子的優位性はないことを示す。
我々は、このタスクの半デバイス非依存のディメンション目撃への応用と、ミューチュアルアンバイアスベースの検出について強調する。
論文 参考訳（メタデータ） (2023-05-17T16:58:05Z) - Extending the Known Region of Nonlocal Boxes that Collapse Communication
Complexity [1.1970409518725493]
非シグナリングボックス(Non-signalling box、NS)は、光速通信の原理によって定義される理論資源である。
そのうちのいくつかは、通信複雑性(CC)を崩壊させることで知られている。
本文では,非局所ボックスがCCを崩壊させるのに十分な条件を見出した。
論文 参考訳（メタデータ） (2023-02-01T14:50:08Z) - Error-free interconversion of nonlocal boxes [0.0]
本稿では,任意のタイプの極端2つの非局所署名ボックスを,他の極端2つの非局所署名ボックスに完全に変換するプロトコルを提案する。
我々の結果は正確であり、必要なボックスの数は事前に決定できないが、期待される数は有限である。
論文 参考訳（メタデータ） (2022-01-24T09:55:41Z) - Efficient exact computation of the conjunctive and disjunctive
decompositions of D-S Theory for information fusion: Translation and
extension [2.127049691404299]
デンプスター・シェーファー理論(DST)はベイズ確率論を一般化し、有用な追加情報を提供するが、高い計算負担に悩まされる。
本稿では,これらの分解物に含まれる実証拠(情報)を利用して計算する手法を提案する。
我々の公式は、識別のフレームのサイズが数ダースの可能な状態を超えると、引くことができる可能性を持っている。
論文 参考訳（メタデータ） (2021-07-13T18:41:54Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - DiscoBox: Weakly Supervised Instance Segmentation and Semantic
Correspondence from Box Supervision [98.25918224571132]
バウンディングボックスによるインスタンスセグメンテーションとセマンティック対応を共同学習する新しいフレームワークであるDiscoBoxを紹介します。
教師は、箱内と箱内の両方の画素関係をモデル化するために、ペアワイズ電位とクロスイメージ電位を組み込んだ構造化エネルギーモデルである。
教師のエネルギーを最小化することは、洗練されたオブジェクトマスクとクラス内のオブジェクト間の密接な対応を同時に生み出す。
論文 参考訳（メタデータ） (2021-05-13T17:59:41Z) - Non-Local Boxes for Networks [0.0]
量子ネットワークに適したネットワーク非ローカルボックスを導入する。
局所的なランダムな出力と最大2ボックス相関を生成するソースとボックスは本質的にユニークであることを示す。
論文 参考訳（メタデータ） (2021-02-06T15:29:53Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。