arXiv · quant-ph· Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén, Francisca Vasconcelos·· 8 天前精选
受量子OR启发的稀疏半定规划次线性时间经典算法
Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
arXiv:2609.40302v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén, Francisca Vasconcelos
首次提交：2026-10-01 01:51
研究任务与主要进展
基于论文摘要，作者提出有界半径稀疏半定规划的次线性时间经典求解器，不依赖低秩假设或约束矩阵的Frobenius范数。其方法将随机Lánczos滤波、Gibbs态采样估计与随机在线学习结合；当γ=时，运行时间为约O((n+m)s)，相对O(mns)输入规模为次线性。作者据此指出，通用稀疏半定规划在维数和约束数上不存在超二次的量子优势。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
本站判断
这项工作针对稀疏半定规划在有界原、对偶半径下的经典求解复杂度，提出结合Gibbs态多期望值估计与随机在线学习的算法，并报告在给定稀疏度和精度条件下的次线性运行时间。基于论文摘要，其关键增量是把量子OR引理中的样本复用机制经典化；但证明细节、实验和完整资源开销尚未提供。本站设想：可在相同精度、半径和稀疏度条件下，与既有经典及量子基线比较端到端时间和内存开销。
来源：arXiv · quant-ph · arxiv.org