
-
生物通官微
陪你抓住生命科技
跳动的脉搏
基于振荡器的伊辛机在大规模稀疏图最大割问题中的应用
《Scientific Reports》:Oscillator-based Ising machine applied for Max-Cut in massively large and sparse graphs
【字体: 大 中 小 】 时间:2026年08月28日 来源:Scientific Reports 4.9
编辑推荐:
摘要解决如最大割(Max-Cut)这样的大规模组合优化问题,对于网络分析和金融等各类应用至关重要。伊辛机作为一种非传统计算范式正在兴起,用于应对这些问题,与传统方法(如 Goemans-Williamson 算法)相比,有望降低能耗并缩短求解时间。在此,我们实现并基准测试了一
解决如最大割(Max-Cut)这样的大规模组合优化问题,对于网络分析和金融等各类应用至关重要。伊辛机作为一种非传统计算范式正在兴起,用于应对这些问题,与传统方法(如 Goemans-Williamson 算法)相比,有望降低能耗并缩短求解时间。在此,我们实现并基准测试了一种基于图形处理器(GPU)原生软件的基于振荡器的伊辛机(OIM)实现方案,该方案能够在度为 25 的正则图中解决多达 2000 万个自旋的最大割问题。经过基准测试的实现方案运行在单个 GPU 上,但可扩展至多 GPU 平台。此外,我们确定了一种退火策略,该策略利用动态检查点作为分岔点,在映射到伊辛哈密顿量的最大割问题的动态相空间中搜索基态,从而支持算法进行快速的局部搜索。对于 G 集问题,OIM 始终能实现平均高于 99.5%(最高达 99.9%)的精度。