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

上海交通大学团队研发出 GPU 加速的半定规划求解器 cuLoRADS，通过挖掘问题低秩结构、重构核心计算流程、利用稀疏性优化存储等设计，大幅提升大规模半定规划的求解效率，在单张英伟达 H100 上求解千万阶矩阵相关问题仅需 10 秒到 1 分钟，远快于传统 CPU 求解器。该求解器成功解开悬而未决 18 年的量子有序搜索基础难题，明确 5 次查询对应的最大可搜索列表规模为 7265。团队还给出相关数学证明为低秩策略提供理论依据。该成果可应用于量子算法复杂度研究、量子化学分子基态能量计算、具身智能机器人实时轨迹规划等多个领域，印证了算法与硬件协同设计的显著优势，不过它仅适用于约束数据足够稀疏或有紧凑算子表示的大规模半定规划问题，在稠密非结构化、需高秩因子表示的问题上优势会减弱。