上海交大团队用 GPU 求解器 cuLoRADS 解开 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 的另一项合作里，他们证明

来源只提供摘要，完整内容请打开原文。