Sublinear Time Quantum Sensitivity Sampling¶

会议: NeurIPS 2026
arXiv: 2509.16801
领域: 优化算法
关键词: 量子算法, 敏感度采样, 核心集构建, 次线性时间算法, 低秩逼近

一句话总结¶

针对大规模数据摘要与逼近问题，本文提出了一个通用的量子敏感度采样框架，基于格罗弗搜索与递归分半缩约，在不依赖数据特定参数（如条件数、矩阵范数）的前提下，首次实现了聚类、回归及多类低秩逼近任务在输入规模上的次线性时间核心集构建。

研究背景与动机¶

在大规模机器学习与数值线性代数中，核心集（coreset）技术通过提取带权重的极小子集来近似全局损失函数，是加速下游聚类、回归与低秩逼近等优化任务的核心工具。经典方法通常依赖敏感度采样（sensitivity sampling）或杠杆分数（leverage score）采样来构造无偏且低方差的估计器。然而，计算或近似每个数据点的敏感度通常需要遍历全数据集，导致经典敏感度采样的运行时间下界至少为数据量与维度的乘积 \(\Omega(nd)\)。在大数据场景下，即使是近线性时间算法也面临巨大的算力瓶颈。

现有的量子计算尝试虽然在某些特定优化问题（如线性规划、聚类、主成分分析）中展现了次线性加速潜力，但大多严重受限于苛刻的前提假设。具体而言，以往的量子算法往往依赖昂贵的量子态制备或专用 QRAM 数据结构输入表示，且算法复杂度深度绑定于数据特定的病态参数（例如数据半径、矩阵谱范数 \(\|A\|_F\)、条件数 \(\kappa(A)\) 或特征值间隔 \(\gamma\) 等）。一旦数据存在病态或谱间隙过小，这些量子算法的速度优势便荡然无存。

本文致力于打破这一壁垒，探索在完全消除数据特定参数依赖、无需特殊输入表示的前提下，能否构建通用的纯采样量子次线性核心集算法。核心 idea：将经典递归样本分半缩约与格罗弗量子拒绝采样相结合，通过建立广义逼近子（approximator）理论桥梁，将敏感度估计的搜索与采样复杂度压缩至 \(\widetilde{O}(\sqrt{ns})\)，从而在通用矩阵与张量优化任务中实现真正的次线性时间加速。

方法详解¶

整体框架¶

算法的核心管线遵循“自顶向下均匀分半下采样 → 递归构建极小逼近子 → 基于量子拒绝采样的重要性重采样”三阶段推进。对于输入点集 \(A \subset \mathbb{R}^d\)（大小为 \(n\)），算法先均匀采样一半点集递归求解，利用小规模核心集构造敏感度的高效经典评估预言机；随后利用格罗弗搜索加速的量子拒绝采样，以仅与子集大小和敏感度总和相关的开销完成整批数据的高精度抽取。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据集 A ∈ ℝ^(n×d)"] --> B["递归分半与近似子空间缩约<br/>均匀下采样 A' ⊂ A 并构建小规模核心集 C'"]
    B --> C["经典敏感度评估预言机<br/>利用 C' 快速计算广义权重上界 w'_i"]
    C --> D["格罗弗量子拒绝采样引擎<br/>以概率 p_i 独立抽取，复杂度压缩至 O~(√(ns))"]
    D --> E["纯采样下游优化求解<br/>双边杠杆分数抽取，无需完整读取数据"]
    E --> F["输出 ε-核心集与低秩解 (U, V)"]

关键设计¶

1. 递归分半与广义逼近子抽象：解除敏感度全局耦合瓶颈

直接在量子叠加态下计算每个点的真实敏感度 \(s_i = \max_{x} \frac{\mathrm{cost}(a_i, x)}{\mathrm{cost}(A, x)}\) 需要访问全量数据，开销巨大。针对这一痛点，本文提出广义权重 \(w(A, B)\) 与 \(\epsilon\)-逼近子（approximator）概念，放宽了经典敏感度局部可加性的限制。算法通过递归将点集按比例 \(1/2\) 均匀下采样至基础规模，并严格证明了当 \(a_i \notin A'\) 时，\(w'_i(A, A') = w_i(A, A' \cup \{a_i\})\) 构成了对全局权重 \(w_i(A, A)\) 的有效上界，且期望总权重满足 \(\mathbb{E}[\|w'(A, A')\|_1] \leq 2 \|w(A, A)\|_1\)。这一性质不仅覆盖了普通的敏感度，还一举拓展到了强耦合的 \(\ell_p\) Lewis 权重和岭杠杆分数（Ridge Leverage Scores）。

2. 格罗弗量子拒绝采样引擎：实现无数据参数依赖的次线性加速

传统格罗弗搜索主要用于寻找满足布尔条件的项，而核心集构建需要按非归一化概率分布 \(p_i \in [0, 1]\) 独立抽样。本文利用基于格罗弗振幅放大的量子拒绝采样算法，采用均匀分布 \(\pi_i = 1/n\) 作为提议分布，通过量子比较器和振幅放大技术，在预言机单次查询时间为 \(\mathcal{T}_{\mathrm{query}}\) 的条件下，仅需 \(\widetilde{O}(\sqrt{n \sum_{i=1}^n p_i}) \cdot \mathcal{T}_{\mathrm{query}}\) 的时间复杂度即可完成全集采样。当最终核心集规模 \(s\) 远小于 \(n\) 时，采样总开销达到严格次线性 \(\widetilde{O}(\sqrt{ns} \cdot \mathcal{T})\)，彻底摆脱了经典扫描所需的 \(\Omega(nd)\) 下界，且完全不依赖数据集的条件数或范数。

3. 纯采样低秩逼近与张量多重响应回归：规避 OSE 全局扫描

在低秩逼近任务中，经典方法在选出列子集 \(C \in \mathbb{R}^{n \times s}\) 后，通常借助 CountSketch 等不经意子空间嵌入（OSE）来求解残差回归 \(\min_X \|CX - A\|_F^2\)，这不可避免地需要扫描 \(A\) 的全部非零元素。本文提出一种“纯采样”方案，先后在左右两端引入基于杠杆分数的采样矩阵 \(T_1\) 和 \(T_2\)，将双线性回归问题缩减为极小尺寸的 \(\min_Y \|T_1 C Y S A T_2 - T_1 A T_2\|_F^2\)。由于 \(T_1 A T_2\) 仅涉及 \(A\) 的 \(\mathrm{poly}(k/\epsilon)\) 个条目，通过随机访问即可在次线性时间内完成求解。针对三阶张量，本文进一步发现即使仅针对展开矩阵做响应采样，也能保证获得 \((4+\epsilon)\) 的常数因子逼近，从而克服了张量边界秩（border rank）与未知设计矩阵采样的理论障碍。

一个完整示例¶

以矩阵 \(A \in \mathbb{R}^{n \times d}\) 的 Frobenius 范数秩-\(k\) 逼近流程为例： 1. 递归阶段：设定目标核心集大小 \(s = \widetilde{O}(k/\epsilon^2)\)，算法分 \(\log(n/s)\) 层递归均匀分半抽取子集；在最底层小规模数据上直接计算精确岭杠杆分数。 2. 量子抽样：在每层回溯时，利用小矩阵的薄 SVD 和 Johnson-Lindenstrauss 降维投影矩阵 \(M\)，将单点权重的查询耗时降至 \(\widetilde{O}(d)\)；格罗弗采样引擎在 \(\widetilde{O}(\sqrt{ns} \cdot d) = \widetilde{O}(n^{0.5} d k^{0.5} \epsilon^{-1})\) 时间内完成上一层点的筛选。 3. 低秩重构：最终得到列核心集 \(C \in \mathbb{R}^{n \times k_1}\)；进一步在行和列维度执行量子杠杆分数采样得到 \(S, T_1, T_2\)，直接在小尺寸矩阵上计算伪逆闭式解 \(\widehat{M} = (T_1 C)^\dagger [P_{T_1 C} T_1 A T_2 P_{SAT_2}]_k (SAT_2)^\dagger\)，输出低秩因子分解 \(M = C \widehat{X}\) 与 \(N^\top = \widehat{Y} S A\)，全程无需读取矩阵 \(A\) 的其余元素。

实验关键数据¶

主实验¶

论文对核心集构建与下游优化求解算法的理论时间复杂度进行了详尽推导与横向对比。

表 1：核心集构建运行时间理论对比（取 \(\epsilon = \Theta(1)\)，忽略 polylog 及关于 \(p\) 的常数因子）

问题类型	先前最优基准	先前复杂度	本文复杂度	相对加速优势
\(k\)-Median 聚类	Xue et al. [70] (量子)	\(\widetilde{O}(n^{0.5} d^{1.5} k^{0.5})\)	\(\widetilde{O}(n^{0.5} d k^{2.5})\)	消除 \(d^{0.5}\) 依赖，高维更优
\(k\)-Means 聚类	Xue et al. [70] (量子)	\(\widetilde{O}(n^{0.5} d^{1.5} k^{0.5})\)	\(\widetilde{O}(n^{0.5} d k^{2.5})\)	消除 \(d^{0.5}\) 依赖，仅保留原始点
\((k,p)\)-Clustering	Xue et al. [70] (量子)	\(\widetilde{O}(n^{0.5} d^{1.5} k^{0.5})\)	\(\widetilde{O}(n^{0.5} d k^{2.5})\)	紧凑无外部合成中心点
\(\ell_{p \neq 2}\) 回归	Apers & Gribling [3] (量子)	\(\widetilde{O}(n^{0.5} d^7)\)	\(\widetilde{O}(n^{0.5} d^{\max\{0.5, p/4\} + 1.5})\)	对所有 \(p \in (0, 22]\) 取得多项式加速
\((k, p<2)\)-子空间逼近	Woodruff et al. [69] (经典)	\(\widetilde{O}(nd)\)	\(\widetilde{O}(n^{1 - p/4} d k^{p/4})\)	在行数 \(n\) 上取得严格次线性
\((k, p \geq 2)\)-子空间逼近	Woodruff et al. [69] (经典)	\(\widetilde{O}(nd)\)	\(\widetilde{O}(n^{1 - 1/p} d k^{0.5})\)	在行数 \(n\) 上取得严格次线性

消融实验¶

论文针对不同矩阵与张量低秩逼近任务，将纯采样量子算法与经典前沿算法在无数据先验参数假设下的求解复杂度进行了系统对比。

表 2：各类低秩逼近问题求解复杂度理论对比

任务类型	经典最优基准	经典复杂度	本文量子算法复杂度	核心瓶颈突破
通用矩阵低秩逼近	Clarkson & Woodruff [23]	\(O(nd)\)	\(\widetilde{O}(n d^{0.5} k^{0.5} \epsilon^{-1})\)	消除全量矩阵读取开销
半正定 (PSD) 低秩逼近	Bakshi et al. [6]	\(O(n k^{\omega-1})\)	\(\widetilde{O}(n^{0.75} k^{2.25})\)	次线性依赖矩阵行数 \(n\)
核低秩逼近 (Kernel Low-Rank)	Bakshi et al. [6]	\(O(n k \mathcal{T}_{\sf K})\)	\(\widetilde{O}(n^{0.75} k^{1.25} \mathcal{T}_{\sf K})\)	核评估次数次线性降至 \(n^{0.75}\)
三阶张量低秩逼近 (Rank-\(k\) FPT)	Song et al. [64]	\(O(n^3 + 2^{k^2})\)	\(\widetilde{O}(n^2 k^{0.5} + 2^{k^2})\)	主导项从 \(n^3\) 降至 \(n^2 k^{0.5}\)
三阶张量双准则低秩逼近	Song et al. [64]	\(O(n^3)\)	\(\widetilde{O}(n^2 k^{0.5})\)	降阶张量输入规模依赖

关键发现¶

在 \(\ell_p\) 回归核心集问题中，先前量子算法通过迭代杠杆分数估计 Lewis 权重，复杂度含高达 \(d^7\) 的维度多项式；本文框架将维度依赖压低至 \(d^{\max\{0.5, p/4\} + 1.5}\)，在常用且计算挑战极大的 \(\ell_1\) 最小绝对偏差回归中，维度阶数从 \(d^7\) 骤降至 \(d^2\)。
在 \((k,p)\)-聚类问题中，先前量子方法构造的核心集大小含有 \(d\)（规模为 \(\widetilde{O}(dk\epsilon^{-2})\)），且被迫混入外部合成中心点；本文通过双边敏感度估计解耦维度，使得核心集大小仅为 \(\widetilde{O}_p(k^5 \epsilon^{-5p-15})\)，完全不依赖维度 \(d\)，在高维特征数据（\(d \gg k\)）下展现出压倒性优势。
在张量低秩分解中，虽然通过响应矩阵的岭杠杆分数采样会引入理论极限上的常数因子膨胀（达到 \((4+\epsilon)\) 逼近），但成功打破了强指数时间假设（SETH）在精确多项式时间下的下界阻碍，换取了密集张量上 \(n^3 \to n^2 k^{0.5}\) 的根本性飞跃。

亮点与洞察¶

通用的量子敏感度采样骨架：首次将敏感度、杠杆分数与 Lewis 权重统一在递归分半与广义逼近子框架下，提供了一个可即插即用处理几何与代数摘要问题的量子理论工具箱。
纯采样机制突破 I/O 墙：在不需要预置量子状态或高级 QRAM 数据结构的前提下，通过双向投影抽样避免了经典 OSE 必须扫描矩阵全部非零元的固有缺陷。
基础模型数据筛选新范式：结合聚类核心集与单轮自适应采样，本文将深度神经网络等昂贵损失函数指导的数据集蒸馏管线耗时从经典的 \(\Omega(ndk)\) 压缩至量子次线性的 \(\widetilde{O}(n^{0.5}kd(\epsilon^{-1}+k^{0.5}))\)，且仅需 \(k\) 次损失评估。

局限与展望¶

聚类敏感度的双边估计缺失：聚类敏感度当前只能给出单边上界估计，破坏了递归分半框架所需的均匀抽样收敛条件，导致聚类算法目前必须依赖预先计算的双准则中心点，未能完全并入统一的递归理论框架。
张量逼近比存在常数膨胀：由于无法获知未知的隐式设计矩阵分布，针对三阶张量目前仅能证明 \((4+\epsilon)\) 的常数逼近比（\(q\) 阶张量为 \((2^{q-1}+\epsilon)\)），尚未实现在次线性时间内达到严格 \((1+\epsilon)\) 乘性逼近。
下界匹配问题：本文证明了矩阵加性-乘性谱逼近需要 \(\Omega(\sqrt{dk})\) 的量子列查询下界，但对于通用核心集大小和时间复杂度的量子最优下界仍待进一步封闭。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立了无数据参数依赖的通用量子敏感度采样次线性理论体系。
理论充分度: ⭐⭐⭐⭐⭐ 数学证明严密自洽，完整覆盖矩阵、张量、核方法及聚类四大优化支柱。
写作质量: ⭐⭐⭐⭐⭐ 逻辑主线清晰，从预言机抽象到下游多任务特化层层递进。
价值: ⭐⭐⭐⭐⭐ 为量子随机数值线性代数（RandNLA）与大数据蒸馏提供了坚实的理论基石。