GPU求解器cuLoRADS解开18年量子有序搜索难题
据MIT科技评论中文援引PNAS论文,上海交通大学团队用GPU加速的求解器cuLoRADS直接解出了5次量子有序搜索查询对应的完整半定规划,确认可搜索的最大有序列表长度为7265,而长度7266时该方案不可行。相关半定规划规模在此前18年间随列表长度呈平方级增长,超出了当时所有CPU求解器的能力范围。论文数据显示,在单张英伟达H100上求解一组千万阶最大割半定规划松弛只需10秒到1分钟,而此前报道的CPU方法往往需要数十小时。
cuLoRADS为量子、量子化学与具身智能研究提供了可直接使用的优化工具,展示了科学计算中算法与硬件协同设计的路径。
一个在量子信息领域悬了 18 年的难解之题,竟然被一张 GPU 解开了。这个问题叫做量子有序搜索,属于量子算法复杂度研究领域的一个基础问题。近日,上海交通大学团队用 GPU 加速的求解器 cuLoRADS 直接解出了 5 次查询对应的完整半定规划(SDP,Semidefinite Programming),确认了最大可搜索列表规模是 7265,相关论文发表在 PNAS 上。
过去 18 年间,相关半定规划问题的规模随着搜索列表长度呈现出平方级增长,这超出了所有 CPU 求解器的能力范围。
半定规划是一类数学优化方法,在组合优化、机器学习、控制和量子科学里都有一定的应用。它的建模能力非常强,计算代价也很高。规模一旦变大,传统方法就会解不动。cuLoRADS 则把这类问题的求解搬到了 GPU 上,同时根据 GPU 的特点重新设计了核心计算流程。
打个比方来说,传统 CPU 求解器在处理半定规划的时候,就像一个班主任逐条核对成绩表,一条一条地来,不仅速度慢,内存也非常吃紧。cuLoRADS 则是把成绩单摊开,让 GPU 上的成千上万个小核心在同一时间开工,各自去算一部分。论文数据显示,在单张英伟达 H100 GPU 上,当求解一组千万阶矩阵的最大割半定规划松弛问题之时,只需要 10 秒到 1 分钟时间,而此前报道的 CPU 方法往往需要数十小时。
#cuLoRADS#Shanghai Jiao Tong University#PNAS#NVIDIA H100#Google Quantum AI#Nanjing University#Stanford University#MIT#MaxCut#NVIDIA