論文の概要: Communication Complexity of Graph Isomorphism, Coloring, and Distance Games
- arxiv url: http://arxiv.org/abs/2406.02199v2
- Date: Tue, 25 Jun 2024 15:14:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-26 19:39:42.356524
- Title: Communication Complexity of Graph Isomorphism, Coloring, and Distance Games
- Title（参考訳）: グラフ同型・色・距離ゲームにおける通信複雑度
- Authors: Pierre Botteron, Moritz Weber,
- Abstract要約: 最適な条件下では,完全非署名戦略が通信複雑性を崩壊させることを示す。
意外なことに、非シグナリング戦略は、古典的および量子的戦略と比較して、新しいゲームにとってより微妙な区別を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter $D\in\mathbb N$, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.
- Abstract（参考訳）: 量子情報において、非局所ゲームは古典的、量子的、および非シグナリング相関の微分に特に有用である。
区別の例としては、通信複雑性の非崩壊の原理があり、これは実現可能な物理理論に必要なものとしてしばしば解釈される。
量子相関によって満たされるが、いくつかの非シグナリングによって破られる。
本研究では,グラフ理論に関連する3つの非局所ゲームについて,よく知られたグラフ同型およびグラフカラー化ゲームから始まり,パラメータ$D\in\mathbb N$で新たなゲームである頂点距離ゲームを導入することから,この原理を考察する。
これら3つのゲームに対して、最適な条件下での通信複雑性を崩壊させる完全ノンシグナリング戦略が証明される。
また、グラフの分数同型、すなわちD-分数同型(D-分数同型)の洗練も定義し、これは頂点距離ゲームに対する完全非符号戦略を特徴付けることを示す。
意外なことに、パラメータDが非シグナリング設定でのみ可視であるため、非シグナリング戦略は古典的および量子的戦略と比較して、新しいゲームに対してより微妙な区別を与える。
関連論文リスト
- Graphon Pooling for Reducing Dimensionality of Signals and Convolutional
Operators on Graphs [131.53471236405628]
グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。
これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。
我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
論文 参考訳（メタデータ） (2022-12-15T22:11:34Z) - G-MSM: Unsupervised Multi-Shape Matching with Graph-based Affinity
Priors [52.646396621449]
G-MSMは、非剛体形状対応のための新しい教師なし学習手法である。
学習形態の集合に親和性グラフを自己教師型で構築する。
近年の形状対応ベンチマークで最先端の性能を示す。
論文 参考訳（メタデータ） (2022-12-06T12:09:24Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Quantum hypergraph homomorphisms and non-local games [1.0152838128195465]
量子ハイパーグラフ準同型(quantum hypergraph homomorphisms)と量子ハイパーグラフ同型(quantum hypergraph isomorphisms)はそれぞれ部分順序と同値関係を構成することを示す。
基礎となるハイパーグラフが非局所ゲームから生じる場合に特化して、量子非局所ゲーム同型と量子非局所ゲーム同型の概念を定義する。
論文 参考訳（メタデータ） (2022-11-09T12:44:24Z) - Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
本稿では,2色グラフの入射系を基礎とするグラフ入射ゲームの解群について検討する。
アルキポフの定理は、連結グラフのグラフ入射ゲームが完全量子戦略を持つことは、それが完全古典的戦略を持つか、あるいはグラフが非平面的であることを言う。
我々はアルキポフの定理を拡張し、連結な2色グラフのグラフ入射ゲームに対して、解群のすべての商閉性は禁じられたマイナーな性質を持つことを示した。
論文 参考訳（メタデータ） (2022-05-10T03:21:38Z) - Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states [0.0]
特に、ほぼ完全な量子戦略は、小さなフロベニウスノルムにおける対応するBCS代数の近似表現であることを示す。
XOR の非局所ゲームに対して、準最適量子戦略はゲームに関連する対応する *-代数の近似表現であることを示す。
論文 参考訳（メタデータ） (2022-03-04T19:05:58Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
論文 参考訳（メタデータ） (2021-12-09T21:06:52Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳（メタデータ） (2021-06-26T06:24:51Z) - Synchronicity for quantum non-local games [0.7646713951724009]
量子グラフの量子準同型(quantum homomorphisms of quantum graphs)は、そのグラフの古典的準同型(classical homomorphisms of the graphs)とみなすことができる。
量子グラフ準同型ゲームにおける完全量子交換と完全近似量子戦略について記述する。
論文 参考訳（メタデータ） (2021-06-22T02:40:41Z) - The quantum-to-classical graph homomorphism game [0.0]
量子グラフと古典グラフの間のグラフ準同型ゲームを導入する。
ゲームに対する様々な量子モデルの勝利戦略は、非可換グラフ準同型の概念の類似であることを示す。
また、全ての量子完備グラフの明示的な量子色付けを実証し、量子グラフに対する4ドルの色付けゲームの代数は常に非自明なものであるという驚くべき事実を導いた。
論文 参考訳（メタデータ） (2020-09-15T17:09:35Z) - Spectra of Perfect State Transfer Hamiltonians on Fractal-Like Graphs [62.997667081978825]
完全量子状態移動の特別な性質を示すハミルトニアンのフラクタル様グラフのスペクトル特性について検討する。
基本的な目標は、完全な量子状態転移、スペクトル特性、基礎となるグラフの幾何学の間の相互作用を理解するための理論的枠組みを開発することである。
論文 参考訳（メタデータ） (2020-03-25T02:46:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。