量子科技中心_量科网

该研究团队提出了一个量子灵敏度采样的统一框架，将量子计算的优势扩展到广泛的经典近似问题领域。这一统一框架为构建核心集提供了高效方法，并在聚类、回归和低秩近似等应用中实现了显著的运行时改进。主要贡献包括： • k中位数与k均值聚类：针对d维欧几里得空间中的n个点，该工作提出的算法能在Õ(n^0.5dk^2.5poly(ϵ^-1))时间内构建ϵ-核心集。相比[Xue等，ICML'23]的最新成果，该方法实现了更好的维度d依赖度，且构建的核心集仅包含数据集中的点，规模更小。 • ℓp回归：对于ℓp回归问题，该团队构建了大小为Õ_p(d^{max{1,p/2}}ϵ^-2)的ϵ-核心集，耗时Õ_p(n^0.5d^{max{0.5,p/4}+1}(ϵ^-3+d^0.5))。该成果改进了[Apers等，QIP'24]提出的量子采样方法，适用于所有p∈(0,2)∪(2,22]情形，包括被广泛研究的最小绝对偏差回归（ℓ1回归）。 • 基于Frobenius范数误差的低秩近似：该团队首次提出不依赖数据相关参数的量子次线性时间算法，运行时间为Õ(nd^0.5k^0.5ϵ^-1)。此外，还提出了面向核低秩近似和张量低秩近似的量子次线性算法，扩展了随机数值线性代数中可实现次线性时间算法的范围。