🔬 applied physics

Convolutional Formulation of Large-Scale Quadratic Unconstrained Binary Optimization with Dense Interactions

本文引入了空间二次无约束二值优化（spQUBO），这是一种卷积形式，能够在利用快速傅里叶变换实现可扩展计算的同时，为空间光子伊辛机提供高效、无需复用实现的密集相互作用问题解决方案。

原作者： Hiroshi Yamashita, Hideyuki Suzuki

发布于 2026-06-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Hiroshi Yamashita, Hideyuki Suzuki

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

想象你有一个巨大且复杂的拼图。你需要排列成千上万个碎片（我们称之为“自旋”），以找到解决问题的完美模式，比如组织一座城市或对照片进行分组。通常，解决这个问题需要一台超级计算机来检查每一个碎片之间所有可能的连接。如果你有 10,000 个碎片，连接的数量会爆炸式增长，使得过程变得极其缓慢且昂贵。

这篇论文介绍了一种思考这些拼图的新方法，使得一种特殊的“光学计算机”（称为空间光子伊辛机，或 SPIM）能够更快地解决它们。

以下是使用简单类比对他们想法的拆解：

1. 问题：“密集网络” vs. “光束”

把 SPIM 想象成一台利用光来解决拼图的机器。光之所以神奇，是因为它可以同时处理很多事情（并行性）。然而，这台机器有一个局限性：它天生根据碎片之间的距离来感知连接，就像池塘里的涟漪一样。

旧方法： 为了解决那些由碎片以混乱、随机方式连接而成的复杂问题（即“密集网络”），研究人员不得不使用一种叫做“多路复用”的技巧。想象一下，试图把一个巨大的、缠绕在一起的毛线球塞进一个小盒子里。这样做虽然可行，但它占用了大量空间并减慢了机器的速度。
论文的洞察： 作者意识到，这台机器实际上并不需要去“挤压”毛线。如果你以一种特定的、有序的方式排列拼图碎片，机器的自然“光之视觉”就能完美地解决问题，而无需任何挤压手段。

2. 解决方案：“空间 QUBO”（网格城市）

作者发明了一种编写这些拼图的新方式，他们称之为 spQUBO（空间二次无约束二进制优化）。

类比： 想象你的拼图碎片不仅仅是随机漂浮在空间中；它们被放置在一个巨大的、完美的网格上（就像带有街道和纵横路的城市地图）。
规则： 在这种新格式中，两个碎片之间的“成本”或“相互作用”仅取决于它们之间的距离。如果两个碎片相距 3 个街区，无论它们在地图上的什么位置，它们的相互作用方式都是完全相同的。
为什么这有帮助： 这种“基于距离”的规则恰恰是光所表现出的自然特性。光波呈圆形扩散；它们并不关心物体的具体身份，只关心它们之间的距离。通过将问题强制转化为这种“网格城市”格式，光学计算机可以使用一次闪光来解决问题，而无需使用那些缓慢的“挤压”技巧。

3. 魔术技巧：将 3D 世界扁平化为 2D

许多现实世界的问题（如数据聚类或设施布局）发生在 3D 甚至更高维度。然而，SPIM 是一个扁平的 2D 设备（就像一张纸）。

论文的声明： 作者证明了一个数学上的“魔术技巧”。他们展示了你可以将任何高维度的拼图扁平化到 2D 网格上，而不会丢失“距离规则”。
类比： 想象你有一个 3D 雕塑。通常，你无法把它放进一张 2D 的纸上。但本文指出：“如果你把雕塑切成薄片，并按照特定模式铺设在纸上，这张 2D 图画仍然保留了所有的 3D 信息。”
结果： 你现在可以将一个复杂的、高维度的难题扁平化到 SPIM 的 2D 表面上，并利用光瞬间解决它，同时保持这种“基于距离”的结构完整。

4. 他们测试的现实世界案例

作者不仅做了数学推导，还针对两类特定问题进行了测试：

“设施布局”问题： 想象你是一名城市规划师，正在决定在哪里开设新的咖啡店。你希望它们分布得足够开，以免产生竞争（靠得太近），但你也希望它们处于良好的位置。论文展示了如何将此映射到他们的网格上，使光机能自动找到最佳位置。
“聚类”问题： 想象你有一个巨大的相册，想要将照片分类（例如，“海滩”、“山脉”、“派对”）。论文展示了如何将这些照片布置在网格上，使机器根据它们在内容上的“距离”自然地将相似的照片归为一类。

5. 加分项：常规计算机上的快速计算

即使你没有这种高端的光学机器，这种编写拼图的新方式对常规计算机也有帮助。

类比： 通常，计算所有碎片之间的连接就像是在体育场里检查每一对人之间的关系（非常慢）。因为作者的方法依赖于“距离规则”，所以你可以使用一种数学捷径（称为快速傅里叶变换）来更快地计算一切。这就像是意识到与其逐一清点每一个人，不如直接计算行数和列数再进行乘法运算。

总结

该论文声称，通过将复杂的优化问题重新格式化为“基于网格、仅基于距离”的风格（spQUBO），我们可以：

释放光学计算机（SPIM）的全部潜力，去解决密集的复杂问题，而不会降低其速度。
高效地将高维问题扁平化到 2D 表面。
利用数学捷径加速计算，无论是对于光学机器还是常规数字计算机。

他们证明了这种“网格城市”方法在涉及设施布局和数据分组的问题中是行之有效的，证明了这种方法是应对困难优化难题的一种强大新途径。

技术摘要：具有稠密相互作用的大规模二次无约束二值优化问题的卷积表述

问题陈述
大规模组合优化问题（通常表述为二次无约束二值优化（QUBO）或 Ising 问题）在硬件求解器上的实现面临显著的扩展性挑战。虽然空间光子 Ising 机（SPIM）通过光学空间并行性为处理稠密相互作用提供了卓越的扩展性，但其原始实现被限制于表示秩为一的耦合矩阵。尽管已提出了用于处理高秩相互作用的多路复用版本，但这些版本引入了降低实现效率的多路复用成本。现有的将通用 QUBO 映射到 SPIM 的方法往往无法利用现实世界问题中固有的空间结构，导致光学硬件的空间体积利用率低下。本文旨在解决的核心挑战是：明确非多路复用型 SPIM 的内在表示能力，并确定一种能够高效实现稠密、结构化相互作用而不牺牲扩展性的表述方法。

方法论
作者引入了 空间 QUBO (spQUBO)，这是一种将变量与 $D$ 维整数格点相关联、并将相互作用定义为空间卷积结构的 Ising 问题表述。在该框架下，两个变量之间的耦合权重取决于它们的相对空间位置，而非任意索引。

关键方法组成部分包括：

spQUBO 定义： 该问题由空间耦合函数 $f(\mathbf{d}_i - \mathbf{d}_j)$ 定义，其中 $\mathbf{d}_i$ 代表第 $i$ 个变量的网格位置。这种结构自然地捕捉了基于距离的相互作用。
与 SPIM 的等价性： 作者证明了理想化 SPIM 的哈密顿量精确对应于一个二维周期性 spQUBO。SPIM 中的耦合系数由用于光学设置的参考图像的离散傅里叶变换 (DFT) 决定。
归约算法： 一个核心贡献是提出了一个归约算法，该算法可以将任何 $D$ $D$ 维 spQUBO（无论是周期的还是非周期的）转换为等效的二维周期性 spQUBO。这是通过以下方式实现的：
- 使用“填充”扩展配置域，以解决周期性冲突（即不同的相对位置映射到同一个周期性索引）。
- 使用特定的双射将高维网格坐标映射到二维网格，该双射保持了卷积结构。
- 最终的空间体积由原始维度乘积加上相互作用函数的局部性决定。
计算效率： 本文确立了 spQUBO 的卷积结构允许使用快速傅里叶变换 (FFT) 高效计算哈密顿量和矩阵-向量乘积，将计算复杂度从 $O(N^2)$ 降低到 $O(V \log V)$ ，其中 $V$ 是空间体积。

主要贡献

spQUBO 表述： 本文定义了一类以空间卷积结构为特征的新型 QUBO 问题，明确地将其与 SPIM 的物理能力联系起来。
理论归约： 证明了任何 spQUBO 都可以归约为二维周期性 spQUBO，同时保持卷积结构，从而能够在无需多路复用的情况下在单次触发的 SPIM 上实现。
扩展性分析： 作者通过对比 spQUBO 与空间多路复用及自旋对映射进行了扩展性分析。研究表明，对于具有空间结构和稠密相互作用的问题，随着相互作用局部性的增加，spQUBO 方法所需的空间体积（SLM 尺寸）明显小于通用的映射方案。
数值验证： 研究通过放置问题（最大化效用并考虑基于距离的惩罚）和聚类问题（最小化簇内距离）的数值示例展示了该框架的适用性。这些问题被成功映射到二维 spQUBO 并使用动量退火法求解。

结果

实现可行性： 归约算法成功地将复杂的、高维的问题（如 3D 聚类）转化为适用于 SPIM 硬件的二维周期形式。
性能比较： 在数值实验中，针对一个聚类实例，所提出的 spQUBO 方法仅需约 $1.4 \times 10^5$ 的空间体积，而空间多路复用需要 $2.4 \times 10^7$ ，自旋对映射则需要约 $1.2 \times 10^7$ 。
计算速度： 对哈密顿量计算时间的数值比较显示，基于 FFT 的 spQUBO 方法在随问题规模 ( $N$ ) 增长时的扩展性显著优于直接矩阵-向量乘法，证实了理论上的效率提升。
解的质量： 放置和聚类问题的近似解表现出了预期的行为，例如设施通过间隔分布以避免效用损失，以及数据点被分组到不同的簇中。

意义与主张
本文声称推进了对 SPIM 在效率和扩展性方面具有独特优势的特定类问题的理解。通过明确指出 SPIM 的内在能力在于处理具有卷积结构的稠密相互作用，这项工作超越了秩一矩阵的局限性，且无需承担多路复用的开销。

作者断言，spQUBO 表述为增强 SPIM 在具有空间或距离特征（如设施放置、聚类和图像复原）的实际现实问题中的适用性提供了基础性步骤。他们强调，虽然本研究侧重于理想化的 SPIM 以隔离空间体积约束，但该框架提供了一种在光学硬件上实现稠密、高维问题的系统化方法。此外，论文指出 spQUBO 的效率不仅限于光学硬件；其卷积结构使得在数字计算机上通过 FFT 进行高效计算成为可能，暗示了其在硬件和软件求解器方面的广泛用途。研究结论指出，未来的研究应探索将 spQUBO 与多路复用技术相结合，并应用统计机器学习来利用稠密相互作用模型中减少的自由度。

1. 问题：“密集网络” vs. “光束”

2. 解决方案：“空间 QUBO”（网格城市）

3. 魔术技巧：将 3D 世界扁平化为 2D

4. 他们测试的现实世界案例

5. 加分项：常规计算机上的快速计算

总结

类似论文