論文の概要: QAOA-MaxCut has barren plateaus for almost all graphs

• arxiv url: http://arxiv.org/abs/2512.24577v1
• Date: Wed, 31 Dec 2025 03:02:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-01 23:27:28.546139
• Title: QAOA-MaxCut has barren plateaus for almost all graphs
• Title（参考訳）: QAOA-MaxCut はほとんど全てのグラフに対して不規則な高原を持つ
• Authors: Rui Mao, Pei Yuan, Jonathan Allcock, Shengyu Zhang,
• Abstract要約: VQAsの表現性と訓練性を示す重要な指標は、高度に対称な例を超えては理解されていない。 指数関数的にスケールするDLA次元は、いわゆるバレンプラトーの存在と関連している。 本研究では、重み付きグラフと非重み付きグラフの両方に対して、標準MaxCutに適用されたQAOAのDLAについて検討する。
• 参考スコア（独自算出の注目度）: 12.977235450329466
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The QAOA has been the subject of intense study over recent years, yet the corresponding Dynamical Lie Algebra (DLA)--a key indicator of the expressivity and trainability of VQAs--remains poorly understood beyond highly symmetric instances. An exponentially scaling DLA dimension is associated with the presence of so-called barren plateaus (BP) in the optimization landscape, which renders training intractable. In this work, we investigate the DLA of QAOA applied to the canonical MaxCut, for both weighted and unweighted graphs. For weighted graphs, we show that when the weights are drawn from a continuous distribution, the DLA dimension grows as $Θ(4^n)$ almost surely for all connected graphs except paths and cycles. In the more common unweighted setting, we show that asymptotically all but an exponentially vanishing fraction of graphs have $Θ(4^n)$ large DLA dimension. The entire simple Lie algebra decomposition of the corresponding DLAs is also identified, from which we prove that the variance of the loss function is $O(1/2^n)$, implying that QAOA on these weighted and unweighted graphs all suffers from BP. Moreover, we give explicit constructions for families of graphs whose DLAs have exponential dimension, including cases whose MaxCut is in $\mathsf P$. Our proof of the unweighted case is based on a number of splitting lemmas and DLA-freeness conditions that allow one to convert prohibitively complicated Lie algebraic problems into amenable graph theoretic problems. These form the basis for a new algorithm that computes such DLAs orders of magnitude faster than previous methods, reducing runtimes from days to seconds on standard hardware. We apply this algorithm to MQLib, a classical MaxCut benchmark suite covering over 3,500 instances with up to 53,130 vertices, and find that, ignoring edge weights, at least 75% of the instances possess a DLA of dimension at least $2^{128}$.
• Abstract（参考訳）: QAOAは近年、激しい研究の対象となっているが、対応する動的リー代数(DLA)は、VQAsの表現性と訓練性の重要な指標である。 指数関数的にスケールするDLA次元は、最適化ランドスケープにいわゆるバレンプラトー(BP)が存在することと関連付けられ、訓練は難易度が高い。 本研究では、重み付きグラフと非重み付きグラフの両方に対して、標準MaxCutに適用されたQAOAのDLAについて検討する。 重み付きグラフの場合、重み付けが連続分布から引き出されるとき、DLA次元は経路とサイクルを除くすべての連結グラフに対してほぼ確実に$(4^n)$として成長することを示す。 より一般的な非重み付け設定では、漸近的にすべてのグラフが指数関数的に消える部分を除いては、大きな DLA 次元が $(4^n)$ であることを示す。 対応する DLA 全体の単純リー代数分解も同定され、損失関数の分散が$O(1/2^n)$であることを証明する。 さらに、DLA が指数次元を持つグラフの族に対して、MaxCut が $\mathsf P$ である場合を含む明示的な構成を与える。 非重みのないケースの証明は、可換に複雑なリー代数問題から可換グラフ理論問題への変換を可能にする多くの分割補題と DLA 自由条件に基づいている。 これらのアルゴリズムは、従来の手法よりも桁違いに高速にDLAを計算し、標準ハードウェア上でのランタイムを数日から秒に短縮する新しいアルゴリズムの基礎を形成する。 このアルゴリズムを従来のMaxCutベンチマークスイートであるMQLibに適用し、最大53,130頂点を持つ3,500以上のインスタンスをカバーし、エッジウェイトを無視して、少なくとも75%のインスタンスが少なくとも2^{128}$のDLAを持つことを示した。

関連論文リスト

• Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips [0.0]
  量子近似最適化アルゴリズム(QAOA)のコストハミルトンコンパイル問題をMax-Cut問題に適用する。 CNOTとRzゲートの標準コンパイルの代わりに、グローバル結合演算と単一ビットビットフリップを採用する。
  論文  参考訳（メタデータ） (2025-08-29T18:12:20Z)
• Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。 まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。 第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。 最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-23T16:35:47Z)
• On the dynamical Lie algebras of quantum approximate optimization algorithms [4.987686869768721]
  動的リー代数(DLAs)は、パラメータ化量子回路の研究において貴重な道具として登場した。 本研究では,量子近似最適化アルゴリズム(QAOA)のDLAについて検討する。 DLAの次元が$O(n3)$であることを示し、DLAの明示的な基底を与える。
  論文  参考訳（メタデータ） (2024-07-17T14:12:30Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。 導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
  論文  参考訳（メタデータ） (2021-10-20T23:46:35Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
  ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。 我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
  論文  参考訳（メタデータ） (2020-06-26T12:06:10Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)
• What do QAOA energies reveal about graphs? [2.0305676256390934]
  グラフ構造に対するQAOAエネルギーの依存を利用して、ランダムにあるいは司法的に選択されたパラメータをグラフについて学習する。 我々の発見の多くは、様々な制約の下で$U(G)$と解釈できる。
  論文  参考訳（メタデータ） (2019-12-27T18:37:30Z)

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

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