QAOA 在大多数 MaxCut 实例中存在贫瘠高原

本文研究了量子近似优化算法 (QAOA) 在 MaxCut 问题上的可训练性。它表明，QAOA 在绝大多数加权和非加权图上都存在贫瘠高原（损失函数几乎平坦的区域），这使得训练变得难以处理。这是一个重要的发现，因为它突出了 QAOA 在一个常见优化问题上的基本局限性。本文提供了一种新算法来分析动力学李代数 (DLA)，这是可训练性的一个关键指标，可以更快地分析图实例。结果表明，QAOA 的性能在实际应用中可能会受到严重限制。

• •QAOA 在大多数 MaxCut 实例中存在贫瘠高原，使得训练变得困难。
• •对于很大一部分图，DLA 维度呈指数增长。
• •开发了一种新算法来分析 DLA，提高了计算效率。
• •这些发现表明了 QAOA 在 MaxCut 实际应用中的局限性。