基于跃迁多态自旋的全并行退火处理系统：突破组合优化计算瓶颈的新路径

《IEEE Access》：Annealing Processing System Capable of Simultaneous Updates of All Spins Using Transition-Based Multi-State Spin

本文推荐一种新型退火处理器TMSPA，其通过引入跃迁多态自旋（TMS）机制，成功解决了全耦合伊辛模型因自旋状态同步更新导致的能量收敛不稳定难题。研究团队在最大割问题（Max-Cut）和旅行商问题（TSP）上的测试表明，该方法在保持解质量的同时可实现全并行计算，相比传统伪退火（PA）方法，2048自旋配置的FPGA系统计算速度提升6.25倍，电路资源利用率仅增加1.03-5.70倍，为实时组合优化问题提供了硬件实现新方案。

　　

在当今数字化社会中，组合优化问题（COPs）如同隐形的调度大师，渗透在物流路径规划、排班调度、金融投资组合等众多领域。然而这类问题多数属于NP难问题，其解空间随问题规模呈指数级膨胀——以经典的旅行商问题（TSP）为例，当城市数量n增加时，可能路径数高达(n-1)!/2，传统计算机通过暴力搜索寻找最优解犹如大海捞针。这一困境催生了退火处理器（APs）的兴起，其通过将目标函数映射为伊辛模型中的自旋相互作用，利用物理系统能量最小化原理寻找最优解，但全耦合型APs因自旋更新需顺序进行，始终难以兼顾计算速度与解质量的双重需求。

为解决这一矛盾，东京科学大学的研究团队在《IEEE Access》发表了创新性研究，提出了一种基于跃迁多态伪退火（TMSPA）的全并行退火处理系统。该研究的核心突破在于设计了跃迁多态自旋（TMS spin）结构，通过将传统±1二态自旋扩展为离散中间态，并将自旋翻转与否映射为不同方向的态跃迁。例如在8态TMS自旋中，自旋值可设置为{±1, ±0.875, ±0.5, 0}，通过算术右移和加法替代乘法运算，显著降低了硬件实现复杂度。

关键技术方法包括：1）构建支持全并行更新的线性模块架构，每个自旋配备独立乘累加（MAC）单元和状态寄存器；2）采用Δσ_j驱动计算法，仅对发生状态变化的相邻自旋进行能量增量计算；3）基于FPGA实现1024/2048自旋配置，通过AXI4-Stream接口实现J_ij矩阵高效加载；4）设计多模式调度控制器，支持初始化、退火执行、结果输出等状态切换。

研究结果分析

最大割问题验证：在K2000全耦合图测试中，16态TMSPA在p=N（全并行）时获得最佳切值32535，较模拟退火（SA）提升2.2%。而稀疏耦合图G46的测试显示，当自旋态数增至16时出现解质量分化现象，表明耦合权重分布影响并行更新稳定性。

旅行商问题性能：针对burma14问题，16态TMSPA将约束满足率提升至100%，且最优解距离已知最优解仅0.4%。值得注意的是，线性退火调度下解质量明显低于指数调度，凸显了终末阶段缓降温对多态自旋收敛的重要性。

硬件效能表现：FPGA实现结果显示，2048自旋系统在100MHz频率下单次蒙特卡洛步仅需4-2052时钟周期。与同类工作NoCAPA相比，1024自旋配置在G46问题上实现6.25倍加速，且LUT资源利用率仅为前者的1.03倍。通过将S₁/S_-1设为0值，成功消除了自旋在正负态间跃迁的重复计算开销。

讨论与展望

该研究揭示了TMSPA性能与问题结构的深层关联：对于耦合权重均匀分布的K2000，较少自旋态更利收敛；而具有块状耦合特征的TSP问题则需要更多自旋态实现约束满足。这种差异源于TMS自旋在中间态振荡时产生的“动量效应”，有助于逃离局部最优解。相比需要复制自旋和自相互作用的随机元胞自动机退火（SCA），TMSPA保持了标准伊辛模型能量函数形式，使算法复杂度与伪退火（PA）基本相当。

这项工作的现实意义在于打通了全并行退火从算法创新到硬件落地的完整路径。通过巧妙的离散态设计，在FPGA上实现了超过2000自旋的全耦合系统，为物流调度、金融风险控制等实时优化场景提供了低成本解决方案。未来通过扩展J_ij比特宽度并优化温度调度策略，有望在蛋白质折叠、药物分子设计等生命科学领域发挥更大价值。