論文の概要: Quantum Perfect Matchings
- arxiv url: http://arxiv.org/abs/2502.05136v1
- Date: Fri, 07 Feb 2025 18:13:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-10 14:56:11.147936
- Title: Quantum Perfect Matchings
- Title（参考訳）: 量子完全マッチング
- Authors: David Cui, Laura Mančinska, Seyed Sajjad Nezhadi, David E. Roberson,
- Abstract要約: 両部グラフにおける$L$完全マッチング、一般グラフやハイパーグラフにおける完全マッチング、分数完全マッチングをテストする非局所ゲームを導入する。
完全マッチングの量子および非符号化バージョンを定義するために、これらのゲームに完全量子および非符号化戦略が存在することを利用する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for $L$-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. Our definitions come from the fact that these games are classical property tests for the corresponding matching conditions. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings. Finally, we provide characterizations of when graphs exhibit these extended properties: - For nonsignaling matchings, we give a complete combinatorial characterizations. In particular, a graph has a nonsignaling perfect matching if and only if it admits a fractional perfect matching that has bounded value on triangles. \item In bipartite graphs, the nonsignaling $L$-perfect matching property is achieved exactly when the left component of the graph can be split into two disjoint subgraphs: one with a classical $L$-perfect matching and another with left-degree 2. - In the quantum setting, we show that complete graphs $K_n$ with odd $n \geq 7$ have quantum perfect matchings. We prove that a graph has a quantum perfect matching if and only if the quantum independence number of its line graph is maximal, extending a classical relationship between perfect matchings and line graph independence numbers. - For bipartite graphs, we establish that the $L$-perfect matching game does not exhibit quantum pseudotelepathy, but we characterize the quantum advantage for complete bipartite graphs $K_{n,2}$. - Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leave open the question of its complexity in graphs.
- Abstract（参考訳）: 非局所ゲームを用いたグラフにおける完全マッチングの量子化と非符号化の一般化について検討する。
具体的には、二部グラフにおける$L$完全マッチング、一般グラフやハイパーグラフにおける完全マッチング、分数完全マッチングをテストする非局所ゲームを紹介する。
我々の定義は、これらのゲームが対応するマッチング条件に対する古典的なプロパティテストであるという事実に由来する。
完全マッチングの量子および非符号化バージョンを定義するために、これらのゲームに完全量子および非符号化戦略が存在することを利用する。
最後に、グラフがこれらの拡張された性質を示すときの特徴を与える: - 非シグナリングマッチングに対して、完全な組合せ的特徴付けを与える。
特に、グラフが非有理完全マッチングを持つのは、それが三角形上の有界値を持つ分数完全マッチングを持つ場合に限である。
\item 両部グラフにおいて、非符号付き$L$完全整合性は、グラフの左成分が2つの非連結部分グラフ(古典的な$L$完全整合を持つ部分グラフと左次2の部分グラフを持つ部分グラフ)に分割できるときに正確に達成される。
-量子環境では、奇数$n \geq 7$の完全グラフが量子完全マッチングを持つことを示す。
グラフが量子完全マッチングを持つことは、その線グラフの量子独立数が最大であることと、その線グラフ独立数と完全マッチングの古典的関係を延長することの証明である。
-二部グラフの場合、$L$完全マッチングゲームは量子擬似テレパシーを示さないが、完全二部グラフに対して$K_{n,2}$の量子優位性を特徴付ける。
さらに、ハイパーグラフにおける量子完全マッチングの決定は決定不可能であることを証明し、グラフにおけるその複雑性の問題を解き放つ。
関連論文リスト
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。
量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。
このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文 参考訳（メタデータ） (2024-07-01T06:09:19Z) - Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
最適な条件下では,完全非署名戦略が通信複雑性を崩壊させることを示す。
意外なことに、非シグナリング戦略は、古典的および量子的戦略と比較して、新しいゲームにとってより微妙な区別を提供する。
論文 参考訳（メタデータ） (2024-06-04T10:53:16Z) - M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning
of Mixture Graph Matching and Clustering [57.947071423091415]
本稿では,理論収束を保証する学習自由度アルゴリズムであるM3Cを提案する。
我々は、新しいエッジワイド親和性学習と擬似ラベル選択を組み込んだ教師なしモデルUM3Cを開発した。
提案手法は,最先端のグラフマッチングと混合グラフマッチングとクラスタリングの手法を精度と効率の両面で優れている。
論文 参考訳（メタデータ） (2023-10-27T19:40:34Z) - On the Equivalence of Graph Convolution and Mixup [70.0121263465133]
本稿では,グラフ畳み込みと混合手法の関係について検討する。
2つの穏やかな条件の下では、グラフの畳み込みはMixupの特別な形式と見なすことができる。
グラフ畳み込みネットワーク(GCN)と単純化グラフ畳み込み(SGC)をミックスアップの形で表現できることを証明し、数学的にこの等価性を確立する。
論文 参考訳（メタデータ） (2023-09-29T23:09:54Z) - Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
Matching [68.35685422301613]
そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。
ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。
合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
論文 参考訳（メタデータ） (2023-01-07T05:14:45Z) - Learning Universe Model for Partial Matching Networks over Multiple
Graphs [78.85255014094223]
2つまたは複数のグラフの部分的マッチングのための宇宙マッチングスキームを開発する。
不整合及び不整合検出のための微妙なロジックを、明確にモデル化することができる。
これは、2グラフマッチング、複数グラフマッチング、オンラインマッチング、混合グラフマッチングを同時に扱うことができる最初のディープラーニングネットワークである。
論文 参考訳（メタデータ） (2022-10-19T08:34:00Z) - Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
本稿では,2色グラフの入射系を基礎とするグラフ入射ゲームの解群について検討する。
アルキポフの定理は、連結グラフのグラフ入射ゲームが完全量子戦略を持つことは、それが完全古典的戦略を持つか、あるいはグラフが非平面的であることを言う。
我々はアルキポフの定理を拡張し、連結な2色グラフのグラフ入射ゲームに対して、解群のすべての商閉性は禁じられたマイナーな性質を持つことを示した。
論文 参考訳（メタデータ） (2022-05-10T03:21:38Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。
提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。
すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
論文 参考訳（メタデータ） (2021-09-01T08:24:02Z) - Quantum search of matching on signed graphs [0.0]
我々は,量子ウォークによって駆動される符号付きエッジの量子探索モデルを構築した。
完全グラフ上のマッチングを与える任意のエッジカラー化の下で、完全グラフのエッジ集合から有色エッジの量子探索を考える。
論文 参考訳（メタデータ） (2020-07-13T09:36:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。