論文の概要: Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
- arxiv url: http://arxiv.org/abs/2509.01261v1
- Date: Mon, 01 Sep 2025 08:50:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 15:17:03.610181
- Title: Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
- Title（参考訳）: 実時間グローバルサイズ追跡によるグローバーアルゴリズムによる最適斜め検出
- Authors: Wenmin Han, Shiqi Zheng, Peian Chen, Yukun Wang,
- Abstract要約: 最大傾き問題(MCP)は、無向グラフにおいて最大の完全部分グラフを見つけることである。
これは、バイオインフォマティクス、ソーシャルネットワーク、データマイニング、その他の分野を含む幅広い応用におけるNP-Hard問題である。
本稿では,最大傾きサイズを動的に追跡する改良アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.528817049577178
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an improved algorithm that dynamically tracks the maximum clique size by encoding prior constraints on the vertex count-derived from Tur\'an's theorem and complete graph properties-into global variables through quantum circuit pre-detection. The algorithm further synergizes with Grover's search to optimize the solution space. Our auxiliary-qubit encoding scheme dynamically tracks clique sizes during quantum search, eliminating iterative measurements, achieving MCP solution with $O\left(\sqrt{2^n}\right)$ Grover iterations and $O(1)$ measurements. This represents an $\boldsymbol{n}$-fold improvement over state-of-the-art Grover-based methods, which require $O(n\sqrt{2^n})$ iterations and $O(n)$ measurements for $n$-vertex graphs. We validate algorithmic correctness through simulations on IBM's Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
- Abstract（参考訳）: 最大傾き問題(MCP)は、無向グラフにおいて最大の完全部分グラフを見つけることであり、すなわち、2つの異なる頂点の間にエッジが存在する部分グラフである。
これは、バイオインフォマティクス、ソーシャルネットワーク、データマイニング、その他の分野を含む幅広い応用におけるNP-Hard問題である。
本稿では,Tur\'anの定理から導かれる頂点数と,量子回路前検出による大域変数への完全グラフ特性の事前制約を符号化することにより,最大傾きサイズを動的に追跡するアルゴリズムを提案する。
このアルゴリズムは、解空間を最適化するために、Groverの探索とさらに相乗化する。
我々の補助量子ビット符号化方式は、量子探索中のクリッドサイズを動的に追跡し、反復的な測定を排除し、$O\left(\sqrt{2^n}\right)$ Grover 反復と$O(1)$測定で MCP ソリューションを実現する。
これは、$O(n\sqrt{2^n})$イテレーションと$O(n)$測定の$n$頂点グラフを必要とする、最先端のGroverベースのメソッドに対する$\boldsymbol{n}$-foldの改善を表す。
我々は,IBM の Qiskit プラットフォーム上でのシミュレーションと,既存の Grover ベースの MCP ソルバに対する qubit/gate 効率のベンチマークにより,アルゴリズムの正当性を検証した。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
二部グラフ解析において、$s$-ビスプレックスの列挙は基本的な問題である。
実世界のデータエンジニアリングでは、すべての$sビプレックスを見つけることは必要でも、計算的にも安価でもない。
単純な2n列挙アルゴリズムを破るMVBPを提案する。
FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。
論文 参考訳（メタデータ） (2024-09-27T06:23:29Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。