論文の概要: Algebra of Nonlocal Boxes and the Collapse of Communication Complexity
- arxiv url: http://arxiv.org/abs/2312.00725v2
- Date: Wed, 17 Jan 2024 17:47:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 20:03:19.065425
- 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"
$P\boxtimes 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 observations 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（参考訳）: 通信複雑性は、文字列X,Yがそれぞれ第1及び第2のコンピュータに分散される関数f(X,Y)を、可能な限りビット交換の制約の下で評価することが、2つの遠隔コンピュータにとってどれだけ難しいかを定量化する。
驚くべきことに、2つのコンピュータが共有するリソースであるいくつかの非ローカルボックスは、ブール関数 f を1ビットの通信の交換で正確に推定できるという意味で、通信複雑性の崩壊を可能にするほど強力である。
popescu-rohrlich(pr)ボックスは、そのような崩壊するリソースの例であるが、崩壊する非局所的なボックスの集合の包括的記述は、いまだに解明されていない。
本研究では,非局所的ボックスを接続する配線の構造に関する代数的研究を行い,ボックスの積"$P\boxtimes 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) - 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) - Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。
最大勝利確率が量子値を超える任意の物理理論において、通信複雑性が崩壊することを示す。
我々は、0.91の結果が証明戦略の大規模なクラスで可能な限り最良のものであることを示す。
論文 参考訳（メタデータ） (2018-09-25T22:39:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。