受量子OR启发的稀疏半定规划次线性时间经典算法
基于论文摘要，作者提出有界半径稀疏半定规划的次线性时间经典求解器，不依赖低秩假设或约束矩阵的Frobenius范数。其方法将随机Lánczos滤波、Gibbs态采样估计与随机在线学习结合；当γ=时，运行时间为约O((n+m)s)，相对O(mns)输入规模为次线性。作者据此指出，通用稀疏半定规划在维数和约束数上不存在超二次的量子优势。
本站判断：这项工作针对稀疏半定规划在有界原、对偶半径下的经典求解复杂度，提出结合Gibbs态多期望值估计与随机在线学习的算法，并报告在给定稀疏度和精度条件下的次线性运行时间。基于论文摘要，其关键增量是把量子OR引理中的样本复用机制经典化；但证明细节、实验和完整资源开销尚未提供。本站设想：可在相同精度、半径和稀疏度条件下，与既有经典及量子基线比较端到端时间和内存开销。