論文の概要: An Exclusive-Sum-of-Products Pipeline for QAOA

• arxiv url: http://arxiv.org/abs/2508.21686v1
• Date: Fri, 29 Aug 2025 14:53:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-01 19:45:11.086715
• Title: An Exclusive-Sum-of-Products Pipeline for QAOA
• Title（参考訳）: QAOAのための排他的生産パイプライン
• Authors: Matthew Brunet, Shilpi Shah, Mostafa Atallah, Anthony Wilkie, Rebekah Herrman,
• Abstract要約: 量子近似最適化アルゴリズムは、最適化問題の解法として一般的に用いられる。 制約のない問題は自然にアルゴリズムにマップされるが、制約は通常、目的関数の制約違反を罰することを必要とする。 ペナル化前の排他的製品形態のブール式として制約を符号化する代替手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm is commonly used to solve combinatorial optimization problems. While unconstrained problems map naturally into the algorithm, incorporating constraints typically requires penalizing constraint violations in the objective function. In this work, we propose an alternative approach that encodes constraints as Boolean expressions in exclusive-sum-of-products (ESOP) form before penalization. We test this method on the maximum independent set problem using graphs with 3 to 20 vertices and find that ESOP constraint formulations achieve higher approximation ratios than standard constraint penalization methods, with percent increases of up to 30.3%. Furthermore, ESOP constraint formulations result in higher approximation ratios than standard QAOA penalization approaches after one layer of the algorithm on approximately 64% of the tested graphs.
• Abstract（参考訳）: 量子近似最適化アルゴリズムは、組合せ最適化問題の解法として一般的に用いられる。 制約のない問題は自然にアルゴリズムにマップされるが、制約を組み込むには、通常、目的関数の制約違反を罰することが必要である。 本研究では,排他的生成物(ESOP)形式におけるブール式として制約をエンコードする代替手法を提案する。 本研究では, 3 から 20 個の頂点を持つグラフを用いて, 最大独立集合問題に対して検証を行い, ESOP 制約の定式化が標準制約のペナライズ法よりも高い近似比を達成し, 最大30.3% まで上昇することを示した。 さらに、ESOP制約の定式化は、テストグラフの約64%上のアルゴリズムの1層後の標準QAOAのペナル化アプローチよりも高い近似比をもたらす。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
  変分量子アルゴリズム(VQA)は、通常、ペナルティ法を用いて制約のない問題として再構成されるように制約付き問題を要求する。 一般的なアプローチでは、不等式制約を扱うためにQUBOの定式化においてスラック変数と二次罰則を導入する。 我々は、カスタムペナルティ関数を使って不等式制約を直接エンコードするスラックフリーな定式化について検討する。 これらのステップのような罰則は、追加の量子ビットを導入するか、微調整された重みを必要とすることなく、実現不可能な解を抑える。
  論文  参考訳（メタデータ） (2025-04-17T03:20:02Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  本稿では、等価な制約のない問題の単一最小化により、煩雑な制約付きポリシー反復を解決するP3Oを提案する。 P3Oは、コスト制約を排除し、クリップされたサロゲート目的による信頼領域制約を除去するために、単純なyet効果のペナルティ関数を利用する。 P3Oは,一連の制約された機関車作業において,報酬改善と制約満足度の両方に関して,最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-24T06:15:51Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization [13.170519806372075]
  2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。 最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。 提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
  論文  参考訳（メタデータ） (2021-07-14T08:01:30Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。 本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
  論文  参考訳（メタデータ） (2021-01-25T01:49:10Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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