浅层QAOA优化景观并非平坦,而是随系统规模多项式增长的崎岖地形。
Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models

- 用大规模数值实验检验了浅层QAOA的优化景观特性。
- 发现景观方差随系统大小多项式增长,而非指数消失。
- 提出经验硬度模型,可准确识别景观类型,适合研究量子算法瓶颈。
变分量子算法(VQA)的动态李代数(DLA)理论预测,足够深的参数化电路会普遍出现损失和梯度方差指数级消失。本文通过针对最大独立集(MIS)问题的约23,000个实例的大规模数值研究发现,在浅层(尤其是恒定深度)条件下,这一预测严重失效:平缓高原(barren plateaus)罕见,而方差随系统规模多项式增长的“崎岖地形”(cragged terrains)普遍存在。这种增长在低对称性随机图和高度对称的顶点传递图中均成立,表明基于单位设计的渐近预测无法描述此区间下的景观行为。作为替代,我们训练经验硬度模型以预测实例级难度指标,虽泛化能力有限,但能高保真地恢复正确的景观类型(平缓高原或崎岖地形)。结果表明,浅层QAOA-MIS是典型场景,揭示了以渐近和单位设计为中心的理论在描述浅层变分量子算法时的根本局限,强调需发展更依赖实证的损失景观建模方法。
原文摘要 · Abstract (English)
The dynamical Lie algebraic (DLA) theory of variational quantum algorithms (VQAs) predicts commonplace exponentially vanishing loss and gradient variances for sufficiently deep parametrized circuits. In this work, we show that these predictions fail dramatically in the shallow-circuit (and particularly constant-depth) regime for the Quantum Approximate Optimization Algorithm (QAOA) applied to the maximum independent set (MIS) problem. In a large-scale numerical study across $\sim$23,000 problem instances, we find that barren plateaus are rare, while landscapes whose variances polynomially increase with system size---which we term "cragged terrains"---are common across graph families. This aggregate polynomial growth persists both for generic, low-symmetry random graphs and for highly symmetric vertex-transitive graphs, indicating that DLA-based variance predictions do not describe landscape scaling in this regime. As a stopgap alternative to the theory, we train empirical hardness models to predict instance-wise hardness metrics for QAOA-MIS. While these models generalize poorly, they nonetheless recover the correct landscape scaling class (barren plateau vs. cragged terrain) with high fidelity. Taken together, our results identify shallow QAOA for MIS as a prototypical setting in which asymptotic, unitary-design-centric predictions may be fundamentally insufficient to describe shallow variational quantum algorithms more broadly, emphasizing the need for more empirically-informed models of VQA loss landscapes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。