近日，威尼斯官网计算机科学与技术学院阮越博士在国际权威期刊《Information Sciences》发表量子近似优化算法最新研究成果。《Information Sciences》是信息系统领域顶级期刊，中科院一区Top期刊，影响因子8.233。威尼斯官网为论文第一单位，阮越博士为论文第一作者，2020级硕士研究生袁志强为第二作者，阮越博士和东南大学博士生导师、副教授刘志昊为共同通讯作者。上述研究成果得到了国家自然科学基金、安徽省自然科学基金、江苏省自然科学基金、安徽省教育厅自然科学重点研究基金等项目资助。

量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是基于量子线路模型对量子绝热算法求解组合优化问题进行近似的算法框架，普遍认为是在含噪的中尺度量子计算设备（Noisy Intermediate-Scale Quantum，NISQ）上展示的相对于经典计算优势的算法之一。在这一框架内，求解约束优化问题的传统方法是在问题哈密尔顿量中添加惩罚项，将原问题转化为无约束的优化问题求解，对应的量子线路较浅，算法演化需要在包含可行解和非可行解的全空间内进行，算法求解出的解质量不高。

本研究给出了在QAOA算法框架内处理约束优化问题的一种新方案，不在问题哈密尔顿量中添加惩罚项，而是将约束写入混合哈密尔顿量，将算法的演化限定在可行解的范围内，提高了最终解的质量。方案分析了组合优化问题约束表达的数学形式，将其形式化地描述为线性等式约束、线性不等式约束和一般约束，给出了满足这些约束条件的混合哈密尔顿量的数学形式及其诱导出的酉算子对应的量子线路。方案还提出了一个重要猜想，即算子的正定性（regularity）有助于提升QAOA算法性能，丰富和完善了QAOA算法处理约束优化问题的手段，在IBM量子计算机上的运行结果显示，相较传统方案有较大的性能提升。

（解决约束优化问题Graph Partition的传统方案及结果）

（解决约束优化问题Graph Partition的新方案及结果）

（猜想验证---算子的正定性有利于提高算法性能）

论文链接：https://doi.org/10.1016/j.ins.2022.11.020

（撰稿：陶陶 审核：吴宣够 张苒 杜飞）