論文の概要: Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem

• arxiv url: http://arxiv.org/abs/2512.02940v1
• Date: Tue, 02 Dec 2025 17:04:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-03 21:04:45.976536
• Title: Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem
• Title（参考訳）: 最小頂点被覆問題に対するスケーラブル量子ウォークに基づくヒューリスティックス
• Authors: F. S. Luiz, A. K. F. Iwakami, D. H. Moraes, M. C. de Oliveira,
• Abstract要約: 連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。 この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。 我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a novel heuristic quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs). In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes, enabling the identification of highly influential vertices through their transition probabilities. To enhance stability and solution quality, we introduce a dynamic decoupling (``freezing'') mechanism that isolates vertices already selected for the cover, preventing their interference in subsequent iterations of the algorithm. The method employs a compact binary encoding, requiring only $\lceil \log_2 (V)\rceil$ qubits to represent a graph with $V$ vertices, resulting in an exponential reduction of quantum resources compared to conventional vertex-based encodings. We benchmark the proposed heuristic against exact solutions obtained via Mixed-Integer Linear Programming (MILP) and against established classical heuristics, including Simulated Annealing, FastVC, and the 2-Approximation algorithm, across Erdős--Rényi, Barabási--Albert and regular random graph ensembles. Our results demonstrate that the CTQW-based heuristic consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology, outperforming classical approaches in both heterogeneous and homogeneous structures. These findings indicate that continuous-time quantum walks, when combined with topology-independent decoupling strategies, provide a powerful paradigm for large-scale combinatorial optimization and complex network control, with potential applications spanning infrastructure resilience, epidemic containment, sensor network optimization, and biological systems analysis.
• Abstract（参考訳）: 連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しいヒューリスティック量子アルゴリズムを提案する。 この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化し、その遷移確率を通じて非常に影響力のある頂点の同定を可能にする。 安定性と解の質を高めるため,カバーに選択された頂点を分離する動的解離機構を導入し,アルゴリズムのその後の反復においてそれらの干渉を防止した。 この方法はコンパクトなバイナリエンコーディングを採用し、$V$頂点を持つグラフを表すために$\lceil \log_2 (V)\rceil$ qubitsのみを必要とする。 我々は、Mixed-Integer Linear Programming (MILP)による正確な解と、Simulated Annealing, FastVC, and the 2- Approximation algorithm(エルデシュ=レーニ、バラバシ=アルベルトおよび正規ランダムグラフアンサンブル)を含む確立された古典的ヒューリスティックに対して提案されたヒューリスティックをベンチマークする。 以上の結果から,CTQWに基づくヒューリスティックは優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著なロバスト性を示し,不均一構造と均質構造の両方において古典的アプローチよりも優れていた。 これらの結果から, 連続時間量子ウォークとトポロジ非依存のデカップリング戦略が組み合わさることで, 大規模組合せ最適化と複雑なネットワーク制御の強力なパラダイムが実現され, インフラストラクチャのレジリエンス, 疫病封じ込め, センサネットワーク最適化, 生物学的システム解析に応用できる可能性が示唆された。

関連論文リスト

• Quantum-Assisted Correlation Clustering [3.8448698053186843]
  この研究は、グラフベースの教師なし学習タスクである相関クラスタリングのためのハイブリッド量子古典的手法を導入する。 我々は、もともと連立構造生成のために設計された量子支援型解法GCS-Qを適用し、署名付きグラフにおけるクラスタ内合意を最大化する。 合成符号グラフと実世界のハイパースペクトル画像データに関する実証的な評価は、相関クラスタリングに適応すると、GCS-Qはロバスト性およびクラスタリング品質において古典的アルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2025-09-03T12:14:35Z)
• Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization [13.021238902084647]
  グラフニューラルネットワーク(GNN)のオーバースムース化は、異なるノード機能で崩壊を引き起こす。 SGPC (Sheaf GNNs with PAC-Bayes) は,セルラーシェーフメッセージパッシングと複数のメカニズムを組み合わせた統一アーキテクチャである。 9つのホモ親和性およびヘテロ親和性ベンチマークの実験により、SGPCは最先端スペクトルおよび層ベースGNNよりも優れた性能を示した。
  論文  参考訳（メタデータ） (2025-08-01T06:39:28Z)
• Quantum-Classical Hybrid Quantized Neural Network [8.382617481718643]
  本稿では、任意のアクティベーションと損失関数の使用を可能にする、量子化されたニューラルネットワークトレーニングのための新しい擬似バイナリ最適化(QBO)モデルを提案する。 我々はQCBO問題を直接解くために量子コンピューティングを利用するQCGD(Quantum Gradient Conditional Descent)アルゴリズムを用いる。
  論文  参考訳（メタデータ） (2025-06-23T02:12:36Z)
• Solving Zero-Sum Convex Markov Games [38.68653814645517]
  本研究では,Nash equilibria (NE) に独立手法を用いて,2プレーヤゼロサムゲーム (cMG) におけるグローバルコンバージェンスを初めて保証する。 NC-pおよび両側pPL条件下での一般的な制約付きmin-max問題に対処する。
  論文  参考訳（メタデータ） (2025-06-19T08:12:02Z)
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  本稿では,コンパクト部分多様体における分散最適化の問題について考察する。 エージェントが量子化変数を用いて変数を更新するアルゴリズムを提案する。 我々の知る限りでは、量子化の存在下で$mathcalO (1/K)$収束率を達成した最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2025-06-09T01:57:25Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  QAMA(Quantum Annealing Multi-Head Attention)は、エネルギーベースのハミルトン最適化問題として注目を集める新しいドロップイン演算子である。 この枠組みでは、トークン相互作用を二項二項項に符号化し、低エネルギー構成の探索に量子アニールを用いる。 経験的に、自然言語と視覚のベンチマークによる評価は、タスク全体にわたって、標準的なマルチヘッドの注意から少なくとも2.7ポイントの精度が低下していることを示している。
  論文  参考訳（メタデータ） (2025-04-15T11:29:09Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。 私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。 基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
  論文  参考訳（メタデータ） (2024-05-22T18:11:42Z)

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

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