論文の概要: The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA
- arxiv url: http://arxiv.org/abs/2503.10077v2
- Date: Sun, 16 Mar 2025 19:30:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-18 12:36:22.796278
- Title: The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA
- Title（参考訳）: 制約回避技術:QAOAによる制約付き組合せ最適化へのペナルティフリーアプローチ
- Authors: Prashanti Priya Angara, Danylo Lykov, Ulrike Stege, Yuri Alexeev, Hausi Müller,
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、2次(および高次)非制約二項最適化問題の最適解とほぼ最適解を決定するために設計されている。
制約付き最適化問題を解くために、革新的な利益緩和フレームワークを導入します。
- 参考スコア（独自算出の注目度）: 0.3774866290142281
- License:
- Abstract: The quantum approximate optimization algorithm (QAOA) is designed to determine optimum and near optimum solutions of quadratic (and higher order) unconstrained binary optimization (QUBO or HUBO) problems, which in turn accurately model unconstrained combinatorial optimization problems. While the solution space of an unconstrained combinatorial optimization problem consists of all possible combinations of the objective function's decision variables, for a constrained combinatorial optimization problem, the solution space consists only of solutions that satisfy the problem constraints. While solving such a QUBO problem optimally results in an optimal solution to the underlying constrained problem, setting the right penalty parameters is crucial. Moreover, finding suitable penalties that ensure near-optimal solutions is also challenging. In this article, we introduce our innovative profit-relaxation framework to solve constrained combinatorial optimization problems. Our effective hybrid approach transforms a selected constrained combinatorial optimization problem into an unconstrained profit problem, such that the solution spaces of the two problems are interrelated with respect to their solution qualities. This allows us to determine optimal and near-optimal solutions for the constrained problem. We use three NP-hard problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- to demonstrate the feasibility and effectiveness of our approach. We conducted a detailed performance evaluation of our profit-relaxation framework on two different platforms: Xanadu PennyLane and Argonne QTensor Quantum Circuit Simulator.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、2次(高次)非制約二元最適化(QUBOまたはHUBO)問題の最適解とほぼ最適解を決定するために設計され、非制約の組合せ最適化問題を正確にモデル化する。
制約のない組合せ最適化問題の解空間は、対象関数の決定変数の可能なすべての組み合わせからなるが、制約された組合せ最適化問題に対しては、解空間は問題の制約を満たす解のみからなる。
このようなQUBO問題の解決は、根底にある制約問題に対する最適解をもたらすが、適切なペナルティパラメータの設定は不可欠である。
さらに, 準最適解を確実にする適切な罰則の発見も困難である。
本稿では,制約付き組合せ最適化問題を解くための革新的な収益緩和フレームワークを紹介する。
我々の効果的なハイブリッドアプローチは、選択された制約付き組合せ最適化問題を、その解空間が解の質に関して相互に関係しているような、制約のない利益問題に変換する。
これにより、制約された問題に対する最適解と準最適解を決定できる。
我々は,最小頂点被覆,最大独立集合,最大傾きの3つのNPハード問題を用いて,本手法の有効性と有効性を示す。
我々は、Xanadu PennyLaneとArgonne QTensor Quantum Circuit Simulatorの2つの異なるプラットフォーム上で、利益緩和フレームワークの詳細な性能評価を行った。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Two-Step QAOA: Enhancing Quantum Optimization by Decomposing K-hot Constraints in QUBO Formulations [0.0]
Two-Step QAOAは、k-hotエンコーディングQUBO定式化の問題を分解することで、QAOAの有効性を向上させることを目的としている。
ソフト制約をハード制約に変換し、初期条件の生成を単純化する。
論文 参考訳（メタデータ） (2024-08-09T23:38:28Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳（メタデータ） (2023-02-08T17:09:20Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Constraint Programming to Discover One-Flip Local Optima of Quadratic
Unconstrained Binary Optimization Problems [0.5439020425819]
qubo annealersや他のソリューションアプローチは、局所的な最適性を持つ多様なソリューションセットから始めることができる。
本稿では,制約プログラミングを活用した1フリップ局所オプティマの集合を生成する新しい手法を提案する。
論文 参考訳（メタデータ） (2021-04-04T22:55:25Z) - Combining Reinforcement Learning and Constraint Programming for
Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。
深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。
制約プログラミング(CP)は最適化問題を解決する汎用ツールである。
本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2020-06-02T13:54:27Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Quantum approximate algorithm for NP optimization problems with
constraints [12.294570891467604]
本稿では,異なる制約型を等式,線形不等式,任意の形式に定式化する。
そこで本研究では,NP最適化問題の解法としてQAOAフレームワークに適合する制約符号化方式を提案する。
提案手法の有効性と有効性を示す。
論文 参考訳（メタデータ） (2020-02-01T04:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。