論文の概要: Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization

• arxiv url: http://arxiv.org/abs/2605.20288v1
• Date: Tue, 19 May 2026 06:53:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.272331
• Title: Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization
• Title（参考訳）: ランダムk-SATに対するQAOAの有効性のメカニズム:断熱マニフォールドからサブ線形パラメータ最適化へ
• Authors: Mingyou Wu, Hanwu Chen,
• Abstract要約: 我々は,ランダムな$k$-SAT問題に対するQAOAを,ユニバーサルミキサ$k$-ローカル検索フレームワーク内で検討する。 この対応は、節密度$m=O(n1+)$と回路深さ$(n2)$のランダムなインスタンスに対して厳密な性能を保証する。 本研究では,非構造な高次元探索からガイド付き精細化プロセスへパラメータ最適化を変換するスムーズなアディバティック・マニフォールドパラメータ化(SAMP)戦略を提案する。
• 参考スコア（独自算出の注目度）: 0.8021197489470758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for demonstrating quantum advantage on near-term devices, yet the physical origins of its efficacy remain poorly understood. In this work, we study QAOA for random $k$-SAT problems within a universal-mixer $k$-local search framework, establishing a formal correspondence between adiabatic state transfer and the QAOA ansatz. This correspondence yields a rigorous performance guarantee for random instances with clause density $m=O(n^{1+ε})$ and circuit depth $Θ(n^2)$. We further investigate the NISQ regime with shallow circuits of depth $p=O(n)$. Surprisingly, the optimal parameters do not become stochastic under depth compression, but instead remain confined to a structured low-dimensional region, which we identify as a smooth adiabatic manifold. Numerical evidence indicates that this manifold persists across different circuit depths and arises from the variational suppression of adiabatic leakage. Based on this structure, we propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process. Numerical experiments on random 3-SAT instances show that SAMP achieves sublinear optimization scaling with circuit depth while providing robust zero-cost initialization for deep circuits.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、近距離デバイスにおける量子優位性を示す主要な候補であるが、その有効性の物理的起源はよく分かっていない。 本研究では, 局所探索フレームワークにおいて, ランダムな$k$-SAT問題に対するQAOAについて検討し, 断熱状態転送とQAOAアンサッツの形式的対応性を確立する。 この対応は、節密度$m=O(n^{1+ε})$と回路深さ$(n^2)$のランダムなインスタンスに対して厳密な性能を保証する。 さらに,深度$p=O(n)$の浅い回路を用いたNISQ方式についても検討する。 意外なことに、最適パラメータは深度圧縮の下で確率的になるのではなく、スムーズな断熱多様体であるような構造的低次元領域に限られる。 数値的な証拠は、この多様体が異なる回路深さにわたって持続し、断熱漏れの変動抑制から生じることを示している。 この構造に基づいて,非構造的高次元探索からガイド付き精細化過程へパラメータ最適化を変換するスムーズなアディバティック・マニフォールドパラメータ化(SAMP)戦略を提案する。 ランダムな3SATインスタンスの数値実験により、SAMPは回路深さによるサブ線形最適化のスケーリングを実現し、ディープ回路に対して堅牢なゼロコスト初期化を提供する。

関連論文リスト

• Universally Empowering Zeroth-Order Optimization via Adaptive Layer-wise Sampling [43.822941944402544]
  ゼロ階最適化は、微調整された大規模言語モデルのための有望なメモリ効率のパラダイムを提供する。 しかし,壁面収差の緩やかな収束と高い推定分散により,その実用化は厳しく制約されている。 本稿では,適応層型ZO最適化フレームワークであるAdaLeZOを提案する。
  論文  参考訳（メタデータ） (2026-04-20T13:37:31Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  単一ループ近似インプリシト差分法(SSAID)アルゴリズムの洗練された収束解析を行う。 i) 最適な$mathcalO(-2)$最先端のマルチループメソッドのレートと一致し、 (ii) $-dependenceの最初の明示的できめ細かい特徴を提供する。
  論文  参考訳（メタデータ） (2026-02-27T03:12:08Z)
• Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case [3.4872784636892047]
  Sherrington-Kirkpatrick(SK)モデルは、混乱したシステムを理解するための基盤となるフレームワークである。 量子近似最適化アルゴリズム (Quantum Approximate Optimization Algorithm, QAOA) は、量子最適化アルゴリズムであり、その性能は深さ$p$で単調に向上する。 無限大の極限においてSKモデルに適用されたQAOAを解析し、回路深さ$mathcalO(n/epsilon1.13)$の最適エネルギーに対して1-epsilon$の近似が得られるという数値的な証拠を与える。
  論文  参考訳（メタデータ） (2025-05-12T18:00:01Z)
• Adiabatic-Passage-Based Parameter Setting for Quantum Approximate Optimization Algorithm [0.7252027234425334]
  本稿では,新しい断熱パスに基づくパラメータ設定法を提案する。 本手法は, 3SAT問題に適用した場合の最適化コストを, サブ線形レベルに著しく低減する。
  論文  参考訳（メタデータ） (2023-11-30T01:06:41Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。 我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
  論文  参考訳（メタデータ） (2021-08-11T15:44:16Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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