百团百项｜AI4S：智算院一年级博士生突破量子有序搜索k=6前沿

转载自：思源智算

量子计算能否在基础搜索问题上稳定超越经典算法，是量子信息科学中的核心问题之一。作为计算机科学中最基本的问题之一，有序搜索问题对应经典二分搜索的理论极限；而量子有序搜索则试图利用量子叠加与干涉机制，在查询复杂度上获得严格的常数因子加速。该问题不仅是量子算法理论中的经典基准，也长期被视为检验“量子优势”精细边界的重要模型问题。

近日，上海交通大学智能计算研究院在ai for science交叉研究方向取得重要进展。由上海交通大学人工智能学院一年级博士生吴彦成任第一作者的研究工作，围绕量子有序搜索问题，提出了一套面向大规模结构化半定规划的矩阵无关gpu优化方法，突破了该问题长期难以推进的k=6 查询计算前沿。该论文已被icml 2026 接收，标志着智算院在“高精度优化计算支撑ai4s”的方向上取得了具有国际显示度的重要成果。

在量子有序搜索问题中，核心目标是将查询复杂度从经典二分搜索的log

n 推进到 clog

n，其中常数 c2n*。此前国际已有工作将该问题推进到 k=5，得到 n*=7265，对应常数约为0.390；但当进入 k=6 时，半定规划约束规模急剧膨胀，显式构造和存储约束矩阵会产生远超现代高性能gpu承载能力的显存需求，使传统cpu/gpu求解器均遭遇难以跨越的“内存墙”。

针对这一瓶颈，吴彦成等人提出了矩阵无关的gpu半定规划优化框架。该方法不再显式生成大规模约束矩阵，而是深度利用量子有序搜索sdp约束中的toeplitz型、近循环型结构，通过定制cuda kernel在gpu上实时计算前向算子与伴随算子，将约束存储复杂度从近似二次规模降至线性规模，从根本上绕开显存瓶颈。论文实验表明，在 k=6,n=100000 的大规模实例上，前向算子和伴随算子的单次计算均约为71毫秒，显存开销仅约560mb，而显式存储相应约束矩阵则需要数tb级显存。

在算法设计上，该工作将低秩半定规划、增强拉格朗日方法、矩阵无关算子计算和gpu并行kernel深度结合。传统低秩sdp方法虽然能够降低变量矩阵本身的存储成本，但在 k=6 规模下，约束矩阵 a 的显式构造仍然不可承受。该研究的关键创新在于：不再把科学问题“翻译”为通用大矩阵再交给求解器，而是直接针对问题结构设计算子级计算路径，使gpu在不存储大矩阵的情况下完成约束评估、梯度计算和不可行性验证。

基于这一方法，研究团队在单张nvidia h100 gpu上完成了此前难以求解的 k=6 大规模实例计算。论文中从数值上证明 n=90000 时对应半定规划可行，并通过严格的对偶不可行性证书证明 n=94000 不可行，从而将 k=6 情形的最优列表规模夹定为

90,000≤n*

并将量子有序搜索的查询复杂度常数上界从此前约0.390推进至约0.365。

在论文工作的基础上，研究团队近期进一步推进了计算边界。根据最新计算结果，当前已经将 n*的候选范围进一步压缩到92529附近，相应查询复杂度常数进一步推进到 约0.364。这意味着该工作不仅首次突破了 k=6 的计算壁垒，而且仍在持续刷新量子有序搜索问题的已知上界，为进一步逼近该问题的真实量子复杂度边界提供了新的计算路径。

这一成果的重要意义不仅在于刷新了量子有序搜索这一经典问题的国际计算边界，更在于展示了ai4s中一条不同于纯数据驱动模型的重要技术路线：以高精度数学规划为核心，以gpu并行计算为底座，以科学问题的深层结构为抓手，直接推动基础科学问题的求解与证明。半定规划是量子信息、量子计算、量子化学、组合优化与控制理论中的核心计算工具，但长期受到内存复杂度、矩阵分解成本和通用求解器可扩展性的制约。该工作表明，通过面向科学问题结构的算子级建模与gpu原生实现，可以突破传统半定规划求解的规模瓶颈，为量子信息中的复杂可验证计算问题提供新的工具链。

从智算院的研究布局看，该成果是人工智能时代高精度高性能智能计算路线在量子信息领域的一次代表性突破。它将数学规划、半定优化、gpu体系结构和量子算法理论深度融合，体现了“ai4s不仅是大模型赋能科学，也包括用智能计算底座重构科学计算范式”的重要方向。未来，该类矩阵无关、结构感知、gpu原生的大规模优化框架，有望进一步推广到量子化学、量子态判别、纠缠检测、谱界估计和大规模组合优化松弛等更广泛的ai4s场景，成为支撑高精度科学计算的重要基础设施。

欢迎转发，但请注明出处“上海经信委”

上观号作者：上海经信委