論文の概要: The Expressive Power of Constrained QAOA: What You Might Have MISsed
- arxiv url: http://arxiv.org/abs/2609.18209v1
- Date: Wed, 16 Sep 2026 06:40:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:53.677094
- Title: The Expressive Power of Constrained QAOA: What You Might Have MISsed
- Title（参考訳）: 制約付きQAOAの表現力:MISsedとは?
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)により,制約の強制が状態空間の到達範囲をいかに変化させるかを示す。
We analyze the alternative $mathitFliptext-ortext-Stay$ mixer, which that the limited to the feasible subspace $W_mathcalF$ is correct to the shift negative Laplacian of the independent-set reconfiguration graph。
どちらのミキサーに対しても、空集合の標準QAOAは、有限深さの最大独立集合上で完全に支えられる状態を作ることができることを示す。
- 参考スコア（独自算出の注目度）: 0.38670524841575715
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Feasibility-preserving mixer Hamiltonians offer an attractive alternative to penalty encodings for constrained quantum optimization, yet how enforcing constraints alters the state space reachable by the Quantum Approximate Optimization Algorithm (QAOA) remains largely unexplored. We address this question within the context of the Maximum Independent Set (MIS) problem. Alongside the standard controlled bit-flip mixer, we analyze the alternative $\mathit{Flip\text{-}or\text{-}Stay}$ mixer, whose restriction to the feasible subspace $W_{\mathcal{F}}$ corresponds precisely to the shifted negative Laplacian of the independent-set reconfiguration graph. Although both mixers induce identical transitions between independent sets, the diagonal modification changes the spectral structure and can substantially enlarge the set of reachable quantum states. For every connected input graph with at least two vertices, we prove that independently parameterized local controls associated with either mixer generate the full unitary Lie algebra on the feasible subspace. Standard QAOA exhibits a more nuanced algebraic structure. We prove that the dynamical Lie algebra associated with MIS-QAOA employing the conventional mixer embeds into its Flip-or-Stay counterpart. Furthermore, we construct an infinite family of graphs for which the corresponding vacuum-state dynamical group orbits exhibit strictly distinct dimensions, establishing a qualitative expressivity separation between the two architectures. For either mixer, we show that standard QAOA initialized in the empty set can prepare a state supported entirely on maximum independent sets at finite depth. For the free architectures, we also derive an exact loss-variance formula in the unitary-design limit, expressed through the number of feasible independent sets and the variance of their cardinalities.
- Abstract（参考訳）: しかし、量子近似最適化アルゴリズム(QAOA)が到達可能な状態空間をどのように変化させるかは、まだ明らかにされていない。
本稿では,最大独立集合問題(MIS)の文脈内でこの問題に対処する。
標準的な制御されたビット-フリップミキサーの他に、代替の $\mathit{Flip\text{-}or\text{-}Stay}$mixer を解析する。
どちらのミキサーも独立集合間の同じ遷移を誘導するが、対角修正はスペクトル構造を変化させ、到達可能な量子状態の集合を著しく拡大することができる。
少なくとも2つの頂点を持つすべての連結入力グラフに対して、どちらのミキサーに関連付けられた独立にパラメータ化された局所制御が、実現可能な部分空間上で完全なユニタリリー代数を生成することを証明する。
標準QAOAはよりニュアンスな代数構造を示す。
従来の混合器を用いたMIS-QAOAに付随する動的リー代数がFlip-or-Stayに埋め込まれていることを証明する。
さらに、対応する真空状態の動群軌道が厳密に異なる次元を示す無限のグラフ群を構築し、2つのアーキテクチャ間の定性的表現性分離を確立する。
どちらのミキサーに対しても、空集合で初期化された標準QAOAは、有限深さの最大独立集合上で完全にサポートされた状態を作成することができることを示す。
自由アーキテクチャに対しては、ユニタリ・デザインの極限において、実現可能な独立集合の数とそれらの濃度の分散を通して表現される正確な損失分散式も導出する。
関連論文リスト
- Multiparameter quantum bounds for entanglement-assisted aperture synthesis [0.0]
エンタングルメント支援光干渉計は、光が物理的に結合できないベースライン上での回折制限イメージングを約束する。
本研究は,拡張シーンを撮像するMステーションアレイのマルチパラメータ推定問題を定式化する。
論文 参考訳（メタデータ） (2026-09-09T12:46:05Z) - Kernel Methods for Refined Prophet Inequalities [27.407082709350707]
単選択預言不等式は、独立した非負の値が逐次現れる標準的なオンライン選択問題である。
単項預言不等式に対する一般的なカーネル法を開発した。
論文 参考訳（メタデータ） (2026-08-09T12:08:57Z) - Symmetry-Projected Weakly Compatible Multiparameter Quantum Sensing [0.0]
位相生成器をサブスペース保存およびサブスペース変更セクターに分類する対称性投影フレームワークを開発する。
対称部分空間に制限されたプローブ状態に対して、対称性投射はQFIMとUCMに共通のブロック対角構造を課し、情報クロストークと測定の不整合性から同時にクロスセクタパラメータを描画する。
論文 参考訳（メタデータ） (2026-08-03T07:42:33Z) - CoCurve: Cross-Module Co-Pruning Curvature for Training-Free Structured LLM Pruning [47.406985340436925]
CoCurveはキャリブレーションのみの、微調整なしの手法で、注意とFFNのユニットを共同で刺激する。
これは1つの予算付き二次プログラムに還元され、ラベル、微調整、リカバリを伴わず、共有された注目の下で1ショットで解決される。
論文 参考訳（メタデータ） (2026-07-20T05:27:57Z) - A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling [7.035974899001363]
我々は, 隣接再帰安定性と重み付き濃度ステップから, 有限ラウンド上尾保証を導出した。
一次元の反例は、なぜギャップ、平滑化、あるいは正則性条件が必要なのかを示す。
論文 参考訳（メタデータ） (2026-06-01T05:36:26Z) - Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。
我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。
重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
論文 参考訳（メタデータ） (2026-02-24T05:32:03Z) - Maximum Independent Set via Probabilistic and Quantum Cellular Automata [0.0]
まず、動的にシステムを最大独立集合の多様体に向けて駆動する同期PCAを紹介する。
この振る舞いを動機として、純散逸相と制約保存ユニタリ進化を組み合わせたQCAを構築する。
論文 参考訳（メタデータ） (2025-12-07T10:33:52Z) - Limitation of Stoquastic Quantum Annealing: A Structural Perspective [0.0]
縮退した局所最小値の集合に付随するエネルギー間の競合から生じる反交差に関する構造的説明を提供する。
本論文は,DIC-DAC-DOAアルゴリズムの主な研究の補足として機能する。
論文 参考訳（メタデータ） (2025-09-18T04:39:48Z) - Solving Zero-Sum Convex Markov Games [38.68653814645517]
本研究では,Nash equilibria (NE) に独立手法を用いて,2プレーヤゼロサムゲーム (cMG) におけるグローバルコンバージェンスを初めて保証する。
NC-pおよび両側pPL条件下での一般的な制約付きmin-max問題に対処する。
論文 参考訳（メタデータ） (2025-06-19T08:12:02Z) - Conditional Distribution Quantization in Machine Learning [83.54039134248231]
条件予測 mathbbE(Y Mid X) はしばしば、マルチモーダル条件分布の複雑さを捉えることに失敗する(Y Mid X)
我々はn点条件量子化(n-point Conditional Quantizations)-勾配降下により学習可能なXの関数写像--近似数学L(Y mid X)-を提案する。
論文 参考訳（メタデータ） (2025-02-11T00:28:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。