論文の概要: NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
- arxiv url: http://arxiv.org/abs/2407.10635v1
- Date: Mon, 15 Jul 2024 11:48:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 15:31:11.854839
- Title: NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
- Title（参考訳）: 量子同型およびホモモルフィズムのNPA階層
- Authors: Prem Nigam Kar, David E. Roberson, Tim Seppelt, Peter Zeman,
- Abstract要約: グラフの量子同型に対するSDP緩和のNPA階層の各々のレベルは、平面グラフの適切なクラスに対する準同型独立性と同値であることを示す。
この準同型不連続性の特徴付けはまた、量子同型に対するSDP緩和のNPA階層の固定レベル毎の正確な実現性を決定するランダム化時間アルゴリズムを与えることもできる。
- 参考スコア（独自算出の注目度）: 0.18749305679160366
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Man\v{c}inska and Roberson~[FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al.~[JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt~[ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Man\v{c}inska and Roberson~[FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
- Abstract（参考訳）: Man\v{c}inska と Roberson~[FOCS'20] は、2つのグラフが量子同型であることと、それらが平面グラフのクラスに対して同型でない場合に限ることを示した。
Atserias et al ~[JCTB'19] は一般に量子同型は決定不可能であることを証明した。
NPA階層は、量子同型性の半定値プログラミング緩和の列を与える。
最近、Roberson と Seppelt~[ICALP'23] は、グラフ同型半定型プログラミング緩和のラッサール階層の各レベルの実現性について、同型不同型の評価を得た。
我々は、グラフの量子同型に対するSDP緩和のNPA階層のそれぞれのレベルが、適切な平面グラフのクラスに対する準同型独立性と同値であることを示すことによって、この結果の量子的類似性を証明する。
NPA階層の収束と、これらのグラフクラスの和がすべての平面グラフの集合であるという事実を組み合わせることで、量子群の理論の使用を避けるMan\v{c}inskaとRoberson~[FOCS'20]の結果の新たな証明を与えることができる。
この準同型不連続性の特徴付けはまた、量子同型に対するSDP緩和のNPA階層のそれぞれの固定レベルの正確な実現性を決定するランダム化多項式時間アルゴリズムを与えることもできる。
関連論文リスト
- Detecting Homeomorphic 3-manifolds via Graph Neural Networks [0.0]
グラフニューラルネットワークを用いたグラフ多様体のクラスに対する同相性問題について検討する。
2つの畳み込みレイヤの異なる組み合わせをテストすることで、教師付き学習環境でさまざまなネットワークアーキテクチャをトレーニングし、ベンチマークします。
論文 参考訳（メタデータ） (2024-09-01T12:58:09Z) - Discrete Graph Auto-Encoder [52.50288418639075]
離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。
まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。
2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
論文 参考訳（メタデータ） (2023-06-13T12:40:39Z) - Probing Graph Representations [77.7361299039905]
グラフ表現でキャプチャされた意味のある情報の量を定量化するために、探索フレームワークを使用します。
本研究は, グラフモデルにおける帰納的バイアスを理解するための探索の可能性を示すものである。
グラフベースモデルを評価する上で有用な診断ツールとして,探索を提唱する。
論文 参考訳（メタデータ） (2023-03-07T14:58:18Z) - Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant
Viewpoint [0.0]
グラフ準同型(Graph homomorphism)は、$mathcalF$ と $mathcalF'$ のそれぞれが 1 つの対称な 0-1 値のバイナリ制約関数を含む特別な場合である。
任意のペアの集合 $mathcalF$ と $mathcalF'$ は、任意の平面#CSPインスタンスに同じ値を与える実数値で任意のアリティ制約関数を示す。
論文 参考訳（メタデータ） (2022-12-06T21:38:40Z) - Quantum isomorphism of graphs from association schemes [0.0]
同じ数の頂点上の任意の2つのアダマールグラフが量子同型であることを示す。
これは、ある関連スキームから生じるグラフの量子同型を示すより一般的なレシピから従う。
論文 参考訳（メタデータ） (2022-09-10T03:22:28Z) - Casting graph isomorphism as a point set registration problem using a
simplex embedding and sampling [0.0]
グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。
それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。
等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
論文 参考訳（メタデータ） (2021-11-15T12:16:21Z) - Relative stability toward diffeomorphisms in deep nets indicates
performance [66.51503682738931]
微分同相性に対する安定性は、画像のベンチマークデータセットの性能と強く相関しないことを示す。
一般変換に対する微分同相性に対する安定性は、テスト誤差 $epsilon_t$ と著しく相関している。
CIFAR10と15の既知のアーキテクチャでは、$epsilon_tapprox 0.2sqrtR_f$を見つける。
論文 参考訳（メタデータ） (2021-05-06T07:03:30Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。
我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
論文 参考訳（メタデータ） (2020-10-28T17:59:59Z) - Algebraic Neural Networks: Stability to Deformations [179.55535781816343]
可換代数を用いた代数ニューラルネットワーク(AlgNN)について検討する。
AlgNNはユークリッド畳み込みニューラルネットワーク、グラフニューラルネットワーク、グループニューラルネットワークなどの多様なアーキテクチャを統合する。
論文 参考訳（メタデータ） (2020-09-03T03:41:38Z) - Graph Homomorphism Convolution [19.94778871237204]
グラフ準同型数は、グラフ分類に使用できる自然な不変量(同型不変量および$mathcalF$-不変量)を提供することを示す。
木幅が有界な元を持つ$mathcalF$を選択することで、同型法は他の方法と比較して効率的であることを示す。
論文 参考訳（メタデータ） (2020-05-03T23:56:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。