論文の概要: SCOOP: A Scalable Quantum-Computing Framework to Constrained Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2504.10897v1
- Date: Tue, 15 Apr 2025 06:17:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-16 22:09:19.469192
- Title: SCOOP: A Scalable Quantum-Computing Framework to Constrained Combinatorial Optimization
- Title（参考訳）: SCOOP: 制約付き組合せ最適化のためのスケーラブルな量子計算フレームワーク
- Authors: Prashanti Priya Angara, Emily Martins, Ulrike Stege, Hausi Müller,
- Abstract要約: 本稿では,制約付き最適化問題を解くための新しいフレームワークSCOOPを提案する。
SCOOPは制約付き問題を制約なしのものに変換し、SCOOP問題ツインを形成する。
本稿では,3つのNP-hard問題,最小支配集合,最小最大マッチング,最小集合被覆の枠組みを実証する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: While the ultimate goal of solving computationally intractable problems is to find a provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a state-of-the-art hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. The QAOA quantum algorithm operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the framework on three NP-hard problems, Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover appearing in practical application domains such as resource allocation, communication networks, and machine learning. We validate SCOOP's feasibility and effectiveness on Xanadu PennyLane simulators.
- Abstract（参考訳）: 計算的に難解な問題の究極的な目標は、証明可能な最適解を見つけることであるが、現実のシナリオの実践的な制約は、しばしば、高品質でほぼ最適な解を効率的に得ることに集中する必要がある。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、2次および高次非制約バイナリ最適化問題(QUBOとHUBO)を用いて符号化された、これらの課題に対処するための最先端のハイブリッド量子古典的手法である。
本稿では,制約付き最適化問題を解くための新しいQAOAベースのフレームワークSCOOPを提案する。
SCOOPは制約付き問題を制約なしのものに変換し、SCOOP問題ツインを形成する。
QAOA量子アルゴリズムは、最適解と準最適解を特定するために、制約のない双対で動作する。
効率的な古典的後処理は、制約された問題空間に設定された解を減少させる。
私たちのSCOOPアプローチは、ソリューション強化、客観的機能互換、スケーラブルです。
本稿では,資源割り当て,通信ネットワーク,機械学習などの実用的なアプリケーション領域に現れる,最小支配セット,最小最大マッチング,最小設定カバーという3つのNPハード問題に関するフレームワークを実証する。
Xanadu PennyLaneシミュレータにおけるSCOOPの有効性と有効性を検証する。
関連論文リスト
- 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) - A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。
2つのよく知られた実世界のアプリケーションでその効果を実証する。
論文 参考訳（メタデータ） (2024-06-14T15:59:36Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳（メタデータ） (2023-02-08T17:09:20Z) - Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
現在の量子最適化アルゴリズムでは、元の問題を二進最適化問題として表現し、量子デバイスに適した等価コストハミルトニアンに変換する必要がある。
目的関数を計算し、制約を認証するための古典的プログラムを設計し、後に量子回路にコンパイルする。
我々は、このアイデアをトラベリングセールスマン問題やMax-K$-Cutといった最適化タスクに活用し、関連するすべてのコスト対策に関して最適に近い回路を得る。
論文 参考訳（メタデータ） (2022-09-07T18:01:01Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Classically-Boosted Quantum Optimization Algorithm [0.0]
我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。
具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。
CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
論文 参考訳（メタデータ） (2022-03-25T23:36:14Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳（メタデータ） (2021-01-19T19:00:40Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。