在日常生活中，我们经常会遇到在有限的资源和一定的约束条件下寻求最优方案的问题。比如非常著名的旅行商问题（Traveling Salesman Problem，TSP），即一个旅行商需要到若干个城市推销商品，每个城市之间都互相连通，但距离各不相同，要求每个城市只能经过一次，旅行商应如何规划路线，使得他在经过所有城市后回到出发城市的总行程最短。

这类问题便属于组合优化问题，在很多领域都有着应用，如物流调度、生产计划、金融风险管理、网络设计等。很多组合优化问题都具有极高的计算复杂度，其求解时间随着问题规模的变大呈指数级增长，因而属于NP-hard问题。这也意味着利用现有的计算机算法无法在限定时间内找到最优解。最大割问题是一类典型的、NP-hard的组合优化问题，至今没有精确的求解方法，而近似求解方法也很难做到既高效又精确。量子计算的出现为开发这类问题的高效近似算法提供了新的可能。

近日，在前期工作的基础上，合肥微观纪元数字科技有限公司（简称“微观纪元”）的量子计算团队巧妙地将稳定子体系应用于最大割问题，构建了一种简单且优美的量子启发式算法，在提升求解速度的同时大幅改善了求解结果的近似程度。

量子计算为组合优化问题带来新思路

组合优化问题在如金融、物流、能源等众多领域中都有着广泛应用，可以帮助企业优化决策方案，从而改进资源调度、提高资源利用效率、降低生产成本、减少能源消耗。但由于组合优化问题的复杂性和困难性，这些问题往往需要耗费大量的计算资源和时间来解决。

目前，传统的优化算法仍然是产业界解决组合优化问题时的主要选择。这些算法包括分枝定界算法、动态规划算法等。这些算法在解决一些小规模的组合优化问题方面非常有效，但在面对实际应用中大规模、高复杂度的问题时，往往会面临指数级的计算复杂度。

产业界也采用了各种启发式算法来解决组合优化问题。常见的启发式算法包括贪心算法、遗传算法、模拟退火算法、蚁群算法等，它们可以从大量的数据中学习和推理，从而找到最佳解决方案。启发式算法可以在较短时间内求解问题，而且不需要对问题进行严格的数学建模，但存在可能陷入局部最优解、搜索空间过大等问题。

整体而言，这些方法在一定程度上可以找到问题的近似解或者局部最优解，但难以保证全局最优解的找寻。而由于其高度并行的计算能力，量子计算在解决组合优化问题方面具有巨大的潜力。

产业界极为关注量子计算

现阶段，研究人员已经开发了一些用于解决组合优化问题的量子算法，如量子模拟退火算法、量子近似优化算法等。理论上，相比于传统优化算法和启发式算法，基于量子计算的算法具有更高的计算效率和求解能力，可以更快地找到最优解，但当前的量子计算技术仍处于发展初期，距离实际解决问题尚有一段距离。

而金融、交通、物流等领域的诸多企业已经对量子计算表达了极大的兴趣，并展开了很多前期的研究。如摩根大通提出了适用于近期量子硬件的投资组合优化算法，德国联邦铁路公司的子公司与剑桥量子公司合作探索利用量子算法优化列车调度，Quantinuum与三星、新日铁和宝马合作共同探索以解决材料科学、供应链和物流优化方面的问题。

值得一提的是，在将量子计算应用于组合优化问题时，二次无约束二元优化（QUBO）问题是目前应用最广泛的优化模型，很多组合优化问题都可以借助QUBO问题来建模。QUBO问题有两种等价的表述形式，即伊辛模型和最大割问题。一般而言，我们在问题建模时使用QUBO表述，在物理实现时使用伊辛模型，而在算法分析时则使用最大割表述。

微观纪元开发“优胜劣汰”算法求解最大割问题

如前所述，最大割问题是一类典型的组合优化问题，在计算机科学、运筹学和图论领域具有广泛的应用。具体而言，给定一个带权无向图，将顶点集拆分成两个集合，连接两个集合的边被称为图的割，最大割问题就是寻找总权重（割中所有边的权重之和）最大的割。

如前所述，目前没有已知的多项式时间算法可以解决所有最大割问题实例，而各种近似算法也都不尽人意。参考解决最小割问题的思想，人们构想出了最大割的边收缩算法，由于被收缩掉的边最终都不出现在割上，所以边收缩算法是一种“劣汰”式算法。

但这种边收缩算法对于最大割的求解效果不佳，人们进而构造了相对应的“优胜”式算法——差分式边收缩算法。尽管这一算法在一定程度上改善了解的近似程度，但改进的程度有限，且算法的结果依赖于边收缩方向。

为此，通过将稳定子体系应用于最大割问题，微观纪元提出了一种全新的“优胜劣汰”式算法——稳定子算法。

该量子启发式算法非常巧妙地统一了最大割的边收缩算法和差分式边收缩算法，使得结果不再受收缩方向的影响，同时在性能上也有大幅提升。在与现有算法的比较中，稳定子算法表现出了显著的优势。在一些旅行商问题实例图的求解上，稳定子方法都得到了最优解，从而远胜于Sahni-Gonzalez系列算法，甚至能够媲美目前可能最强大的经典算法：基于半正定规划的Goemans-Williamson算法。与此同时，稳定子算法的运算速度也有了很大提升，可以轻松应用于具有数千节点且权重为任意实数值的图上。

稳定子算法在组合优化问题求解中潜力巨大

稳定子可以粗略地理解为“一组相互对易的力学量”；而稳定子态，就是它们的“共同本征态”，且本征值均为1。对于量子比特体系来说，稳定子表述具有更加丰富而优美的数学结构。正因为利用了这些数学结构，相应的量子启发式算法才在实践中表现得“快速、简单且高效”，而这一算法的思路也可以启发人们开发更多适用于其它组合优化问题的新算法。

经典世界是量子世界的特殊极限，经典问题和它们的量子类比之间往往存在着深层的联系。可以预期，对经典与量子计算之间深层联系的挖掘将带来全新的研究思路，并最终将二者融为一体。