组合优化问题，在应用数学和理论计算机科学领域，指的是在一个有限的对象里集中找出最优对象的一类课题。这类问题特征是可行解的集是离散或者可以简化到离散结果，并且目标是要找到最优解。当前，常见的组合优化问题通用版上包括旅行商问题和最小生成树，行业场景领域上涉及极大规模的集成电路设计、药物设计和财务组合管理等问题。

显然，无论是金融、制药或是财务等领域，组合优化问题都是最贴近科技赋能日常生活与工作的实用问题之一，一旦有效解决这类问题，将会迅速提高我们的日常效率，而同时经过了实验和市场论证的最优解算工具就是“退火算法”。

组合优化问题的挑战与解算方案

当前，因为在组合优化问题的解算中，穷举搜索和枚举法并不可行。其核心问题主要在于理论分析中涉及了拓扑分析，所以在不同的拓扑形态下，不同部分的约束关系就不同，算法也需要随时调整。如果给定一个拓扑形态，组合优化往往就退化成一个整数优化的问题了，这样有些问题就可以比较简单的推理和解算了。

以组合优化问题之一的旅行商问题（TSP）为例，最早的旅行商问题的数学规划是在1959年由Dantzig等人提出，它是最基本的最短路径问题，这也属于组合优化中的一个NP困难问题。

具体的问题描述为旅行商要到若干个城市旅行，各城市之间的费用是已知的，为了节省费用，旅行商决定从所在城市出发，到每个城市旅行一次后返回初始城市，那么他应选择什么样的路线才能使所走的总费用最短？当城市数量增加时，问题的复杂度会迅速的呈指数增加，如当有30个城市时，用现在最快的超级计算机将所有可能的路线都尝试一遍，也需要花几十万年的时间。

旅行商问题的解（图片来源：网络）

此外，这类问题的衍生还可涉及到物流中的配送问题，比如将n个客户的订货沿最短路线全部送到，如何确定最短路线？一个厂房中n个不同工序之间如何排布？电路板上不同器件之间如何排列？诸如此类都是组合优化问题中的实际问题。

量子退火VS模拟退火

如上文所提，对于旅行商类问题的最优化算法，目前常用的算法就是退火算法，分为模拟退火和量子退火两种，模拟退火的方法已经可以解决其中的很多问题，只不过量子退火更胜一筹。

不过想要了解“模拟退火”“量子退火”，首先要知道什么是“退火”？“退火”本质上是一种将金属缓慢加热到一定温度并保持足够时间，然后以适宜速度冷却的金属热处理工艺。目的是对金属材料和非金属材料降低硬度，改善切削加工性，也可稳定尺寸、减少变形与裂纹倾向以及消除组织缺陷。

拿半导体芯片来看，在经过离子注入以后就需要退火，因为往半导体中注入杂质离子时，高能量的入射离子会与半导体晶格上的原子碰撞，使一些晶格原子发生位移，结果造成大量的空位，这会使得注入区中的原子排列混乱或者变成非晶区，所以在离子注入以后必须把半导体放在一定的温度下进行退火，以恢复晶体的结构和消除缺陷。

显然，“退火”解决的是材料在研制过程中的硬件工艺不稳定问题，而“模拟退火”“量子退火”则是解决组合优化等数学计算中的非优解问题。

在20世纪80年代中期，贝尔实验室的研究人员斯柯特·柯克帕特里克(Scott Kirkpatrick)等人就开发了模拟退火算法。它最初是为了通过模拟退火过程来更好地优化集成电路芯片的设计而开发，原理上可类比“退火”，是一种通用概率算法，只不过是将热力学理论套用到统计学上，常用来在一定时间内寻找在一个搜寻空间中的近似最优解。

量子退火就是通过超导电路、相干量子计算（CIM）实施激光脉冲等方式、以及基于模拟退火（SA）的相干量子计算，与数字电路，如现场可编程门阵列（FPGA）等一起实现的量子算法。

量子退火先从权重相同的所有可能状态（候选状态）的物理系统的量子叠加态开始运行，按照含时薛定谔方程开始量子演化。根据横向场的时间依赖强度，在不同的状态之间产生量子穿隧，使得所有候选状态不断改变，实现量子并行性。当横向场最终被关闭的时候，预期系统就已得到原优化问题的解，也就是到达相对应的经典伊辛模型(Ising Model)基态。这就是量子退火机的应用原理。

量子退火（图片来源：网络）

与模拟退火相比，在量子退火中，横向场的强度决定了改变所有并行状态量子幅的量子力学几率，依据实验分析和数据结果，可以表明量子退火在某些条件下优于模拟退火，但并不是完全替代和绝对碾压。

显然，与在传统计算机上运行的模拟退火算法不同，量子退火基于伊辛模型的算法以高度并行的方式进行计算，并且对于大型问题具有更好的可扩展性。因为模拟退火运行时间的长短在很大程度上取决于组合优化问题的规模，但在基于伊辛模型进行计算的情况下，计算时间基本保持不变，硬件大小根据问题呈线性或二次方增长。

因此，在组合优化类NP问题的求解中，量子退火算法的一般结构，更适用于求解max-SAT和最小multicut这类问题。

量子退火的应用情况

提到量子退火的商业应用——量子退火机，就不得不提到加拿大的一家量子计算机公司D-Wave。D-Wave商业销售的量子计算机原理是用金属铌制成的微小电流环形成量子比特，直接实现量子退火现象，可以模仿量子计算中单一比特存储大量数值的效果。值得注意的是，在商业应用落地上，量子退火方法可以通过使用叠加状态搜索各种可能性来有效地解决优化问题，有效满足各大企业对于实际工作方案的提效与加速需求。

截至目前，D-Wave已在物流、人工智能、材料科学、药物发现、网络安全、故障检测和财务建模等各个领域，构建了250多款早期应用程序。

D-Wave量子计算单元（图片来源：网络）

具体应用案例上，以早期采用 D-Wave 技术的大众汽车公司为例，其使用量子混合求解器服务扩展了量子用例，构建了涂装车间的调度应用程序。相关算法旨在优化汽车涂漆的顺序，通过使用混合求解器服务，产线可显着减少颜色切换的次数，以减少浪费并提高产能。

2020年3月，D-Wave还开放访问了旗下的量子云服务Leap，实现了实时量子计算的访问公开化，以便合作伙伴随时随地能通过任何笔记本电脑来访问它的最强功能。例如Sigma-I正在创建现实世界的实际应用程序，以面对医疗资源分配、员工调度、以及化解商业设施（比如电影院）拥堵等棘手挑战；Menten AI率先用它来确定从头开始设计的蛋白质结构，并且针对 COVID-19 的活病毒测试进行了开发。

虽然此前有人质疑这家公司的产品不是真的量子计算机，但现在的D-Wave的量子退火机接受了市场的检验并受到了社会对于其商业价值的大力肯定。

当下，通用量子计算机的研发落地还处于上升期，而量子退火类的专用量子计算机商业落地仅仅是一个开始。例如，不同于D-Wave利用超导器件研发的量子退火机，由全球量子科技领域奠基人山本喜久教授主导，联合日本电信电话株式会社和日本国立情报学研究所利用光学器件研发的量子计算设备，其可控的量子位数目已达5万个。而师承山本喜久教授的文凯博士，也是相干量子计算（CIM）方案的首位博士，现已回国创办了量子计算科技公司玻色量子，并搭建了在通用量子计算机、专用量子计算机之外的第三种混合计算架构：经典计算机+量子AI架构。

在量子计算产业落地上，正呈现着专用量子计算“一超多前”的商用态势。随着“量子信息”在我国国务院政府工作报告中的多次提出与强调，未来，国内量子计算的商用落地也会未来可期。

文：慕一

​编辑：王珩