論文の概要: IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization

• arxiv url: http://arxiv.org/abs/2504.08663v1
• Date: Fri, 11 Apr 2025 16:12:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 14:18:22.892761
• Title: IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Title（参考訳）: IF-QAOA:制約量子最適化の高速化のためのペナルティフリーアプローチ
• Authors: David Bucher, Jonas Stein, Sebastian Feld, Claudia Linnhoff-Popien,
• Abstract要約: 本稿では、量子近似最適化アンザッツのコスト関数に不等式制約を組み込むための低複雑さ形式について述べる。 シミュレーション実験において,IF-QAOAの従来のペナルティベースアプローチよりも優れた性能を示す。 また、最近開発されたクナップサック問題に対する量子木生成器QAOAとベンチマークを行い、同様の複雑さの回路に対する解の質を実証した。
• 参考スコア（独自算出の注目度）: 5.722288093279744
• License:
• Abstract: Traditional methods for handling (inequality) constraints in the Quantum Approximate Optimization Ansatz (QAOA) typically rely on penalty terms and slack variables, which increase problem complexity and expand the search space. More sophisticated mixer-based QAOA variants restrict the search within the feasible assignments but often suffer from prohibitive circuit complexity. This paper presents a low-complexity formalism for incorporating inequality constraints into the cost function of QAOA using an oracle-based subroutine that evaluates constraint satisfaction in an additional register, subsequently called Indicator Function QAOA (IF-QAOA). The IF-QAOA cost function consists of a step-function but does not require a penalty term with additional parameters. Applied to the Knapsack problem, we demonstrate the superior performance of IF-QAOA over conventional penalty-based approaches in simulated experiments. Using advanced QAOA simulation techniques with instances consisting of up to 22 items, we find that IF-QAOA achieves significantly higher solution quality and a faster time-to-solution in 82% of our benchmark cases. Analysis of the scaling behavior shows favorable scaling of IF-QAOA compared to penalty-based methods. Also, benchmarked against the recently developed Quantum Tree Generator QAOA for Knapsack Problems, we demonstrate higher solution quality for circuits of similar complexity. Additionally, the paper introduces a method for approximate indicator function when the number of ancillary qubits is limited. With a specialized simulation algorithm based on projective measurements, we empirically demonstrate that a fixed number of ancillary qubits is sufficient to encode general inequality constraints.
• Abstract（参考訳）: QAOA(Quantum Approximate Optimization Ansatz)における制約(不等式)を扱う従来の手法は、通常ペナルティ項とスラック変数に依存しており、この問題の複雑さを増大させ、探索空間を拡張する。 より洗練されたミキサーベースのQAOA変種は、実現可能な割り当て内での探索を制限するが、しばしば回路の複雑さに悩まされる。 本稿では,QAOAのコスト関数に不等式制約を組み込むために,付加レジスタ内の制約満足度を評価するオラクルベースのサブルーチンを用いて,低複雑さな形式化を行い,後にIndicator Function QAOA (IF-QAOA) と呼ぶ。 IF-QAOAコスト関数はステップ関数から構成されるが、追加パラメータを持つペナルティ項を必要としない。 Knapsack問題に適用し、シミュレーション実験における従来のペナルティに基づくアプローチよりもIF-QAOAの優れた性能を示す。 IF-QAOAは, 最大22項目のインスタンスを用いた高度なQAOAシミュレーション手法を用いて, 82%のベンチマークケースにおいて, 解の質と解の高速化を実現している。 IF-QAOAのスケーリングは,ペナルティに基づく手法に比べて良好である。 また、最近開発されたクナップサック問題に対する量子木生成器QAOAとベンチマークを行い、同様の複雑さの回路に対する解の質を実証した。 さらに,アシラリー量子ビット数が制限された場合の近似指標関数の手法を提案する。 射影測定に基づく特殊シミュレーションアルゴリズムを用いて, 一般の不等式制約を符号化するのに, 固定数のアクビットが十分であることを示す。

関連論文リスト

• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。 ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。 満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
  論文  参考訳（メタデータ） (2024-11-28T21:39:58Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  本稿では,変分量子アルゴリズムで実現可能な空間(VQA-PFS)アンサッツを提案する。 このアンザッツは制約変数に混合演算子を適用し、非制約変数にハードウェア効率アンザッツ(HEA)を用いる。 その結果, VQA-PFSは成功確率を著しく向上し, より高速な収束を示すことがわかった。
  論文  参考訳（メタデータ） (2023-12-12T01:36:49Z)
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
  量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。 本稿では,低自己相関二項列(LABS)問題に対するQAOAの広範な数値的な検討を行う。 パラメータが固定されたQAOAのランタイムは、分岐とバウンドの解法よりも良くスケールする。
  論文  参考訳（メタデータ） (2023-08-04T14:17:21Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  雑音は量子回路のバイアスによる目的関数の評価を行う。 我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
  論文  参考訳（メタデータ） (2022-09-21T19:18:41Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。 量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
  論文  参考訳（メタデータ） (2021-07-11T10:56:24Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。 学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。 また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
  論文  参考訳（メタデータ） (2021-05-14T11:31:14Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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