🔬 物理学

Omnisolver: An extensible interface to Ising spin-glass and QUBO solvers: adding a distributed GPU brute-force plugin

本文介绍了 \texttt{omnisolver-bruteforce}，这是 Omnisolver 框架的一个新插件，它通过统一的接口、基于 Ray 的任务拆分架构以及数值稳定性技术，实现了在分布式 CUDA GPU 上对 QUBO 和 Ising 实例进行精确的穷举搜索，并能在高达 60 个变量的情况下获得与理论缩放法则高度一致的地面真值解。

原作者： Konrad Jałowiecki, Jakub Pawłowski, Bartłomiej Gardas, Łukasz Pawela

发布于 2026-10-09

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Konrad Jałowiecki, Jakub Pawłowski, Bartłomiej Gardas, Łukasz Pawela

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代计算的广袤版图中，存在着一类极其复杂的难题，寻找单一最优解的过程，感觉就像是在一片随着每一步移动而翻倍扩大的沙漠中，寻找一颗特定的沙粒。这些是优化挑战，通常被建模为相互作用的部分组成的网络，其目标是排列这些部分以达到最低可能的能量或成本状态。科学家和工程师使用这些模型来理解从原子层面的材料行为到交通调度或金融投资组合管理的一切事物。几十年来，解决这些谜题最可靠的方法是检查每一个可能的排列组合，这种方法被称为穷举搜索。然而，随着部件数量的增加，可能排列的数量会呈爆炸式增长，以至于即使是世界上最强大的超级计算机也无法在人类的一生内完成这项工作。这造成了一个关键的空白：如果没有一种方法来找到绝对的最佳答案，研究人员就无法确定他们用来寻找“足够好”答案的巧妙捷径是否真的接近真相。

来自波兰的一个研究小组现在开发了一种新工具，旨在为特定范围的困难问题填补这一空白。他们创建了一个软件更新，将标准的图形处理器（即高端游戏和视频电脑中常见的显卡）变成了一台能够检查包含多达六十个部件问题的所有可能排列的机器。通过将这种原始的检查能力与一种在多台计算机之间分配工作的系统相结合，他们成功找到了以前因规模过大而无法完全解决的问题的完美解。这一成就提供了一个“金标准”答案，其他更快的计算机程序可以针对该答案进行测试，从而让科学家能够验证他们的捷径是否真正奏效，或者是否完全遗漏了最佳解。

这项工作的核心是一个名为 Omnisolver-bruteforce 的软件插件，它充当了不同类型计算机求解器的通用翻译器。把它想象成一把万能钥匙，让研究人员可以接入各种工具来应对同一个问题。研究人员利用了一个现有的工具，该工具可以在单张图形处理器上检查所有可能性，并将其升级为可以在八张强大的图形处理器网络中协同工作。他们通过将庞大的搜索空间分解为较小的、独立的区块来实现这一点。想象一下一个图书馆，你需要找到一本特定的书；与其让一个人检查所有的书架，不如将任务分配给八个人同时检查不同的区域，并在发现目标时报告回来。在这种情况下，“图书馆”是问题的所有可能排列，而“搜索者”则是并行工作的图形处理器。

研究人员在一个由八张高性能图形处理器组成的集群上测试了这个新系统，每张显卡都拥有大量的内存。他们设置系统去解决这些优化问题的随机版本，将问题规模从四十个部件逐渐增加到六十个部件。结果令人瞩目。对于拥有六十个部件的问题，系统大约需要三天时间来检查每一种可能性并确认最佳答案。这听起来可能很长时间，但如果没有这种新方法，这项任务在合理的时间内是不可能完成的。研究人员观察到，对于问题中每增加一个部件，解决问题所需的时间大约会翻倍，这一模式在他们所有的测试中都成立。这种可预测的行为证实了他们的系统正完全按照物理学和数学定律所规定的方式运行。

一项重要的创新在于确保计算机在进行如此大规模的工作时不会犯下微小的错误。图形处理器的设计初衷是追求速度，往往以牺牲极高的精度为代价，这可能导致微小的误差随时间累积。研究人员开发了一种方法，可以在这些微小误差发生时自动进行纠正，从而确保最终答案在数学上是精确的。他们通过将结果与较小规模问题的已知完美解进行对比来验证这一点，发现答案精确到了最后一位数字。这种可靠性水平至关重要，因为该工具并非旨在解决企业的日常问题，而是作为参考点。它允许科学家测试新的、更快的算法——例如受量子物理学或生物系统启发的算法——以观察它们是真的找到了最佳解，还是仅仅在进行猜测。

该研究还展望了更大规模计算机集群可能实现的可能性。研究人员计算出，如果他们能够连接两百一十六张图形处理器，他们只需三十三秒即可解决一个拥有六十个部件的问题。他们进一步估计，拥有这样一个庞大的网络，理论上可以在一个月内解决多达七十六个部件的问题。然而，他们谨慎地指出，这些都是基于当前数据的预测，现实世界的因素（如计算机之间的通信延迟）可能会改变确切的数字。由于软件处理计数排列的方式，目前的系统限制在六十四个部件以内，但在该限制范围内，它能提供一个确定的答案。

这项工作并不声称解决了所有的优化问题，也不建议用穷举搜索来取代日常使用的更快速、更近似的方法。相反，它提供了一种认证那些更快方法质量的方式。通过为一定规模的问题提供一个保证正确的答案，研究人员为新技术的准确性提供了一把衡量尺。随着计算领域向更复杂的挑战迈进，拥有一个能够明确说出“这就是最佳答案”的工具，成为了一个不可或缺的基准。研究人员已将他们的软件开放给他人，邀请整个科学界使用这种新能力来验证他们的发现，并推动计算能力的边界。

技术摘要：Omnisolver-Bruteforce 插件

问题陈述
本文针对二次无约束二元优化（QUBO）和 Ising 自旋玻璃实例对于经过认证的真值解（ground-truth solutions）的需求进行了研究。虽然启发式方法（如模拟分叉机，Simulated Bifurcation Machine）和量子退火器已被广泛使用，但其性能必须针对精确最优解进行基准测试。以往的穷举求解器通常是缺乏与现代求解器框架集成的独立工具。此外，现有的基于 GPU 的穷举求解器面临两个特定的局限性：它们受限于单设备执行，且其“快速路径”（利用 float32 算术实现高吞吐量）在问题规模 $N \ge 40$ 时会遭受数值漂移（舍入误差）的影响，从而损害了所报告的基态能量的准确性。

方法论
作者引入了 omnisolver-bruteforce，这是现有 Omnisolver 框架的一个插件。该方法集成了三个核心技术组件：

统一接口： 将先前工作 [2] 中的单 GPU 穷举内核重新封装为一个一等公民插件。它提供了一个与 dimod 兼容的统一 Python 和命令行界面（CLI），并返回带有运行时元数据的 dimod.SampleSet 对象。
分布式执行： 为了克服单 GPU 内存和时间的限制，作者使用 Ray 实现了一个分布式框架。通过固定 $k$ 个变量来分解搜索空间，从而创建 $2^k$ 个独立的子问题，每个子问题包含 $N-k$ 个未固定的变量。这些子问题被分发到多个 GPU 和主机上。控制节点负责聚合部分结果。
数值稳定性： 为了在保持 float32 算术高吞吐量的同时确保准确性，该插件采用了以下技术：
- 补偿增量更新（Compensated incremental updates）。
- 周期性的精确能量重锚定（使用 float64 重新评估能量）。
- 最佳缓冲区刷新机制（Best-buffer refresh mechanisms）。
  这些稳定性技术在 $N \ge 40$ 时会自动激活。

性能关键的内核使用 CUDA/C++ 编写，并通过 Cython 暴露给 Python。该实现支持 64 位安全的位操作，以处理超出原始单 GPU 范围的问题规模。

主要贡献

一等公民插件： 将穷举 GPU 求解器集成到 Omnisolver 生态系统中，并具备一致的 API。
可扩展的分布式搜索： 基于 Ray 的架构使得对单设备无法处理的问题规模进行穷举搜索成为可能，并实现了接近线性的强扩展性。
稳定的快速路径： 消除了大 $N$ 时 float32 导致的数值漂移，且未牺牲单精度算术的吞吐量优势。
验证： 通过与 dimod.ExactSolver 进行全面测试，并利用 float64 重计算来验证能量的准确性。

结果
作者在包含 8× NVIDIA H100 GPU（每块 96 GB）的本地集群上评估了该插件。

性能扩展： 分布式采样器在 $N=40$ 到 $N=42$ 之间跨越了单 GPU 性能平衡点。从 $N \gtrsim 44$ 开始，它实现了预期的来自 8-GPU 池的约 $\approx 8\times$ 的加速。
穷举极限： 该系统成功地在分布式模式下解决了高达 $N=60$ 的全连接随机 Ising 实例，耗时约 3.15 天。这符合经验性的倍增法则（ $t_{N+1} \approx 2t_N$ ）。
准确性： 对于测试的最大规模实例（ $N=56, 58, 60$ ），报告的 float32 能量与 float64 重计算能量之间的绝对偏差保持在 $4 \times 10^{-6}$ 以下。
基准测试效用： 该插件成功为同时测试了模拟分叉机（SBM）的实例认证了精确基态。SBM 的解与穷举结果在比特层面是完全一致的（汉明距离为 0），能量差异仅归因于单精度舍入误差。

意义与范围
论文将 omnisolver-bruteforce 定位为验证与认证后端，而非用于应用级问题的常规优化器。其主要意义在于提供用于以下用途的真值最优解：

基准测试近似和启发式方法（例如 SBM）。
验证面向 NISQ 的工作流。
评估关于量子运行时优势（quantum runtime advantage）的说法。

作者明确指出， $O(2^N)$ 的复杂度保持不变。更新过程减少了常数因子并消除了数值陷阱，但并未改变根本的计算复杂度。目前的实现存在硬性限制：由于 64 位自旋索引，限制为 $N \le 64$ ，且子问题规模受限于 GPU L2 缓存预算。作者提出的未来工作包括向用户开放稳定性参数、实现层次化归约以更好地扩展到大规模工作节点数量，以及发布可复现性胶囊（reproducibility capsules）。

技术摘要：Omnisolver-Bruteforce 插件

类似论文