論文の概要: On the uniqueness of compiling graphs under the parity transformation
- arxiv url: http://arxiv.org/abs/2401.11980v2
- Date: Mon, 24 Feb 2025 12:20:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-25 22:39:40.477306
- Title: On the uniqueness of compiling graphs under the parity transformation
- Title(参考訳): パリティ変換の下でのコンパイルグラフの特異性について
- Authors: Florian Dreier, Wolfgang Lechner,
- Abstract要約: 解析可能なすべてのハイパーグラフを包含するマッピングとしてパリティ変換を導入する。
すると、グラフのすべての同値類の任意の部分集合上の変換の射影性に対する等価条件を導出する。
本稿では,従来の計算機科学に基づいて,理論的にコンパイルされた物理レイアウトを計算するアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: In this article, we establish a mathematical framework that utilizes concepts from graph theory to formalize the parity transformation, an encoding strategy for compiling optimization problems on quantum devices. We introduce the transformation as a mapping that encompasses all possible compiled hypergraphs and investigate its uniqueness properties in more detail. Specifically, by introducing so-called loop labelings, we derive an alternative expression of the preimage of any set of compiled hypergraphs under this encoding procedure when all equivalence classes of graphs are being considered. We then deduce equivalent conditions for the injectivity of the parity transformation on any subset of all equivalences classes of graphs. Through concrete examples, we demonstrate that the parity transformation is not an injective mapping, and also introduce an important class of physical layouts and their corresponding set of constraints whose preimage is uniquely determined. In addition, we provide an algorithm which is based on classical algorithms from theoretical computer science and computes a compiled physical layout in this class in polynomial time.
- Abstract(参考訳): 本稿では、グラフ理論の概念を利用してパリティ変換を形式化する数学的枠組みを構築し、量子デバイス上で最適化問題をコンパイルするための符号化戦略について述べる。
この変換を,コンパイル可能なすべてのハイパーグラフを包含するマッピングとして導入し,その特異性特性をより詳細に検討する。
具体的には、いわゆるループラベリングを導入することにより、グラフの同値クラスが考慮されている場合、この符号化手順の下でコンパイルされたハイパーグラフの任意のセットの事前画像の代替表現を導出する。
すると、グラフのすべての同値類の任意の部分集合上のパリティ変換の単射性に対する等価条件を導出する。
具体例を通して、パリティ変換は射影写像ではないことを示し、また、物理配置の重要なクラスとそれに対応する制約のセットが一意に決定されることを示した。
さらに、理論計算機科学の古典的アルゴリズムに基づくアルゴリズムを提供し、このクラスにおけるコンパイルされた物理レイアウトを多項式時間で計算する。
関連論文リスト
- Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
グラフの有限集合がラプラシアンの重み付き和を通してデータ分布の関係を特徴付けるグラフ辞書信号モデルを定義する。
本稿では,観測データからグラフ辞書表現を推論するフレームワークを提案する。
我々は,脳活動データに基づく運動画像復号作業におけるグラフ辞書表現を利用して,従来の手法よりも想像的な動きをよりよく分類する。
論文 参考訳(メタデータ) (2024-11-08T17:40:43Z) - What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。
本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
論文 参考訳(メタデータ) (2024-06-04T05:30:16Z) - Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳(メタデータ) (2024-05-26T08:17:13Z) - SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
複素構造特性をチェックできるグラフ同型を一般化する。
この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。
本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-15T18:12:44Z) - Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
種々の非重み付きグラフの集合上でガウス過程の先行を定義するための原理的手法を提案する。
さらに、未重み付きグラフの同値類の集合を検討し、それに対する事前の適切なバージョンを定義する。
化学の応用に触発されて、我々は、小データ構造における実際の分子特性予測タスクについて、提案手法を解説した。
論文 参考訳(メタデータ) (2022-11-03T10:18:17Z) - Self-Supervised Graph Representation Learning via Topology
Transformations [61.870882736758624]
本稿では,グラフデータのノード表現のための自己教師型学習の一般的なパラダイムであるトポロジー変換同変表現学習について述べる。
実験では,提案手法を下流ノードおよびグラフ分類タスクに適用し,提案手法が最先端の教師なし手法より優れていることを示す。
論文 参考訳(メタデータ) (2021-05-25T06:11:03Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳(メタデータ) (2021-03-05T04:42:32Z) - Articulated Shape Matching Using Laplacian Eigenfunctions and
Unsupervised Point Registration [38.16866987817019]
スペクトルグラフ理論は、これらのグラフを低次元空間にマッピングし、それらの埋め込みを整列させることで形状と一致させることができる。
我々は、ラプラシア行列の固有関数の最適部分集合を選択することによって、2つの同値な$K$-次元の点集合の最良の整合を求める新しい定式化を導出する。
論文 参考訳(メタデータ) (2020-12-14T08:49:25Z) - Building powerful and equivariant graph neural networks with structural
message-passing [74.93169425144755]
本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。
まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。
次に,メッセージのパラメトリゼーション手法を提案する。
論文 参考訳(メタデータ) (2020-06-26T17:15:16Z) - The general theory of permutation equivarant neural networks and higher
order graph variational encoders [6.117371161379209]
一般置換同変層の式を導出し、各層が列と列を同時に置換することで行列に作用する場合を含む。
このケースはグラフ学習や関係学習アプリケーションで自然に発生する。
2階グラフ変分エンコーダを提案し、同変生成モデルの潜在分布は交換可能である必要があることを示す。
論文 参考訳(メタデータ) (2020-04-08T13:29:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。