論文の概要: Quantum search algorithm for similar subgraph identification under fixed edge removal

• arxiv url: http://arxiv.org/abs/2604.02027v1
• Date: Thu, 02 Apr 2026 13:34:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.817216
• Title: Quantum search algorithm for similar subgraph identification under fixed edge removal
• Title（参考訳）: 固定エッジ除去における類似部分グラフ同定のための量子探索アルゴリズム
• Authors: Ruben Kara, Sven Danz, Tobias Stollenwerk, Andrea Benigni,
• Abstract要約: ラプラシアン $boldsymbolB'$ の重み付き参照グラフが与えられた場合、このアルゴリズムは同じ集合上のラプラシアン $boldsymbolB'$ を特徴付ける部分グラフを決定する。 本稿では,電力グリッドを表す標準的なテストケースに対する本手法の適用例を示す。
• 参考スコア（独自算出の注目度）: 2.1098915638533446
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a novel quantum algorithm for similar subgraph identification in form of an NP-hard cardinality-constrained binary quadratic optimization problem. Given a weighted reference graph with Laplacian $\boldsymbol{B}$, our algorithm determines the subgraph featuring Laplacian $\boldsymbol{B'}$ on the same vertex set, but $x$ out of $N$ inactive edges, minimizing the Frobenius distance $||\boldsymbol{B} - \boldsymbol{B'}||_\mathrm{F}^2$. We represent the $\binom{N}{x}$ graph topologies by an equal-weight superposition in form of a Dicke state, enabling controlled transformations applied to the quantum state associated with the vectorized Laplacian of the reference graph. Combined with amplitude estimation and a minimum finding approach, our algorithm provides a polynomial speed up $\mathcal{O}(\sqrt{N^{x}/x!}N\log\log N)$ compared to $\mathcal{O}(N^{x+1}/x!)$ of classical brute-force search algorithms. We demonstrate the application of our method on standard test cases, which represent electric power grids, by reconstructing $||\boldsymbol{B} -\boldsymbol{B'}||_\mathrm{F}^2$ from measurements and show how our approach can be additionally used to calculate energy functional like quadratic forms of the Laplacians with respect to a given vector.
• Abstract（参考訳）: そこで本研究では,NP硬度制約二項二乗最適化問題を用いて,類似部分グラフ同定のための新しい量子アルゴリズムを提案する。 ラプラシアン $\boldsymbol{B}$ の重み付き参照グラフが与えられたとき、我々のアルゴリズムは、同じ頂点集合上のラプラシアン $\boldsymbol{B'}$ を含む部分グラフを決定するが、$N$不活性エッジの$x$は、フロベニウス距離 $|\boldsymbol{B} - \boldsymbol{B'}|||_\mathrm{F}^2$ を最小化する。 我々は、Dicke状態の形で等重重ね合わせにより$\binom{N}{x}$グラフトポロジーを表現し、参照グラフのベクトル化されたラプラシアンの量子状態に適用される制御変換を可能にする。 振幅推定と最小探索法を組み合わせることで、このアルゴリズムは$\mathcal{O}(\sqrt{N^{x}/x! }N\log\log N)$を$\mathcal{O}(N^{x+1}/x!)$と比較する。 実測値から $||\boldsymbol{B} -\boldsymbol{B'}||_\mathrm{F}^2$ を再構成することにより、電力グリッドを表す標準的なテストケースに適用し、与えられたベクトルに関してラプラシアンの二次形式のようなエネルギー関数の計算に、我々のアプローチをどのように利用できるかを示す。

関連論文リスト

• Dequantization and Hardness of Spectral Sum Estimation [1.0323063834827415]
  対数行列式などの行列のスペクトル和を推定するための新しい定式化と硬度結果を与える。 古典的な上界を$mathsfDQC1$-completenessで補い、特定のスペクトル和を推定する。
  論文  参考訳（メタデータ） (2025-09-24T14:44:53Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• A framework for optimal quantum spatial search using alternating phase-walks [0.0]
  我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。 様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
  論文  参考訳（メタデータ） (2021-09-29T11:16:52Z)
• Improved approximation algorithms for bounded-degree local Hamiltonians [12.961180148172197]
  与えられた積状態によって達成される近似比を改善するために使用できる浅量子回路群について述べる。 結果は、$k$-local Hamiltonianと絡み合った初期状態に拡張します。
  論文  参考訳（メタデータ） (2021-05-03T22:23:47Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)

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

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