Fugu-MT 論文翻訳(概要): A Quantum Algorithm for the Sub-Graph Isomorphism Problem

論文の概要: A Quantum Algorithm for the Sub-Graph Isomorphism Problem

arxiv url: http://arxiv.org/abs/2111.09732v2
Date: Fri, 2 Sep 2022 08:51:50 GMT
ステータス: 処理完了
システム内更新日: 2023-03-07 12:37:17.089103
Title: A Quantum Algorithm for the Sub-Graph Isomorphism Problem
Title（参考訳）: 部分グラフ同型問題に対する量子アルゴリズム
Authors: Nicola Mariella and Andrea Simonetto
Abstract要約: ゲート型量子コンピュータ上でのサブグラフ同型問題を解くための新しい変分法を提案する。本手法は,中期の現実的な部分グラフ同型問題に対して適用可能であることを示す。
参考スコア（独自算出の注目度）: 3.04585143845864
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new Ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.
Abstract（参考訳）: ゲート型量子コンピュータ上でのサブグラフ同型問題を解くための新しい変分法を提案する。この方法は、(1)グラフの頂点数と対数的にスケールする多数の量子ビットを必要とする、基礎となるグラフの隣接行列の新しい表現に依存し、(2)置換空間を効率的に探索できる新しいアンサッツに依存する。グラフ上の16頂点までのアプローチを示すためにシミュレーションが提示され、対数スケーリングを考えると、このアプローチは中項における現実的な部分グラフ同型問題に適用することができる。

関連論文リスト

Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文参考訳（メタデータ） (2024-07-01T06:09:19Z)
Discrete Graph Auto-Encoder [52.50288418639075]
離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
論文参考訳（メタデータ） (2023-06-13T12:40:39Z)
Harnessing spectral representations for subgraph alignment [15.86857474914914]
本稿では,コンパクトで計算が容易で,トポロジ的変化に頑健で,既存のパイプラインに差し込むのが容易で,特に部分グラフアライメント問題に有効である地図のスペクトル表現を提案する。サブグラフアライメントタスクで生じる部分性がマップ係数の特別な構造として表される驚くべき現象を初めて報告する。
論文参考訳（メタデータ） (2022-05-30T09:03:28Z)
Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals [8.140698535149042]
本稿では,その隣接行列を推定することにより,スパース重み付きグラフを学習するアルゴリズムを提案する。提案アルゴリズムは,本論文におけるいくつかの既存手法よりも,平均反復回数の観点から,より高速に収束することを示す。
論文参考訳（メタデータ） (2022-02-06T17:06:13Z)
On The Variational Perspectives To The Graph Isomorphism Problem [0.0]
本稿では,変分アルゴリズムの観点からグラフ同型問題について考察する。本研究では,4ノードと5ノードのグラフに対して,アルゴリズムの結果と,そこで発生する変動について述べる。
論文参考訳（メタデータ） (2021-11-18T17:43:21Z)
Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
論文参考訳（メタデータ） (2021-11-15T12:16:21Z)
Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文参考訳（メタデータ） (2020-10-20T05:54:31Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)
Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
グラフ信号定常性の概念に依存するオフライン手法を提案する。我々の検出器は、漸近的でない不等式オラクルの証拠を伴っている。
論文参考訳（メタデータ） (2020-06-18T15:51:38Z)
Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文参考訳（メタデータ） (2020-03-12T22:31:59Z)
Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
本稿では,最近のスコアベース生成モデルを用いて,グラフモデリングにおける置換不変手法を提案する。特に、入力グラフにおけるデータ分布の勾配をモデル化するために、置換同変のマルチチャネルグラフニューラルネットワークを設計する。グラフ生成では、我々の学習アプローチはベンチマークデータセット上の既存のモデルよりも良い、あるいは同等の結果を得る。
論文参考訳（メタデータ） (2020-03-02T03:06:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。