論文の概要: Resource-Aware Grover Search for Minimum Vertex Cover
- arxiv url: http://arxiv.org/abs/2610.07252v1
- Date: Mon, 05 Oct 2026 18:50:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 02:58:29.605229
- Title: Resource-Aware Grover Search for Minimum Vertex Cover
- Title（参考訳）: 最小頂点被覆のための資源を考慮したグローバー探索
- Abstract要約: Groverのアルゴリズムは、非構造化検索のためのクエリの複雑さを2次的に低減する。
既存のGroverベースのMVCの定式化は、かなりの量子リソースオーバーヘッドを引き起こす可能性がある。
我々は、量子ビット数、回路深さ、ゲートの複雑さを低減するために、いくつかの符号化およびオラクル設計戦略を開発し、評価する。
- 参考スコア（独自算出の注目度）: 42.07426424778508
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network analysis and resource allocation. Grover's algorithm provides a quadratic reduction in query complexity for unstructured search, but existing Grover-based MVC formulations can incur substantial quantum resource overhead due to costly vertex-counting circuits and complex oracle constructions. We develop and evaluate several encoding and oracle-design strategies for reducing the qubit count, circuit depth, and gate complexity of Grover-based MVC search. First, we construct a Dicke-Parallel formulation that restricts the search to fixed-cardinality subsets, eliminating explicit vertex counting, together with a parallel edge-verification oracle that reduces feasibility-checking overhead. We then develop an Edge-Counting formulation that replaces per-edge auxiliary storage with a logarithmic-size counting register, substantially reducing ancillary-qubit requirements. Finally, we propose an Edge-Centric encoding that represents endpoint selections directly and derives vertex-selection states through incident-edge Boolean operations, enabling more depth-efficient oracle construction. Our resource analysis reveals complementary trade-offs among qubit width, circuit depth, gate count, and Grover iteration count. Edge-Counting is particularly attractive under tight qubit constraints, while Edge-Centric can reduce both circuit depth and Grover iteration count when the graph has a moderate edge count and sufficient representation multiplicity. Dicke-Parallel provides a more robust choice when such multiplicity is limited or graph density makes the edge-based search space large. These results provide practical guidance for selecting Grover-based MVC formulations according to hardware constraints and graph structure.
- Abstract（参考訳）: Minimum Vertex Cover (MVC) 問題は、ネットワーク分析やリソース割り当ての応用における基本的なNPハード組合せ最適化問題である。
グローバーのアルゴリズムは、構造化されていない検索に対してクエリの複雑さを2次に減らすが、既存のGroverベースのMVCの定式化は、高価な頂点カウント回路と複雑なオラクル構造のために、かなりの量子リソースオーバーヘッドを引き起こす可能性がある。
我々は、GroverベースのMVCサーチにおいて、キュービット数、回路深さ、ゲートの複雑さを低減させるいくつかの符号化およびオラクル設計戦略を開発し、評価する。
第一にDicke-Parallel の定性部分集合への探索を制限し、明示的な頂点カウントを排除し、実現可能性チェックのオーバーヘッドを低減する並列エッジ検証オラクルを構築する。
次に,エッジ・カウンティング(Edge-Counting)という,エッジ・カウンティング(Edge-Counting)の定式化を行い,各エッジ・ストレージを対数サイズカウントレジスタに置き換えた。
最後に、エンドポイント選択を直接表現し、インシデントエッジブール演算により頂点選択状態を導出し、より深度効率の良いオラクル構築を可能にするエッジ中心符号化を提案する。
資源分析により,キュービット幅,回路深さ,ゲート数,Grover反復数間の相補的トレードオフが明らかになった。
一方Edge-Centricは、グラフが適度なエッジ数と十分な表現多重度を持つ場合、回路深さとGrover繰り返し数を削減できる。
Dicke-Parallel は、そのような多重度が制限されている場合やグラフ密度がエッジベースの探索空間を大きくする場合、より堅牢な選択を提供する。
これらの結果は、ハードウェアの制約やグラフ構造に応じてGroverベースのMVCの定式化を選択するための実用的なガイダンスを提供する。
関連論文リスト
- GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
GONDORはGreedy Best-First Search(GBFS)の拡張である
GONDORは、アンカー状態のスパースセットを保持しながら周期的に探索木を圧縮し、ゴールに達するとスパース状態間の再探索によって経路を再構築する。
実験により、GONDORは標準のGBFSと比較して、低メモリ予算下でのカバレッジを一貫して改善することが示された。
論文 参考訳（メタデータ） (2026-05-27T13:20:58Z) - Reducing Circuit Resources in Grover's Algorithm via Constraint-Aware Initialization [3.7738353997936973]
Groverの検索アルゴリズムは、クエリの複雑さの観点から、古典的なブルートフォースサーチよりも2次的なスピードアップを提供する。
本稿では,Groverのアルゴリズムで制約認識を初期化するための単純な前処理手順を用いた体系的フレームワークを提案する。
提案手法は,Groverのアルゴリズムのより資源効率の高い実装を実現するための実践的ベースラインとして機能することが示唆された。
論文 参考訳（メタデータ） (2026-01-25T07:31:06Z) - A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search [0.0]
本稿では、パスフィニングタスクを構造化探索問題としてキャストすることで、完璧な迷路を解くための量子アルゴリズムを提案する。
グロバーの振幅増幅に基づいて、アルゴリズムは重ね合わせ中の全ての候補経路を符号化し、その目標に近接することを評価する。
グロバー互換のオラクルは、高い適合状態を示し、適応的なカットオフ戦略は、探索を反復的に洗練する。
論文 参考訳（メタデータ） (2025-07-29T15:51:19Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Decision Diagram-Based Branch-and-Bound with Caching for Dominance and
Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。
鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。
このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文 参考訳（メタデータ） (2022-11-22T10:18:33Z) - Improved Acyclicity Reasoning for Bayesian Network Structure Learning
with Constraint Programming [0.0]
離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。
本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。
最適ではないにもかかわらず、性能は桁違いに向上することを示す。
結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
論文 参考訳（メタデータ） (2021-06-23T09:46:11Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳（メタデータ） (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。