优化问题的量子加速求解研究

《中国科学：物理学 力学 天文学》英文版(SCIENCE CHINA Physics, Mechanics & Astronomy, SCPMA) 2021年第10期出版了清华大学和北京量子研究院龙桂鲁教授团队和深圳京鲁计算科学应用研究院李可仁研究员团队的最新研究成果：“Quantum Second order Optimization Algorithm for General Polynomials ”[1]，同期出版了中国科学院物理研究所范珩研究员撰写的点评文章[2]。

这是一个关于量子牛顿算法的理论设计工作，该算法具有很快的收敛速度，大大降低了优化问题的计算复杂度，将在分解机模型训练、非线性方程组的求解等问题中发挥重要作用。

量子牛顿算法的线路框图

优化问题是数值研究的核心问题之一，在经济管理、金融投资、天气预测等诸多复杂模型的参数评估过程中扮演重要角色。然而经典数值优化方法的计算复杂度随着问题的变量维度成线性或者更快的增长，因此对于动辄含有数以十亿计待优参数的复杂模型，其训练将变得越来越困难。

多项式函数作为简单的完备函数基，不仅自身常被用为最小二乘估计、分解机模型训练等过程的损失函数，而且可以通过简单的叠加组合来表示更一般的函数形式。因此，多项式函数优化问题的快速求解具有普遍的实用意义。

量子梯度优化算法(a, b)与量子牛顿算法(c, d)的收敛效率对比

该文中作者通过对经典的量子幅度编码添加辅助量子态的方式，赋予了量子幅度编码更强的表达能力。在此基础上，结合量子主成分分析方法和哈密顿量模拟方法，提出了一种适用于一般多项式函数的量子牛顿优化算法。该算法的计算复杂度对于变量维度的依赖从经典算法的线性关系降低到了对数关系，较于经典方法在单步迭代过程有指数加速。与已有的量子梯度优化方法相比，量子牛顿方法具有更快的收敛速度，在上图所示的该文相关实例中其更是表现出两个数量级的加速优势，进一步降低了优化问题的整体计算复杂度。这一方法将在分解机模型训练、非线性方程组的求解等问题中发挥重要作用。

---