量子科技中心_量科网

该研究团队提出了基于乘性权重更新方法（MW）的二阶锥规划（SOCP）近似求解经典与量子算法。该工作延续了先前应用于半定规划（SDP，SOCP为其特例）的MW框架，并证明通过利用SOCP特有结构可设计出具有更优运行时间的专用算法。对于包含m个线性约束、n个变量划分为r≤n个二阶锥的SOCP问题，其量子算法需对实例定义数据进行Oe(√rγ⁵ + √mγ⁴)次（相干）查询，其中γ为与精度倒数成比例的无量纲参数。该复杂度几乎与线性规划（LP，SOCP表达能力较弱的子集）求解相当，且显著优于直接套用现有SDP算法（复杂度Oe(γ⁴(n+γ√n+√m))）的朴素方法——尤其在n≫r时优势更明显。该团队提出的经典SOCP算法在采样-查询模型中具有Oe(nγ⁴ + mγ⁶)复杂度。