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