論文の概要: A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation

• arxiv url: http://arxiv.org/abs/2511.20212v1
• Date: Tue, 25 Nov 2025 11:35:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.429428
• Title: A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation
• Title（参考訳）: 定距離QAOA予測計算の統一複雑度アルゴリズムによる説明
• Authors: Jingheng Wang, Shengminjie Chen, Xiaoming Sun, Jialin Zhang,
• Abstract要約: 一般グラフと任意の固定ラウンド$pge2$に対して、所定の角度での固定ラウンドQAOAの期待を正確に評価することは、$mathrmNP$-hardであることを示す。 フレームワークを汎用バイナリ非制約組合せ最適化(BUCO)に拡張する。
• 参考スコア（独自算出の注目度）: 5.137643077079792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round $p\ge2$, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is $\mathrm{NP}$-hard, and that approximating this expectation within additive error $2^{-O(n)}$ in the number $n$ of vertices is already $\mathrm{NP}$-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the $p$-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size $n$. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to $p=3$ on representative structured families, including the generalized Petersen graph $GP(15,2)$, double-layer triangular 2-lifts, and the truncated icosahedron graph $C_{60}$, and report cut ratios while benchmarking against locality-matched classical baselines.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、組合せ最適化のために広く研究されており、理論的保証と実用的性能の両方において大きな進歩を遂げているが、一般的な組合せ最適化問題では、固定ラウンドQAOAの期待性能と古典的シミュラビリティは未だ不明である。 Max-Cut に着目して、まず、一般グラフと任意の固定円 $p\ge2$ に対して、所定の角度で固定円 QAOA の期待を正確に評価することは、$\mathrm{NP}$-hard であり、この期待を加法誤差 2^{-O(n)}$ で近似すると、頂点の$n$ は、既に$\mathrm{NP}$-hard であることを示す。 QAOAの性能を評価するために,木分解を利用した動的プログラミングアルゴリズムを提案する。 副産物として、$p$-ローカルツリー幅が頂点の数と対数的に大きくなると、グラフサイズ$n$の多項式時間 \emph{exact} 評価アルゴリズムが得られる。 Max-Cut以外にも、フレームワークを一般的なバイナリ制約のないコンビニアル最適化(BUCO)に拡張しています。 最後に、一般化されたPetersen graph $GP(15,2)$, double-layer triangular 2-lifts, and the truncated icosahedron graph $C_{60}$, and report cut ratios while benchmarking against locality-matched classical baselines。

関連論文リスト

• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
  NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。 従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
  論文  参考訳（メタデータ） (2023-05-22T19:59:19Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。 任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。 我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
  論文  参考訳（メタデータ） (2021-10-27T06:35:59Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
  すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。 任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
  論文  参考訳（メタデータ） (2021-01-14T09:17:20Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。 我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
  論文  参考訳（メタデータ） (2020-05-18T14:23:09Z)

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

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