量子算法为解决复杂问题提供了潜在的加速潜力，越来越多的研究人员正在探索基于量子行走的优化方法，将其视为一种颇具前景的方法。

图片来源：Quantum Zeitgeist

据外媒报道，里约热内卢联邦大学（Federal University of Rio de Janeiro）的Guilherme A. Bridi、拉脱维亚大学（University of Latvia）的Debbie Lim和新加坡国立大学（National University of Singapore）的Lirandë Pira及其同事正在研究这项技术的根本局限性，并为量子行走优化的表达能力和可训练性设定了关键界限，揭示了算法何时需要过多的参数才能找到有效解。重要的是，该团队证明，对于许多实际问题，这种方法避免了可能阻碍其他量子算法性能的棘手“贫瘠高原（barren plateaus，即由于梯度消失而导致优化停止的区域）”，为更可靠的量子优化策略铺平了道路。

探索基于Grover混合器的量子近似优化算法（QAOA）性能

这项广泛的研究详述了量子近似优化算法（QAOA）在解决复杂优化问题中的潜力，重点研究了其如何将Grover算法作为“混合器”来提升性能。研究人员研究了如何在使用Grover混合器时优化QAOA的参数和结构，并通过精心的参数初始化、电路设计以及利用问题中的对称性来应对“贫瘠高原”的挑战。

该论文深入探讨了基于Grover混合器的QAOA的理论复杂性，试图确定其性能的界限，并确定其在哪些条件下能够超越模拟退火和遗传算法等经典算法。论文考察了电路深度、参数优化和解决方案质量之间的权衡，并研究了包括MaxCut、3-SAT和车辆路径规划在内的基准问题上的性能。

理解优化问题和QAOA电路的对称性可以实现更高效的优化，并可能避免陷入“贫瘠高原”（barren platform），并使用动态李代数来分析行为并确定最优参数设置。关键研究结果表明，Grover混合器有望提升QAOA的性能，尤其是在实现比非结构化搜索更快的加速方面，并且利用对称性对于缓解“贫瘠高原”至关重要。

尽管QAOA展现出潜力，但要实现明确的量子优势仍然是一项重大挑战，需要精心设计、优化和问题选择。本研究重点关注理解QWOA的“表达力”和“可训练性”（决定其找到良好解的能力的关键因素），并推导出动态李代数（DLA）维度的新极限，DLA是一种用于分析量子算法复杂性的数学工具。这个界限揭示了一个根本性的权衡：QWOA需要额外的计算资源，具体来说是其量子电路中的更多层，才能找到某些类型问题的最优解。

研究表明，如果优化问题不属于BPPO复杂度类别，则QWOA必须过度参数化才能成功；如果问题不属于BP-APX类别，即使是近似解也需要过度参数化。重要的是，研究表明，对于一类具有多项式有界成本函数的问题，QWOA能够避免贫瘠高原。该团队的方法依赖于基本谱论证，从而清晰地理解QWOA的能力和局限性，并为更有针对性和更高效地应用这种量子优化技术铺平道路。

量子行走优化的动态李代数界

本研究为量子行走优化算法（QWOA）建立了动态李代数（DLA）维度的新上界，并证明该上界可预测地随待解决问题中不同代价值的数量而变化，且对于NPO-PB复杂度类中的问题，该上界保持多项式有界。这阐明了QWOA在哪些情况下需要过度参数化才能获得最优或近似解，尤其对于BPPO和BP-APX类之外的问题。此外，该研究表明，QWOA能够避免NPO-PB类中所有问题的贫瘠高原，从而确保该类中任意实例的可训练性。

研究人员称，未来研究需要建立DLA维度的下界，从而更全面地理解QWOA的表达能力，并建议在实际环境中探索表达能力与泛化能力之间的联系。最后，他们提出，这些结果可以通过结合特定问题的结构来启发开发新的、更高效的量子算法。