量子科技中心_量科网

该论文研究了向量域和矩阵域的无投影稀疏凸优化问题，该问题涵盖机器学习和数据科学中的大量重要应用。针对向量域𝒟⊂ℝ^d，该研究团队提出两种面向稀疏约束的量子算法，通过函数值预言机分别以O(d/ε)和O(1/ε)的查询复杂度找到ε最优解，相较最佳经典算法分别降低了O(d)和O(d)的复杂度因子，其中d为维度。对于矩阵域𝒟⊂ℝ^(d×d)，研究人员开发了两种核范数约束的量子算法，将更新步骤计算的时间复杂度提升至Õ(r d/ε^2)和Õ(r d/ε^3)，相较最优经典算法至少降低O(d)的复杂度因子，其中r为梯度矩阵的秩。这些算法在维度d的依赖性上超越了最优经典方法，展现了无投影稀疏凸优化问题中的量子优势。