上交团队用GPU优化算法，解开18年未解量子难题

一个在量子信息领域悬了 18 年的难解之题，竟然被一张 GPU 解开了。这个问题叫做量子有序搜索，属于量子算法复杂度研究领域的一个基础问题。近日，上海交通大学团队用 GPU 加速的求解器 cuLoRADS 直接解出了 5 次查询对应的完整半定规划（SDP，Semidefinite Programming），确认了最大可搜索列表规模是 7265，相关论文发表在 PNAS 上。

过去 18 年间，相关半定规划问题的规模随着搜索列表长度呈现出平方级增长，这超出了所有 CPU 求解器的能力范围。

半定规划是一类数学优化方法，在组合优化、机器学习、控制和量子科学里都有一定的应用。它的建模能力非常强，计算代价也很高。规模一旦变大，传统方法就会解不动。cuLoRADS 则把这类问题的求解搬到了 GPU 上，同时根据 GPU 的特点重新设计了核心计算流程。

打个比方来说，传统 CPU 求解器在处理半定规划的时候，就像一个班主任逐条核对成绩表，一条一条地来，不仅速度慢，内存也非常吃紧。cuLoRADS 则是把成绩单摊开，让 GPU 上的成千上万个小核心在同一时间开工，各自去算一部分。论文数据显示，在单张英伟达 H100 GPU 上，当求解一组千万阶矩阵的最大割半定规划松弛问题之时，只需要 10 秒到 1 分钟时间，而此前报道的 CPU 方法往往需要数十小时。

这个对比背后基于这样一个关键的设计思路，研究团队没有采取直接把 CPU 程序移植到 GPU 上的做法，他们先是找到了这类问题里面可以利用的低秩结构。半定规划的最优解通常可以用一个很小的矩阵因子来表示，无需存下整个巨大的矩阵。这样一来，存储需求就会得到大幅下降，计算也可以被拆成适合 GPU 并行处理的小块任务。

（来源：PNAS）

本次论文还给了一个数学证明，说明对于一般的半定规划问题，总是能够找到一个规模不大的近似解，这个结论为低秩策略提供了一定依据，也让求解器在处理大规模问题时拥有了更加明确的方向。

具体到落地应用，cuLoRADS 能被用在量子有序搜索之中。当量子计算机查找一个有序列表里的目标元素的时候，理论上要比经典计算机更快。但是这个优势到底有多大，最优常数到底是多少，一直以来都是一个难题。

2007 年，有科学家把这个问题转化成一个半定规划问题来研究。人们发现到了第 5 次查询这个场景的时候，问题规模会随着列表长度呈现出平方级增长，这被学界认为超出了当时半定规划求解器的能力范围。

cuLoRADS 直接解出了这个完整的半定规划，本次团队算出了 5 次查询能搜索的最大列表长度是 7,265，与此同时也算出当长度是 7,266 时这个方案就会行不通。

长远来看，本次成果解决的是 AI for Science 里一个非常容易被忽略的层面。当人们讨论使用 AI 加速科学发现的时候，注意力一般放在大模型和算法上，但其实底层优化计算的能力同样重要。

对于量子化学来说要算分子能量，对于具身智能来说要做轨迹规划，对于量子算法来说要验证复杂度上界，这些任务的背后都指向了半定规划这类数学工具。而这个工具能够处理多大规模的问题，直接决定了上层研究到底能走多远。

（来源：PNAS）

论文里还讲到了这样一个细节，半定规划里面有一个核心操作叫线性映射，它计算的是约束矩阵和变量矩阵之间的内积。传统做法是一条约束接着一条约束地算，可在 GPU 上这样做会反复启动大量小核函数，以至于开销会非常大。本次团队把它改成两个大的核函数，其中一个负责构造矩阵乘积，另一个负责计算线性映射。

另一个细节是关于存储压缩的，采用低秩方法虽然可以省内存，但是中间过程还是需要构造一个完整的向量。面对边长为五十万的矩阵，这个向量在双精度下需要 1.8 TB 以上的内存，显然不太现实。为此，本次团队使用稀疏性来规避这个问题，仅仅计算那些在约束矩阵里有非零对应的分量，避免分配以及操作整个大向量。

从应用角度来看，这项工作跨越了好几个方向。对于量子有序搜索来说，它本身是一个纯理论问题，这个问题研究的是量子算法在查找有序列表时的最优复杂度。2007 年有科学家发现，这个问题能够被写成半定规划，但是当时能解的规模非常有限。

18 年过去了，这个问题一直卡在那里，虽然在理论上已经有人想到了解法，但是在计算上一直做不到。cuLoRADS 则把这个瓶颈给打开了，它通过把 5 次查询的完整半定规划直接解了出来。这对量子算法领域是一个明显的推进，也给未来更高次查询的研究提供了工具。

（来源：PNAS）

此次成果在量子化学方向的应用则更加实际一些。分子基态能量的计算是量子模拟里的核心任务之一，也是药物设计以及材料研究的基础。使用半定规划去估计基态能量的下界，是量子化学里的一条技术路径。在研究团队和 Google Quantum AI 的另一项合作里，他们证明了 cuLoRADS 已经进入这个领域的具体研究流程，不再只是算一些抽象的问题。

这一成果还能用于具身智能，机器人做轨迹规划以及模型预测控制，本质上是在约束条件之下寻求一个最优解。约束越多的时候，问题也就越复杂，求解速度也就越关键。假如一次规划要算好几秒，机器人就没有办法在动态环境里实时反应。而当 cuLoRADS 把这类问题的求解速度提上来之后，在机器人控制中那些以前算不动的问题就有了实际落地的可能。

另据悉，本次论文第一作者在本科阶段就参与了这项工作，现在在美国麻省理工学院读博士。通讯作者来自上海交通大学安泰经济与管理学院和智能计算研究院，合作者包括南京大学和美国斯坦福大学的学者。他们从管理科学的基础方法出发，延伸到量子科学、量子化学以及具身智能，这种跨方向的合作也是本次工作的一个亮点。

不过，cuLoRADS 也有它的适用边界。论文指出这套方法最适合那些约束数据足够稀疏、或者有紧凑算子表示的大规模半定规划问题。对于稠密或者非结构化的问题，它的优势会有所减弱。当问题需要更高秩的因子来表示的时候，低秩方法在内存和速度上的好处也会随之下降。

对做科学计算的从业者来说，本次成果提供了一个可以直接使用的工具，也提供了一个新的思路：算法和硬件能够被一起设计。在过去很多年里，算法研究归算法研究，硬件优化归硬件优化，两边等于是各走各的路。

最近几年开始，尤其是从深度学习开始，人们慢慢地意识到，算法和硬件协同设计能够带来单靠一边做不到的提升，cuLoRADS 正是这种思路在数学优化领域的又一次验证。

参考资料：

https://www.pnas.org/doi/epdf/10.1073/pnas.2516128123

注：封面由 AI 辅助生成