Exact Spin Elimination for Quadratic and k-Local Ising Optimization

科学和工程领域中许多困难的问题，归根结底都是要在海量的可能性中寻找唯一的最佳排列方式。想象一下，要在一个房间里安排一群人，在满足一系列关于谁与谁能相处的复杂规则的前提下，让每个人都尽可能开心。在计算世界中，这些问题通常被建模为微小的开关，这些开关可以在两种状态之间切换。目标是通过以恰当的方式翻转开关，达到能量最低的状态，这便对应着完美的解决方案。然而，用于解决这些问题的机器对于一次能容纳多少个开关有着严格的限制。当问题过于庞大，或者规则涉及三个或更多开关同时相互作用时，机器根本无法将整个谜题装进其内存中。

为了让这些大型问题能够适配，研究人员传统上使用了一种叫做“二次化”（quadratization）的技巧。这种方法将涉及多个开关的复杂规则分解为仅涉及两个开关的简单规则。其代价是，为了实现这一点，计算机必须创造额外的、虚构的开关来充当占位符。虽然这简化了规则，但也用这些新的变量填满了机器有限的内存，往往导致没有空间容纳实际的问题。这是一种权衡：规则更简单了，但能解决的实际问题却变少了。剑桥大学的娜塔莉亚·G·贝洛夫（Natalia G. Berloff）的一项新研究提出了一种不同的方法。该研究建议，与其通过增加虚构开关来简化规则，不如直接移除真实的开关。通过仔细计算移除一个开关后会发生什么，研究人员发现他们可以在不需要额外内存的情况下缩小问题规模，从而让机器能够处理比以前大得多的谜题。

这种新方法的核心是一个被称为“沃尔什消除”（Walsh elimination）的过程。在标准的计算机模拟中，如果你想移除一个开关，你通常必须猜测它的值或忽略它，这可能会导致丢失正确答案。这项新技术做得更加精确。它观察一个特定的开关，并计算出其邻居每种可能排列下的最佳结果。然后，它用一组新的规则来替换涉及该开关的复杂规则，这些新规则描述了剩余开关的情况，从而有效地总结了被移除开关的影响，而无需将其保留在系统中。至关重要的是，计算机会在新规则旁边存储一份简单的指令表。这张表会告诉系统稍后如何重建被移除开关的位置，确保最终答案在数学上与该开关从未被移除时完全一致。这个过程是精确的；它既不进行近似，也不进行猜测。

研究人员在两类困难问题上测试了这种方法。第一类涉及每个开关恰好与另外三个开关相互作用的开关网络，这种设置被称为“稀疏自旋玻璃”（sparse spin glass）。第二类涉及三个开关同时进行的相互作用。在这些测试中，研究人员将标准方法与使用“模拟退火求解器”（一种模仿金属冷却过程以寻找稳定状态的算法）的新消除方法进行了对比。他们进行了数千次尝试，每次尝试都有固定的时间限制。结果令人震惊。对于三开关相互作用问题，找到最佳解决方案的成功率从约 17% 跳升至 87.5%。对于较简单的两开关问题，成功率从大约 10% 飙升至接近 98%。即使在考虑到计算机准备缩减问题所花费的时间后，这种提升依然成立。事实上，对于较简单的题目，寻找解决方案所需的时间降低了约 34 倍，而对于较复杂的题目，时间降低了约 11 倍。

为了确保这些收益并非特定测试案例的偶然现象，研究人员使用一套固定的协议生成了一组全新的问题，并在不改变任何设置的情况下再次进行了测试。这种改进依然存在。在每一个已知正确答案的新问题上，缩减后的模型比原始的未缩减模型能更频繁地找到解。研究人员还将他们的方法与另一种基于采样数据来固定开关值的技术进行了比较。那项旧技术有时会做出错误的猜测，从而彻底消除完美的解决方案。相比之下，这种新的消除方法从未做出错误的猜测；它在每一个案例中都保留了最佳答案的可能性，在移除 30% 到 40% 的开关的同时，仍保持了问题的可解性。

除了让现有机器运行得更好之外，这项研究还证明了一个理论极限，即问题可以变得多大。对于一类每个开关恰好连接三个开关的特定网络，研究人员证明了消除法总能至少移除三分之一的开关，同时保持规则的简单性和成对性。这意味着，一台具有固定容量（例如 16 个开关）的机器，理论上可以解决原本需要多达 24 个开关的问题。这在不构建更大硬件的情况下，显著扩展了可能性的范围。该方法通过确保移除开关后产生的新规则不会变得过于复杂来实现。研究人员对剩余开关可以拥有的连接数设定了严格限制，以确保问题仍处于当前求解器的能力范围内。

然而，研究也指出了该方法何时不再奏效。如果开关之间的连接过于密集，或者问题涉及四个或更多开关同时相互作用，那么移除开关的过程会产生难以高效处理的复杂新规则。在这种情况下，准备缩减问题的耗时会超过解决较小问题所节省的时间。该方法在连接稀疏的问题中表现最为出色。研究人员发现，对于四向相互作用的问题，准备时间过长，以至于原始的未缩减方法反而更快。这凸显了移除开关带来的收益完全取决于问题的结构以及所创建新规则的成本。

这项工作的意义不仅限于这些特定的测试。它表明，问题的表示方式对于计算机来说，与计算机的原始算力同样重要。通过改变问题的表示形式以适配机器的资源，而不是强迫机器去适应问题的复杂度，研究人员可以解决更大、更难的谜题。研究证实，精确的数学约减可以提高实际的优化效率，为解决那些原本由于硬件限制而无法处理的问题提供了一条路径。研究人员已将他们的软件开放给他人使用，允许科学界将这种精确的消除技术应用于他们自己的挑战中。结果表明，通过正确的数学工具，我们可以比之前预想的更进一步地推动当前计算硬件的极限——不是通过建造更大的机器，而是通过更聪明地利用我们现有的机器。