論文の概要: Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained Problems

• arxiv url: http://arxiv.org/abs/2310.04542v1
• Date: Fri, 6 Oct 2023 19:09:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-12 17:50:43.140649
• Title: Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained Problems
• Title（参考訳）: 量子最適化:制約問題の解法におけるラグランジアン双対QUBO
• Authors: Einar Gabbassov, Gili Rosenberg, Artur Scherer
• Abstract要約: 本稿では,ラグランジアン双対性の概念を離散化された断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。 回路モデル-フォールトトレラント量子計算の設定において,本手法が回路深さの2次改善を実現し,制約に依存しない回路幅を維持できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of discretized adiabatic quantum computation (DAQC). Within the setting of circuit-model fault-tolerant quantum computation, we present numerical evidence that our approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width, in contrast to the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) formalism. Our study includes a detailed analysis of the limitations and challenges encountered when using QUBO for constrained optimization in both classical and quantum contexts. While the focus of the present study is deep quantum circuits allowing pre-tuned adiabatic schedules, our proposed methodology is also directly applicable to variational algorithms suitable for implementations on noisy intermediate-scale quantum (NISQ) devices, such as the quantum approximate optimization algorithm (QAOA). Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete 0-1 knapsack problem.
• Abstract（参考訳）: 本稿では, 離散化断熱量子計算(DAQC)の枠組みにラグランジアン双対性の概念を組み込んだ制約付き組合せ最適化問題の解法を提案する。 回路モデル-フォールトトレラント量子計算の設定において,2次非拘束二元最適化(QUBO)の形式に基づくリフォームによる制約問題の解法とは対照的に,回路深さの2次改善を実現し,制約非依存の回路幅を維持するという数値的証拠を示す。 本研究は、quboを用いた古典的および量子的文脈における制約付き最適化の限界と課題の詳細な分析を含む。 本研究の焦点は、事前調整された断熱スケジュールを実現するディープ量子回路であるが、提案手法は、量子近似アルゴリズム(QAOA)のようなノイズの多い中間規模量子(NISQ)デバイスの実装に適した変分アルゴリズムにも直接適用可能である。 NP完全0-1knapsack問題を用いて,QUBO法に対するラグランジアン双対アプローチのベンチマークを行った。

関連論文リスト

• Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems [0.4915744683251151]
  不等式制約は、統計力学により、同様の目的関数に緩和できることを示す。 本研究では, 典型的な不等式制約付き最適化問題である2次クナップサック問題において, この手法の性能を評価する。
  論文  参考訳（メタデータ） (2024-11-11T11:59:50Z)
• Two-Step QAOA: Enhancing Quantum Optimization by Decomposing One-Hot Constraints in QUBO Formulations [0.0]
  本稿では,QAOAの有効性を向上させるための簡単なアプローチであるTwo-Step QAOAを提案する。 問題を2段階に分けて,ソフト制約をハード制約に変換する。
  論文  参考訳（メタデータ） (2024-08-09T23:38:28Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。 これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
  論文  参考訳（メタデータ） (2023-05-14T03:49:10Z)
• Quantum annealing with inequality constraints: the set cover problem [0.0]
  本稿では,複数の不等式制約を持つ集合被覆問題を量子アニール上で解くための2つの新しい手法を提案する。 第1の方法は拡張ラグランジアン法を用いて制約を表現し、第2の方法は高階バイナリ最適化(HUBO)を用いる。 どちらのアプローチも、D-Wave量子アニールの不等式制約の問題を解くために、スラック変数で標準的なアプローチより優れている。
  論文  参考訳（メタデータ） (2023-02-22T07:39:51Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  本稿では,2次最適化問題に対する現行手法の適用性を高めるために,分解に基づくアプローチを提案する。 我々は、乗算器の交互方向法(ADMM)が、MBOを二項制約のない問題(量子アルゴリズムで解ける)に分割できることを示した。 提案手法の有効性は,Qiskit で実装された量子回路上での VQE と QAOA を用いたシミュレーションにより,いくつかの最適化問題に対して得られた数値結果によって示される。
  論文  参考訳（メタデータ） (2020-01-07T14:43:13Z)

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

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