QAOAはMaxCutのほとんどのインスタンスでBarren Plateausに苦しむ

この論文は、MaxCut問題に対する量子近似最適化アルゴリズム（QAOA）の学習可能性を調査しています。QAOAが、加重グラフと非加重グラフの大部分で、学習が困難になるようなbarren plateaus（損失関数がほぼ平坦な領域）に苦しむことを示しています。これは、一般的な最適化問題に対するQAOAの基本的な制限を浮き彫りにする重要な発見です。この論文は、学習可能性の重要な指標である動的リー代数（DLA）を分析するための新しいアルゴリズムを提供し、グラフインスタンスのより高速な分析を可能にします。この結果は、QAOAの性能が実際のアプリケーションで著しく制限される可能性があることを示唆しています。

• •QAOAは、ほとんどのMaxCutインスタンスでbarren plateausに苦しみ、学習が困難になります。
• •DLAの次元は、グラフの大部分で指数関数的に増加します。
• •DLAを分析するための新しいアルゴリズムが開発され、計算効率が向上しました。
• •この発見は、MaxCutに対するQAOAの実用的な適用可能性の限界を示唆しています。