論文の概要: Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks

• arxiv url: http://arxiv.org/abs/2607.27915v1
• Date: Thu, 30 Jul 2026 09:29:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.487139
• Title: Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks
• Title（参考訳）: 連続時間量子ウォークに基づく最小頂点被覆問題に対する反復量子アルゴリズム
• Abstract要約: 最小頂点被覆問題に対する制約保存型ハイブリッド量子古典グリードフレームワークを提案する。 このフレームワークは、射影されたパウリ-X項を使い、その和は実現可能な部分空間を保存し、その内部は、実現可能な被覆の層グラフの隣接行列として正確に作用する。 条件付きエネルギー戦略はテストされたインスタンスで最適に動作し、アルゴリズムの性能は正確な連続時間制限に近く維持されることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a constraint-preserving hybrid quantum-classical greedy framework for the minimum vertex cover problem, which extends directly to maximum independent set by bitwise complementation. The framework uses projected Pauli-X terms whose sum preserves the feasible subspace and acts within it exactly as the adjacency matrix of a layered graph of feasible covers. This graph is connected, so every feasible cover is linked to the configuration containing all vertices by a sequence of allowed single-vertex flips. Starting from this configuration, the corresponding continuous-time quantum walk propagates amplitude into layers containing progressively smaller covers. We rank vertices using either their marginal cover probabilities or the expected cover size obtained after fixing each candidate vertex in the cover, and use these rankings to guide recursive greedy reductions. Across several random-graph families, with walk times fixed using independent calibration ensembles, the quantum-informed algorithms achieve lower mean approximation ratios and solve a larger fraction of instances optimally than their corresponding classical greedy baselines. The conditioned-energy strategy performs best on the tested instances and retains algorithmic performance close to the exact continuous-time limit under low-depth Trotterisation. For bounded-degree graphs, each Trotter layer has circuit depth independent of system size, and the framework requires neither penalty terms nor variational training.
• Abstract（参考訳）: 本稿では,最小頂点被覆問題に対する制約保存型ハイブリッド量子古典グリードフレームワークを提案する。 このフレームワークは、射影されたパウリ-X項を使い、その和は実現可能な部分空間を保存し、その内部は、実現可能な被覆の層グラフの隣接行列として正確に作用する。 このグラフは連結であるため、すべての実現可能な被覆は、許容される単頂点フリップの列によって全ての頂点を含む構成にリンクされる。 この構成から始まり、対応する連続時間量子ウォークは振幅を徐々に小さいカバーを含む層に伝播させる。 本研究は,各候補頂点の固定後に得られた限界被覆確率と予測被覆サイズを用いて頂点をランク付けし,これらのランキングを用いて再帰性欲求低下を導出する。 独立キャリブレーションアンサンブルを用いてウォークタイムを固定したランダムグラフ系では、量子インフォームドアルゴリズムは平均近似比を低くし、対応する古典的なグリードベースラインよりも広い数のインスタンスを最適に解決する。 条件付きエネルギー戦略は、テストインスタンス上で最善を尽くし、低深度トロッタライゼーションの下での正確な連続時間限界に近いアルゴリズム性能を維持する。 有界グラフの場合、各トロッター層はシステムサイズに依存しない回路深度を持ち、フレームワークはペナルティ条件も変分訓練も必要としない。

関連論文リスト

• Quantum Optimisation for Protein-Protein Interaction Network Alignment [0.4763980315619087]
  タンパク質-タンパク質相互作用(PPI)ネットワークアライメントは、トポロジカル情報とシーケンス情報を組み合わせて、種間で保存されたモジュールを識別する。 我々は、アライメントを重み付き最大共通誘導部分グラフ問題としてモデル化し、モジュラー積グラフを通してそれを再構成する。 カーネル化,ブランチ・アンド・バウンド,および7つの量子近似最適化アルゴリズムを組み合わせたハイブリッドフレームワークを開発した。
  論文  参考訳（メタデータ） (2026-09-04T15:04:55Z)
• Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA [3.7768601360100647]
  仮定から強制可能な性質へ分割性を変換する適応分解フレームワークであるFrozenLGPを紹介する。 FrozenLGPは、高結合性インスタンス上での標準分割およびコンカヤベースラインの4.6%と比較して100%の分解カバレッジを実現している。
  論文  参考訳（メタデータ） (2026-07-09T06:19:12Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。 この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。 我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2025-12-02T17:04:57Z)
• Finite-Time Information-Theoretic Bounds in Queueing Control [54.11376591632282]
  本稿では, 待ち行列の待ち行列を, 待ち行列と待ち行列の双方で処理するネットワーク上のスケジューリング問題において, 待ち行列の総長を求める新しいポリシーを導出する。 これらの結果は「ドリフトオンリー」な手法の基本的な制限を明らかにし、待ち行列制御における原則的、非漸近的最適性への道を示す。
  論文  参考訳（メタデータ） (2025-06-23T04:14:40Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization [6.48447388642063]
  ノード連続体を持つグラフオン上での分散最適化問題について検討する。 グラノン上での勾配降下と勾配追従アルゴリズムを提案する。 時間変化アルゴリズムを適切に選択することにより、すべてのノードの状態が接続されたグラフに対して$mathcalLinfty$-consensusを達成することを示す。
  論文  参考訳（メタデータ） (2024-07-03T02:47:39Z)
• Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models [0.0]
  非一様ハイパーグラフブロックモデル(HSBM)の下でのランダムハイパーグラフの教師なし分類問題 本稿では,クラスタリング精度と強い一貫性しきい値に対する情報理論の限界を確立する。
  論文  参考訳（メタデータ） (2023-06-12T03:38:25Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)

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

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