論文の概要: A Quantum Genetic Algorithm Framework for the MaxCut Problem

• arxiv url: http://arxiv.org/abs/2501.01058v1
• Date: Thu, 02 Jan 2025 05:06:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:11:58.604842
• Title: A Quantum Genetic Algorithm Framework for the MaxCut Problem
• Title（参考訳）: MaxCut問題のための量子遺伝的アルゴリズムフレームワーク
• Authors: Paulo A. Viana, Fernando M. de Paula Neto,
• Abstract要約: 提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
• 参考スコア（独自算出の注目度）: 49.59986385400411
• License:
• Abstract: The MaxCut problem is a fundamental problem in Combinatorial Optimization, with significant implications across diverse domains such as logistics, network design, and statistical physics. The algorithm represents innovative approaches that balance theoretical rigor with practical scalability. The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles. By partitioning graphs into manageable subgraphs, optimizing each independently, and applying graph contraction to merge the solutions, the method exploits the inherent binary symmetry of MaxCut to ensure computational efficiency and robust approximation performance. Theoretical analysis establishes a foundation for the efficiency of the algorithm, while empirical evaluations provide quantitative evidence of its effectiveness. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach, which provides up to 99.7\% of the optimal solution for larger graphs. On Erd\H{o}s-R\'{e}nyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96\% of the SDP results. These results showcase the potential of the QGA framework to deliver competitive solutions, even under heuristic constraints, while demonstrating its promise for scalability as quantum hardware evolves.
• Abstract（参考訳）: MaxCut問題(英語版)は組合せ最適化の基本的な問題であり、ロジスティクス、ネットワーク設計、統計物理学など様々な分野に重大な影響を及ぼす。 このアルゴリズムは、理論的な厳密さと実用的なスケーラビリティのバランスをとる革新的なアプローチを表している。 提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 グラフを管理可能な部分グラフに分割し、それぞれを独立に最適化し、解をマージするためにグラフ収縮を適用することにより、計算効率とロバスト近似性能を確保するためにMaxCutの固有二項対称性を利用する。 理論的解析はアルゴリズムの効率の基盤を確立し、実証的な評価はその効果の定量的な証拠を提供する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、より大規模なグラフに対して最適な解の99.7 %を提供する半有限計画法(SDP)よりも優れている。 Erd\H{o}s-R\'{e}nyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96\%以内の中央値の解を達成する。 これらの結果は、量子ハードウェアが進化するにつれてスケーラビリティが約束される一方で、ヒューリスティックな制約の下でも、競争力のあるソリューションを提供するためのQGAフレームワークの可能性を示している。

関連論文リスト

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Qudit-inspired optimization for graph coloring [0.0]
  グラフ色問題(GCP)に対する量子インスピレーションアルゴリズムを提案する。 我々は、グラフ内のノードを表現し、d次元球面座標でパラメータ化した各キューディットを積状態に使用する。 我々は,2つの最適化戦略をベンチマークする: 傾き勾配降下, ランダム状態の立方体開始, コスト関数の最小化のために勾配勾配勾配を用いる。
  論文  参考訳（メタデータ） (2024-06-02T16:19:55Z)
• Quantum Graph Optimization Algorithm [7.788671046805509]
  本研究では,メッセージパス機構を統合した新しい変分量子グラフ最適化アルゴリズムを提案する。 QUBOタスクのスケーラビリティに関して,本アルゴリズムはQAOAよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2024-04-09T16:25:07Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。 我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。 本研究は,本手法の有効性と応用の可能性を示すものである。
  論文  参考訳（メタデータ） (2022-03-29T05:44:07Z)
• Quantum variational optimization: The role of entanglement and problem hardness [0.0]
  本稿では, 絡み合いの役割, 変動量子回路の構造, 最適化問題の構造について検討する。 数値計算の結果,絡み合うゲートの分布を問題のトポロジに適応させる利点が示唆された。 リスク型コスト関数に条件値を適用することで最適化が向上し、最適解と重複する確率が増大することを示す。
  論文  参考訳（メタデータ） (2021-03-26T14:06:54Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)

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

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