近日，本源量子联合中科大研究团队在量子近似优化算法（QuantumApproximateOptimizationAlgorithm，后称“QAOA”）的研究中取得最新进展。该研究证明了S-QAOA算法（ShortcutstoQuantumApproximateOptimizationAlgorithm，后称“S-QAOA”）是利用现阶段的含噪声量子计算机求解组合优化问题的理想选择，进一步推进了量子计算在组合优化问题上的应用。
（图片由本源量子授权发布）
什么是组合优化问题？以著名的旅行商问题（TSP）为例，假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。这就是一个典型的组合优化问题。
从广义上讲，组合优化问题是涉及从有限的一组对象中找到"最佳"对象的问题。“最佳”是通过给定的评估函数来测量的，该函数将对象映射到某个分数或者成本，目标是找到最高评估分数和最低成本的对象。组合优化往往涉及排序、分类、筛选等问题。
组合优化问题在现实生活中具有广泛的应用，比如交通、物流、调度、金融等领域的许多问题都是组合优化问题。并且很多组合优化问题对应的经典算法都有较高的复杂度，在问题规模较大时，经典计算机难以快速地找到这些问题的最优解。因此，利用量子计算加速组合优化问题的求解具有重要的意义。
在含噪声的中等规模（NISQ）的量子时代，可靠的量子操作数会受到量子噪声的限制（目前量子噪声包括量子退相干、旋转误差等）。因此，人们对量子-经典混合算法很感兴趣，这类混合算法可以借助经典优化器来优化量子线路中的参数，从而选择最优的演化路径，以降低量子线路深度。比较著名的一类量子-经典混合算法就是量子近似优化算法（QAOA），它有望为组合优化问题的近似解的求解带来指数级的加速。
研究人员表示，理论上，如果量子线路足够深，QAOA可以得到较好的近似解。但由于量子噪声引起的误差会随着量子线路深度的增加而累积，当量子线路深度较大时，QAOA的性能实际上会下降。因此，在当前的量子计算机上展现QAOA算法的优势是一项具有挑战性的任务，降低QAOA算法的线路深度对于在现阶段的量子计算机上展现QAOA算法的优势具有重要意义。
为了减少量子电路的深度，研究人员提出了一种新的思路，称为“ShortcutstoQAOA”:（S-QAOA）。首先，在S-QAOA中考虑了额外的两体相互作用，在量子电路中加入与YY相互作用相关的双门以补偿非绝热效应，从而加速量子退火过程，加速QAOA的优化；其次，释放了两体相互作用（包括ZZ相互作用和YY相互作用）的参数自由度，增强量子电路的表示能力，从而降低量子线路的深度。数值模拟结果表明，与QAOA相比，S-QAOA在量子线路更浅的情况下可以获得较好的结果。
研究人员通过引入更多的两体相互作用和释放参数自由度来改进QAOA算法，降低QAOA算法需要的线路深度，使得QAOA算法更适合现阶段的含噪声的量子计算机。由于该算法利用了STA（Shortcutstoadiabaticity）的原理，因此研究人员将其称为“ShortcutstoQAOA”。
本源量子研究人员表示：“在S-QAOA中，参数自由度的释放是通过对梯度较大的参数进行进一步的优化，但是是否有更好的方式挑选出最重要的参数做优化，还是值得探索和研究的一个方向。我们将在下一步的工作中研究更多的案例，以验证和完善我们的想法。我们希望我们的方法可以为尽早实现量子优越性提供新的方法和思路。”（张梦怡、杨夏，图片由本源量子授权发布）