論文の概要: Quantum Algorithms for Approximate Graph Isomorphism Testing

• arxiv url: http://arxiv.org/abs/2603.02656v1
• Date: Tue, 03 Mar 2026 06:43:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-04 21:38:10.67161
• Title: Quantum Algorithms for Approximate Graph Isomorphism Testing
• Title（参考訳）: 近似グラフ同型検査のための量子アルゴリズム
• Authors: Prateek P. Kulkarni,
• Abstract要約: 近似グラフ同型テストの量子クエリ複雑性について検討する。 入力グラフの積グラフ$(G,H)$に対するMNRS量子ウォーク探索に基づく量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on $n$ vertices drawn from the Erdős--Rényi distribution $\mathcal{G} (n,1/2)$ are considered approximately isomorphic if they can be made isomorphic by at most $k$ edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph $Γ(G,H)$ of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity $\mathcal{O}(n^{3/2} \log n/\varepsilon)$, where $\varepsilon$ parameterizes the approximation threshold. We complement this with an $Ω(n^2)$ classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.
• Abstract（参考訳）: グラフ同型問題は、2つのグラフが頂点 relabeling に等しいかどうかを問う。 正確な問題は準多項式時間古典アルゴリズムを許容するが、分子比較、ノイズの多いネットワーク分析、パターン認識といった多くの応用には、構造的類似性の柔軟な概念が必要である。 近似グラフ同型テストの量子クエリ複雑性について検討し、エルデシュ-レーニ分布$\mathcal{G} (n,1/2)$から引き出された$n$の頂点上の2つのグラフを、少なくとも$k$のエッジ編集で同型にできるならば、概同型と見なすことができる。 MNRS量子ウォークサーチに基づく量子アルゴリズムを, 2つの入力グラフの積グラフの$(G,H)$に対して提案する。 グラフがほぼ同型であるとき、量子ウォーク探索は、密接な近接同型マッチング集合に属する頂点対を検出し、候補ペアリングは局所的な一貫性の伝播によって再構成され、グロバー加速整合チェックによって検証される。 このアプローチはクエリの複雑さを$\mathcal{O}(n^{3/2} \log n/\varepsilon)$で証明し、$\varepsilon$は近似しきい値のパラメータ化を行う。 我々はこれを定数近似の古典的下界$Ω(n^2)$で補い、クエリモデルに真の多項式量子スピードアップを確立する。 グラフラプラシア固有値と重み付きおよび属性付きグラフに基づくスペクトル類似度尺度に拡張する。 最大20頂点のグラフに対する量子シミュレータの小型シミュレーションの結果は、短期的な量子デバイスとの互換性を示す。

関連論文リスト

• Symmetric and Antisymmetric Quantum States from Graph Structure and Orientation [0.0]
  グラフ状態が粒子置換の下で完全に対称であることは、基礎となるグラフが完備である場合に限る。 任意の向きが与えられた完全有向グラフは、奇数の四重項が完全に非対称な多粒子状態を生成することを示す。
  論文  参考訳（メタデータ） (2026-01-27T18:12:52Z)
• Combinatorial structures in quantum correlation: A new perspective [1.2078273498134855]
  我々は、$A_$-graph状態と呼ばれる新しい量子状態のクラスを導入する。 構築された状態は、安定化形式主義から生じる標準グラフ状態とは異なる。 モーメントに基づく絡み検出基準をグラフ理論で定式化する。
  論文  参考訳（メタデータ） (2025-12-17T18:44:07Z)
• Quadratic Quantum Speedup for Finding Independent Set of a Graph [5.668733678326325]
  グラフ内の独立集合を見つけるための量子アディアバティックアルゴリズム(QAA)の二次的高速化が解析的に証明されている。 スケールが$O(n2)$の古典的アルゴリズムと比較して、我々の量子アルゴリズムは、大きなISを見つけるために$O(n2)$の時間複雑性を達成し、サイズ2ISを特定するために$O(n)$に還元する。
  論文  参考訳（メタデータ） (2025-10-30T11:35:47Z)
• Studies of properties of bipartite graphs with quantum programming [0.0]
  両部グラフの$G(U,V,E)$に対応するマルチキュービット量子状態について検討する。 得られた状態の絡み合い距離は任意の二部グラフ構造に対して解析的に導出される。
  論文  参考訳（メタデータ） (2025-07-22T14:49:57Z)
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。 量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
  論文  参考訳（メタデータ） (2024-07-01T06:09:19Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  フービニ・スタディ計量に基づく絡み合い尺度は、Cocchiarellaと同僚によって最近導入された。 本稿では,多モードガウス状態に対する幾何絡み合いの一般化であるガウスエンタングルメント尺度(GEM)を提案する。 自由度の高い系に対する計算可能な多部絡み合わせ測度を提供することにより、自由なボゾン場理論の洞察を得るために、我々の定義が利用できることを示す。
  論文  参考訳（メタデータ） (2024-01-31T15:50:50Z)
• Understanding Heterophily for Graph Neural Networks [42.640057865981156]
  グラフニューラルネットワーク(GNN)における異方性パターンの影響に関する理論的理解について述べる。 分離性ゲインは、$l$の近隣分布の正規化距離によって決定されることを示す。 合成データと実世界のデータの両方の実験により、我々の理論の有効性が検証された。
  論文  参考訳（メタデータ） (2024-01-17T11:01:28Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
  グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)? 本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。 この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:54:27Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。