‘壹’ 什么叫组合优化
组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令Ω＝{s1，s2，…，sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有C(s*)＝minC(si)。组合优化往往涉及排序、分类、筛选等问题，它是的一个重要分支。
典型的组合优化问题有旅行商问题（Traveling Salesman Problem－TSP）、加工调度问题（Scheling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack Problem）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）、聚类问题（Clustering Problem）等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。
‘贰’ 本源量子联合中科大在量子近似优化算法研究中取得新进展
近日，本源量子联合中科大研究团队在量子近似优化算法（Quantum Approximate Optimization Algorithm，后称“QAOA”）的研究中取得最新进展。该研究证明了S-QAOA算法（Shortcuts to Quantum Approximate Optimization Algorithm，后称“S-QAOA”）是利用现阶段的含噪声量子计算机求解组合优化问题的理想选择，进一步推进了量子计算在组合优化问题上的应用。
什么是组合优化问题？以着名的旅行商问题（TSP）为例，假设有渗乎磨一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。这就是一个典型的组合优化问题。
从广义上讲，组合优化问题是涉及从有限的一组对象中找到“最佳”对象的问题。“最佳”是通过给定的评估函数来测量的，该函数将对象映射到某个分数或者成本，目标是找到最高评估分数和最低成本的对象。组合优化往往涉及排序、分类、筛选等问题。
组合优化问题丛斗在现实生活中具有广泛的应用，比如交通、物流、调度、金融等领域的许多问题都是组合优化问题。并且很多组合优化问题对应的经典算法都有较高的复杂度，在问题规模较大时，经典计算机难以快速地找到这些问题的最优解。因此，利用量子计算加速组合优化问题的求解具有重要的意义。
在含噪声的中等规模（NISQ）的量子时代，可靠的量子操作数会受到量子噪声的限制（目前量子噪声包括量子退相干、旋转误差等）。因此，人们对量子-经典混合算法很感兴趣，这类混合算法可以借助经典优化器来优化量子线路中的参数，从而选择最优的演化路径，以降低量子线路深度。比较着名的一类量子-经典混合算法就是量子近似优化算法（QAOA），它有望为组合优化问题的近似解的求解带来指数级的加速。
研究人员表示，理论上，如果量子线路足够深，QAOA可以得到较好的近似解。但由于量子噪声引起的误差会随着量子线路深度的增加而累积，当量子线路深度较大时，QAOA的性能实际上会下降。因此，在当前的量子计算机上展现QAOA算法的优势是一项具有挑战性的任务，降低QAOA算法的线路深度对于在现阶段的量子计算机上展现QAOA算法的优势具有重要意义。
为了减少量子电路的深度，研究人员提出了一种新的思路，称为“Shortcuts to QAOA”:（S-QAOA）。首先，在S-QAOA中考虑了额外的两体相互作用，在量子电路中加入与YY相互作用相关的双门以补偿非绝热效应，从而加速量子退火过程，加速QAOA的优化；其次，释放了两体相互作用（包括ZZ相互作用和YY相互作用）的参数自由度，增强量子电路的表顷此示能力，从而降低量子线路的深度。数值模拟结果表明，与QAOA相比，S-QAOA在量子线路更浅的情况下可以获得较好的结果。
研究人员通过引入更多的两体相互作用和释放参数自由度来改进QAOA算法，降低QAOA算法需要的线路深度，使得QAOA算法更适合现阶段的含噪声的量子计算机。由于该算法利用了STA（Shortcuts to adiabaticity）的原理，因此研究人员将其称为“Shortcuts to QAOA”。
本源量子研究人员表示：“在S-QAOA中，参数自由度的释放是通过对梯度较大的参数进行进一步的优化，但是是否有更好的方式挑选出最重要的参数做优化，还是值得 探索 和研究的一个方向。我们将在下一步的工作中研究更多的案例，以验证和完善我们的想法。我们希望我们的方法可以为尽早实现量子优越性提供新的方法和思路。”