論文の概要: Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement

• arxiv url: http://arxiv.org/abs/2511.17259v1
• Date: Fri, 21 Nov 2025 14:04:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-24 18:08:19.055527
• Title: Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
• Title（参考訳）: 制約問題に関するQAOAの基本的限界と指数拡張への道
• Authors: Chinonso Onah, Kristel Michielsen,
• Abstract要約: 本稿では,制約問題に対する一般量子近似最適化アルゴリズム(QAOA)の基本的限界について検討する。 本稿では,制約埋め込みによる指数的改善の道筋を示す。 カーネル構築における問題アルゴリズムの共設計のおかげで、技術と保証は置換を超えて幅広いNP-Hard制約最適化問題にまで拡張される。
• 参考スコア（独自算出の注目度）: 0.2578242050187029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study fundamental limitations of the generic Quantum Approximate Optimization Algorithm (QAOA) on constrained problems where valid solutions form a low dimensional manifold inside the Boolean hypercube, and we present a provable route to exponential improvements via constraint embedding. Focusing on permutation constrained objectives, we show that the standard generic QAOA ansatz, with a transverse field mixer and diagonal r local cost, faces an intrinsic feasibility bottleneck: even after angle optimization, circuits whose depth grows at most linearly with n cannot raise the total probability mass on the feasible manifold much above the uniform baseline suppressed by the size of the full Hilber space. Against this envelope we introduce a minimal constraint enhanced kernel (CE QAOA) that operates directly inside a product one hot subspace and mixes with a block local XY Hamiltonian. For permutation constrained problems, we prove an angle robust, depth matched exponential enhancement where the ratio between the feasible mass from CE QAOA and generic QAOA grows exponentially in $n^2$ for all depths up to a linear fraction of n, under a mild polynomial growth condition on the interaction hypergraph. Thanks to the problem algorithm co design in the kernel construction, the techniques and guarantees extend beyond permutations to a broad class of NP-Hard constrained optimization problems.
• Abstract（参考訳）: ブールハイパーキューブ内の低次元多様体を有効解とする制約問題に対する一般量子近似最適化アルゴリズム(QAOA)の基本的限界について検討し,制約埋め込みによる指数的改善への道筋を示す。 置換制約対象に焦点をあてると、逆場混合器と対角r局所コストを持つ標準一般QAOAアンサッツは、内在的実現可能性ボトルネックに直面している。 このエンベロープに対して、最小限の制約強化カーネル(CE QAOA)を導入し、製品の内部で直接動作し、ブロック局所XYハミルトニアンと混合する。 置換制約問題に対して, CE QAOA と一般 QAOA の既約質量の比が, 相互作用ハイパーグラフ上の軽度多項式成長条件下において, n の線形分数までのすべての深さに対して指数関数的に 1n^2$ で指数関数的に増加するような, 角度の頑健さ, 深さの一致した指数拡張を証明した。 カーネル構築における問題アルゴリズムの共設計のおかげで、技術と保証は置換を超えて幅広いNP-Hard制約最適化問題にまで拡張される。

関連論文リスト

• Geometric Algorithms for Neural Combinatorial Optimization with Constraints [46.17172939797694]
  Self-Supervised Learning for Combinatorial Optimization (CO)は、ニューラルネットワークを使って問題を解決するための新しいパラダイムである。 ニューラルネットワークによる離散的な制約付き最適化問題の解決を可能にする、エンドツーエンドの微分可能なフレームワークを設計する。
  論文  参考訳（メタデータ） (2025-10-28T03:49:01Z)
• Improving QAOA to find approximate QUBO solutions in O(1) shots [0.0]
  本稿では,目標近似比(AR)を達成する確率を,正確な最適化を必要とせず考慮した修正fpQAOA方式を提案する。 この組み合わせは、問題の大きさが大きくなるにつれて、近似解を得るために必要なショットの中央値の減少につながることを実証する。
  論文  参考訳（メタデータ） (2025-09-23T14:07:55Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz [0.0]
  線形に制約された最適化問題のクラスを解く量子交互演算子アンサッツ(QAOA$+$)を提案する。 このクラスの問題に対して、回路層数が増加するにつれて、最適解に確実に収束する回路を考案する。 この分析はQAOA$+$の性能保証を線形に制約された問題のより一般的な集合に拡張し、将来の一般化のためのツールを提供する。
  論文  参考訳（メタデータ） (2024-09-27T15:23:47Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm [1.3469999282609788]
  我々は、$n-要素$d$-ary文字列の集合上で定義される最適化問題の一般化された定式化に焦点を当てる。 我々の主な貢献は、当初提案されたQAOAの次元を含む。 アルゴリズムをより小さな次元の空間に制限することは、回路の量子シミュレーションと古典シミュレーションの両方を著しく加速させる可能性がある。
  論文  参考訳（メタデータ） (2023-09-25T00:35:40Z)
• Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks [41.94295877935867]
  本稿では,三対角四角形非制約二元最適化問題の解法として量子インスピレーション付きテンソルネットワークアルゴリズムを提案する。 また、直列鎖内の一方の隣り合う相互作用を伴うより一般的な2次非制約離散最適化問題を解く。
  論文  参考訳（メタデータ） (2023-09-19T10:45:15Z)
• 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)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)

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

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