日本研究人员推动组合优化问题求解进展

来自日本东京理科大学 (Tokyo University of Science) 电气工程系的研究人员已经开发出了一种 “a novel approach” 来解决组合优化问题 (COPs)。

组合优化问题 (COPs) 是计算上难以求解的问题，例如轮班排班、交通路线规划以及药物研发，这通常意味着它们不能在现实时间内得到解决。

尽管关于量子计算（该技术利用量子力学的独特性质有望解决此类问题）的进展已有大量讨论，但目前还有一种被研究的方法称为 Ising machine。

Ising machine 以物理学家 Ernst Ising 和 Wilhelm Lenz 的名字命名，是一种专门为解决组合优化问题而设计的定制硬件，其中问题中使用的数据以磁性自旋的形式呈现，而约束则被建模为自旋之间的相互作用。求解组合优化问题需要找到能够使系统能量最小化的自旋状态。

Ising 模型有两种类型：稀疏耦合模型和全耦合模型。稀疏耦合模型通过允许更多自旋展现出高度的可扩展性，但要求将组合优化问题转换以适应该模型；全耦合模型则使得任何组合优化问题都可以直接映射而无需转换，但它们在自旋数量方面容量有限，且以交互比特宽度衡量的精度也较低。

研究人员指出，虽然以往的研究已通过利用特定应用集成电路 (ASICs) 构建的可扩展结构实现了全 Ising 模型，从而提高了容量，但这些模型的交互比特宽度是固定的，这使得某些组合优化问题难以求解。

由川原孝之教授 (Takayuki Kawahara) 领导的日本研究团队开发出了一种 “innovative” 双重可扩展退火处理系统 (DSAPS)，该系统能够 “simultaneously scale both capacity and precision using the same scalable structure”。

退火处理器是为解决组合优化问题而构建的专用硬件。东京理科大学的团队证明，DSAPS 系统可以利用单个现场可编程门阵列芯片 (FPGA) 控制多个大规模集成电路 (LSIs)。

研究指出，这项工作标志着在开发可扩展、高精度全耦合 Ising machine 方面迈出了重要一步，并在多个领域展现出有前景的应用潜力。

川原教授表示：“该系统将对开发用于解决复杂现实组合优化问题的可扩展 APs 起到关键作用。”

今年早些时候，哥德堡大学 (University of Gothenburg) 的研究人员展示了一种采用现成微波元件构建的表面声波延迟线技术实现的 50 自旋 Ising machine。

当时研究人员表示，他们所采用的技术展示了一种构建节能且高性能、具有商业可行性的组合优化问题求解平台的方法。

目前有大量研究在探索利用 Ising machine 的不同方式。但与构成数字计算机基础的冯·诺依曼架构不同，现有的研究方法众多，这与量子计算领域的情况类似，说明目前还没有明确的最佳方案。然而，共同点在于各家都致力于提高 Ising machine 的能效并使用现有的芯片制造工艺来构建这些系统。