量子科技中心_量科网

近年来，量子近似优化算法（QAOA）虽被广泛研究，但其对应的动态李代数（DLA）——衡量变分量子算法表达能力与可训练性的关键指标——在高度对称实例之外仍鲜为人知。DLA维度的指数级增长会导致优化空间中出现所谓“贫瘠高原”现象，使训练过程难以进行。该研究团队通过分析QAOA在典型MaxCut问题（含加权与未加权图）中的DLA特征发现：对于连续分布权重的连通图（路径图与环图除外），其DLA维度几乎必然以Θ(4ⁿ)速率增长；而在更常见的未加权图中，除指数级可忽略的极少数图例外，绝大多数图同样具有Θ(4ⁿ)量级的DLA维度。 研究人员还完整解析了对应DLA的单李代数分解结构，据此证明损失函数方差为O(1/2ⁿ)，表明这些加权与未加权图上的QAOA均会遭遇贫瘠高原问题。该工作进一步给出了DLA呈指数维度的图族显式构造，其中包含MaxCut属于P类问题的特例。针对未加权图的证明基于新型分裂引理与DLA无约束条件，成功将复杂的李代数问题转化为可处理的图论问题。基于此开发的新算法将DLA计算效率提升数个数量级，在标准硬件上实现从数天到秒级的突破。该算法应用于包含3,500余个实例（最大规模达53,130个顶点）的经典MaxCut基准库MQLib时发现：忽略边权情况下，至少75%实例的DLA维度不低于2¹²⁸。