論文の概要: Testing graph isomorphism using simple quantum circuits

• arxiv url: http://arxiv.org/abs/2610.19962v1
• Date: Wed, 14 Oct 2026 10:48:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.105937
• Title: Testing graph isomorphism using simple quantum circuits
• Title（参考訳）: 単純量子回路を用いたグラフ同型試験
• Abstract要約: 簡単なグラフ依存のInstantaneous Quantum Polynomial-time 回路が非同型グラフを識別できるかどうかを検討する。 ハミング重み分布は、数値計算されたエネルギーギャップがゼロとなる深さでのグラフ対を区別することができる。 IQP出力分布の正確なグラフ理論的特徴付けを$=/2$と$=/4$で導き出す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth $p=2$, this invariant numerically distinguishes all $10{,}486$ cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at $θ=π/2$ and $θ=π/4$. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.
• Abstract（参考訳）: グラフ同型問題は、2つのグラフが頂点の置換に等しいかどうかを問う。 その正確な計算複雑性は未解決のままであり、多項式時間アルゴリズムが存在するかどうかは不明である。 簡単なグラフ依存型瞬時量子多項式時間 (IQP) と量子近似最適化アルゴリズム (QAOA) が非同型グラフを識別できるかどうかを検討する。 まず、適切なIQPとQAOAの構成により、基礎となるグラフを多項式数を用いて再構成できることを示す。 QAOAエネルギーを用いた以前の研究に基づいて、ハミング重量分布は、数値計算されたエネルギーギャップがゼロとなる回路深さでのグラフ対を区別できることを示した。 次に、出力分布にZZ相関子の行列にグラフ不変量を適用する。 グラフスペクトルの特定の場合、QAOA 深さ $p=2$ で、この不変量は最大18頂点でテストされた10{,}486$のコスペクトル正則グラフ対を数値的に区別する。 IQP回路では、ハミング重みセクター内の確率乗法に基づくより微細な不変量を導入し、数値的に検証されたすべての非同型グラフ対を区別する。 最後に、IQP出力分布の正確なグラフ理論的特徴付けを$θ=π/2$および$θ=π/4$で導き出す。 これらの結果から, 簡単なグラフ依存量子回路は構造情報を符号化し, 一般グラフ同型に対して効率的に抽出できるかどうかを公開している。

関連論文リスト

• DiPhon: Diffusion on Graphons for Scalable Graph Generation [100.75398811422308]
  拡散モデルはグラフ生成の主要なパラダイムであり、分子設計のような領域に顕著な影響を与えている。 有限グラフ上のこれらのダイナミクスを模倣する離散化グラフレベルプロセスであるDiPhonを提案する。 我々は、DiPhonが連続グラノン過程によって引き起こされる限界分布の第一モーメントと正確に一致することを証明し、第二モーメントを閉形式差まで近似する。
  論文  参考訳（メタデータ） (2026-07-08T10:15:17Z)
• Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
  近似グラフ同型テストの量子クエリ複雑性について検討する。 入力グラフの積グラフ$(G,H)$に対するMNRS量子ウォーク探索に基づく量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-03T06:43:41Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  SWING: Space Walks for Implicit Network Graphsはグラフ上のグラフランダム特徴を含む計算アルゴリズムの新しいクラスである。 SWINGの詳細な解析を行い、様々なiグラフのクラスで徹底的な実験を行い、それを補完する。
  論文  参考訳（メタデータ） (2026-02-13T08:12:38Z)
• Multiparticle quantum walks for distinguishing hard graphs [0.0]
  特に、多粒子量子ウォークとよく知られた古典的なWLテストを比較する方法について考察する。 我々は、入力重畳状態を持つ k-QW が k-CFI グラフを区別することを示す理論的証明と実験結果を提供する。 さらに、局所的な入力状態を持つ k-1 QW が k-CFI グラフを区別することを示す。
  論文  参考訳（メタデータ） (2025-01-07T10:30:40Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
  量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。 量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
  論文  参考訳（メタデータ） (2023-02-13T22:09:02Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。 本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。 今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
  論文  参考訳（メタデータ） (2022-02-19T02:56:47Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• What do QAOA energies reveal about graphs? [2.0305676256390934]
  グラフ構造に対するQAOAエネルギーの依存を利用して、ランダムにあるいは司法的に選択されたパラメータをグラフについて学習する。 我々の発見の多くは、様々な制約の下で$U(G)$と解釈できる。
  論文  参考訳（メタデータ） (2019-12-27T18:37:30Z)

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

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