274
在文章开始之前，小编想和大家一起做个小游戏。游戏规则如下：对于给定的图形，只画一条线，在一条边只能被经过一次的条件下，使得笔画经过的边的数量最多。比如对于三角形，图示的画法就是经过边数量最多的画法（对称的画法算一种）。
再比如对于四边形，其割值最大的分割方法是如下图所示的。
那么对于下图，怎样才能使经过的边最多呢？
上面的游戏就是著名的最大割问题。最大割问题（Maximum Cut， Max-Cut）的描述是，给定一张图，求一种分割方法，将所有顶点分割成两群，同时使得被切断的边数量最大[1]。该问题是一个NP完备问题（注：NP问题是指不能在多项式时间内求解的问题）。
Max-Cut问题在现实生活中有很多应用，比如电路设计、交通优化、社交网络分析等。类似的组合优化问题广泛地出现在我们生活的方方面面，而这些问题中很多一部分问题是像最大割问题一样的NP问题，解决其所需要的时间随着问题的规模增大而指数地增加，导致我们很难获得精确解。而现有的基于冯诺依曼体系的算法，使得我们只能在精确度和时间之间进行取舍。除了探索研究更好的算法，探索非冯诺依曼计算体系也成为研究的方向之一。
而伊辛机便是在这种需求下应运而生。所谓的伊辛机是将组合优化问题映射到我们小学二年级就学过的伊辛模型上，通过物理退火搜索最优值的一种方法。要想理解伊辛机，首先得了解什么是伊辛模型。
01、伊辛模型简介
伊辛模型是以德国物理学家恩斯特·伊辛命名的数学模型，用以描述物质的铁磁性[2]。其基本思想是想象铁磁物质是由一个个小磁针构成，小磁针只能有两个朝向，向上或者向下，磁针的朝向称为自旋，磁针之间会有相互作用。
图1：伊辛模型示意图
在没有外磁场的情况下，系统的哈密顿量为：
其中是磁针之间的耦合系数，是自旋，只能取或者-1。在自旋相互作用的作用下，整个系统的磁针排列方式会朝着使系统伊辛能量最低的方向演化，这也符合能量最低原理。例如下面两幅图是二维伊辛模型的模拟结果，随着自旋组合的变化，系统的伊辛能量逐渐降低。
图2：2D伊辛模型模拟变化图
图3：2D伊辛模型能量变化
伊辛模型虽然简单，但却很有效，除了用以描述物质的铁磁性，也被应用到股票市场、种族隔离、政治选择等不同的问题[3]。今年获得诺贝尔物理学奖的霍普菲尔德神经网络也是启发自伊辛模型，可以视为伊辛模型的变种。由于篇幅限制，小编在这里就不再做过多介绍，想了解更多有关伊辛模型的同学请自行查看有关的资料哦。
02、伊辛机是什么
了解了什么是伊辛模型，接下来介绍一下什么是伊辛机，以及如何用伊辛机去解决最大割问题。所谓的伊辛机一种模拟伊辛模型的特殊物理装置，通过自旋间的相互作用其自然地趋于系统的最低能量状态，可以被用来解决一些组合优化问题。具体来说，我们将问题的参数映射到自旋的取值上，然后利用物理退火的方式去搜寻伊辛模型的基态，伊辛模型的基态对应着组合优化问题的最优值。
达到基态后，我们只需要将基态对应的自旋取值转换成组合优化问题对应的参数，就得到了组合优化问题的最优方案[4][5]。举个例子，如图所示，我们假设给定图的顶点处有个小磁针，我们分别给它编号，边代表小磁针之间的耦合强度，这里假定所有的磁针之间的耦合强度都是-1，且没有外磁场。那么请同学们认真思考，小磁针怎样排布可以使系统的能量最低呢？
我们可以计算图此时的伊辛能量，由于没有外磁场，伊辛能量只有第一项，我们代入公式：
注意耦合强度是-1，得到伊辛能量为-4，我们会发现这就是这幅图伊辛能量的最低值。小磁针的取值使得顶点被分为两类，我们试着用笔分开不同类别的顶点，就得到了如下所示的结果。
同学们可以发现，这样的割法得到的割值就是最大的，是不是非常的amazing！伊辛能量的最低值竟然恰好和最大割问题的最优值对应，这是巧合吗？对于最大割问题，我们的目标函数为:
对上面的式子稍加变形，引入自旋变量，就可以得到如下的式子:
上式中，可以看到这个表达式的第二项正是伊辛能量，于是若伊辛能量达到最小值，整个式子便达到了最大值，也就意味着找到了最大割。
03、结语
在大数据人工智能背景下，随着摩尔定律极限的逼近，探索非冯诺依曼计算架构对于满足日益增长的算力需求具有重要意义，而伊辛机作为一种新型的计算架构，以其解决组合优化问题的出色表现，具有重要的研究价值和广阔的应用前景。尽管目前有关伊辛机的研究，例如相干伊辛机[4][5]、微波光子伊辛机[6]等尚停留在实验室阶段，但可以预见，随着研究的深入，伊辛机将会为解决算力瓶颈提供新思路和解决方案。
参考文献
[1]https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%89%B2%E5%95%8F%E9%A1%8C
[2]Onsager L. Crystal statistics. I. A two-dimensional model with an order-disorder transition[J]. Physical Review, 1944, 65(3-4): 117.
[3]https://wiki.swarma.org/index.php/%E4%BC%8A%E8%BE%9B%E6%A8%A1%E5%9E%8B_Ising_Model
[4]Honjo T, Sonobe T, Inaba K, et al. 100,000-spin coherent Ising machine[J]. Science advances, 2021, 7(40): eabh0952.
[5]nagaki T, Haribara Y, Igarashi K, et al. A coherent Ising machine for 2000-node optimization problems[J]. Science, 2016, 354(6312): 603-606.
[6]Cen Q, Ding H, Hao T, et al. Large-scale coherent Ising machine based on optoelectronic parametric oscillator[J]. Light: Science & Applications, 2022, 11(1): 333.
编辑：Max
责编：六块钱的鱼
