本源量子联合中科大研究团队在量子近似优化算法研究中取得新进展

来源：本源量子

近日，本源量子联合中科大研究团队在量子近似优化算法（Quantum Approximate Optimization Algorithm，后称“QAOA”）的研究中取得最新进展。该研究证明了S-QAOA算法（Shortcuts to Quantum Approximate Optimization Algorithm，“S-QAOA”）是利用现阶段的含噪声量子计算机求解组合优化问题的理想选择。这项研究进一步推进了量子计算在组合优化问题上的应用。

论文地址：https://arxiv.org/abs/2112.10943

组合优化问题在现实生活中具有广泛的应用，比如物流、调度、金融等领域的许多问题都是组合优化问题。并且很多组合优化问题对应的经典算法都有较高的复杂度，在问题规模较大时，经典计算机难以快速地找到这些问题的最优解。因此，利用量子计算加速组合优化问题的求解具有重要的意义，其中著名的QAOA算法就有望在组合优化问题的求解上取得指数级的加速。

在含噪声的中等规模（NISQ）的量子时代，可靠的量子操作数会受到量子噪声的限制（目前量子噪声包括量子退相干、旋转误差等）。因此，人们对量子-经典混合算法很感兴趣，这类混合算法可以借助经典优化器来优化量子线路中的参数，从而选择最优的演化路径，以降低量子线路深度。比较著名的一类量子-经典混合算法就是量子近似优化算法（QAOA），旨在寻找目标哈密顿量的基态，它有望为组合优化问题的近似解的求解带来指数级的加速。

理论上，如果量子线路足够深，QAOA可以得到较好的近似解。但由于量子噪声引起的误差会随着量子线路深度的增加而累积，当量子线路深度较大时，QAOA的性能实际上会下降。因此，在当前的量子计算机上展现QAOA算法的优势是一项具有挑战性的任务，降低QAOA算法的线路深度对于在现阶段的量子计算机上展现QAOA算法的优势具有重要意义。

为了减少量子电路的深度，研究人员提出了一种新的思路，称为“Shortcuts to QAOA”:（S-QAOA）。首先，在S-QAOA中考虑了额外的两体相互作用，在量子电路中加入与YY相互作用相关的双门以补偿非绝热效应，从而加速量子退火过程，加速QAOA的优化；其次，释放了两体相互作用（包括ZZ相互作用和YY相互作用）的参数自由度，增强量子电路的表示能力，从而降低量子线路的深度。数值模拟结果表明，与QAOA相比，S-QAOA在量子线路更浅的情况下可以获得较好的结果。

图一

图二 说明：S-QAOA在u3R-MaxCut问题（图一）和w3R-MaxCut问题（图二）上的应用。图中展示了三种算法的成功率随着算法层数的变化：蓝色数据点表示QAOA算法，粉色数据点表示在QAOA算法基础上只释放参数自由度，绿色数据点表示S-QAOA算法（即除了释放参数自由度外，还在线路中引入了YY两体相互作用）。在线路深度一定时，S-QAOA算法都能得到更高的成功率，尤其是在更难优化的w3R-MaxCut问题上，S-QAOA算法的优势更为明显。

研究人员通过引入更多的两体相互作用和释放参数自由度来改进QAOA算法，降低QAOA算法需要的线路深度，使得QAOA算法更适合现阶段的含噪声的量子计算机。由于该算法利用了STA(Shortcuts to adiabaticity)的原理，因此研究人员将其称为“Shortcuts to QAOA”。

本源量子研究人员表示：“在S-QAOA中，参数自由度的释放是通过对梯度较大的参数进行进一步的优化，但是是否有更好的方式挑选出最重要的参数做优化，还是值得探索和研究的一个方向。我们将在下一步的工作中研究更多的案例，以验证和完善我们的想法。我们希望我们的方法可以为尽早实现量子优越性提供新的方法和思路。”

—End—

相关阅读：

光子盒将为中国境内的研究机构和企业提供一个免费的垂直招聘信息发布渠道，欢迎有需求的机构或企业直接联系光子盒。（微信：Hordcore）

你可能会错过：