技术摘要：AQKA：预算约束下的主动量子核获取

1. 问题陈述

量子核方法将经典输入映射到量子特征空间以计算保真度 $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$，是无噪声中等规模量子（NISQ）硬件中最易实现的工作负载之一。然而，其实际部署受限于测量成本。估计一个 $N \times N$ 的核矩阵需要 $\Theta(N^2 S)$ 次电路执行（shots），其中 $S$ 是达到所需精度所需的每个条目 shots 数。在当前硬件上，电路延迟从毫秒到秒不等，这种扩展性将可部署的问题规模限制在数百以内。

现有的节省预算策略（例如 Nyström-QKE、ShoFaR、核 - 目标对齐）通过子采样哪些条目进行测量（例如选择地标列或训练点）来解决这一问题。然而，这些方法通常在其选定的子集内均匀分配 shots 预算。它们未能考虑到每个特定核条目对下游分类器性能贡献的异质性。核心未解问题是：给定固定的 shots 预算 $B$，应如何在成对级别分配 shots 以最小化下游任务的损失？

2. 方法论：AQKA

作者将受 shots 预算约束的量子核学习表述为一个优化问题，即在总 shots 预算约束 $\sum s_{ij} \leq B$ 下最小化期望损失 $\mathbb{E}[L(\hat{K})]$。

理论推导

利用一阶分析（Delta 方法）结合 Karush-Kuhn-Tucker (KKT) 条件，作者推导出了闭式最优分配规则。对于用 $s_{ij}$ 次 shots 估计的核条目 $K_{ij}$，其方差为 $K_{ij}(1-K_{ij})/s_{ij}$。最小化损失估计量方差的最优分配 $s^*_{ij}$ 与该条目的损失敏感度成正比：
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
其中 $g_{ij} = \partial L / \partial K_{ij}$ 是损失关于核条目的梯度。

• 对于核岭回归 (KRR)： 梯度显式推导为 $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$，其中 $\alpha = (K+\lambda I)^{-1}y$ 且 $\beta = (K+\lambda I)^{-1}\alpha$。
• 对于支持向量机 (SVM)： 利用包络定理（Danskin 定理），梯度推导为 $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$，其中 $\eta^*$ 是最优对偶变量。

算法实现

作者提出了 AQKA（主动量子核获取），这是一种可部署的算法，按轮次运行：

1. 预热 (Warm-up)： 花费一小部分预算（$\eta_w B$）进行均匀采样，以生成初始核估计 $\hat{K}$。
2. 敏感度估计： 算法在 $\hat{K}$ 上求解 KRR（或 SVM）问题，以计算基于梯度的敏感度评分 $g_{ij}$。
3. 目标填充分配 (Target-Fill Allocation)： 不同于从多项分布中采样 shots（这可能会因随机波动而“饿死”低敏感度对），AQKA 采用确定性的“目标填充”方法。它计算目标 shots 数 $s^*_{ij}$，并将差值 $\max(0, s^*_{ij} - s_{ij})$ 添加到每一对中。
4. 探索 (Exploration)： 添加一小部分探索预算（$\eta_e B$）进行均匀采样，以防止算法完全忽略那些可能因高阶效应或估计噪声而变得重要的对。

3. 主要贡献

1. 完整的机制分解

该论文提供了不同分配策略何时最优的原则性特征描述：

• AQKA 在稀疏敏感度 KRR 任务的预算受限机制（$B \lesssim 16 n_{pairs}$）中占主导地位。
• Nyström-QKE（低秩重建）在饱和预算下的植入稀疏数据上表现最佳，此时低秩结构可以被完全恢复。
• ShoFaR 风格的方法仅在极端低预算机制中具有竞争力。

2. 成对级别获取的闭式理论

• KKT 最优分配： 推导了 shots 噪声下 KRR 和 SVM 的闭式梯度 $g_{ij}$。
• 修正的稀疏感知界限： 作者推导了可实现方差降低比率 $\rho$ 的柯西 - 施瓦茨界限。他们将假设 $g$ 支持在 $S \times S$ 上的朴素 $\Theta(m^2/N^2)$ 扩展修正为更准确的 $\Theta(m/N)$ 扩展（对于 KRR，$\rho \leq 2m/N$）。这反映了这样一个结构事实：即使解向量 $\alpha$ 是稀疏的，敏感度向量 $\beta = (K+\lambda I)^{-1}\alpha$ 在一般情况下也是稠密的，这意味着任何触及支持集的对都具有非零敏感度。
• 遗憾界限 (Regret Bounds)： 提供了显式常数的即插即用遗憾界限，表明随着预热预算的增加，误差收敛于神谕最优值。

3. 可部署的目标填充算法

该论文证明，确定性的目标填充方案优于自然的多项式采样，特别是在预算受限机制中。多项式采样倾向于激进地集中在少数高分对上，从而“饿死”其他对并放大矩阵求逆中的噪声；而目标填充则维持了最低覆盖底线。

4. 量子硬件上首次多种子实时在线自适应

作者报告了在当前的 156 量子比特 IBM Heron 类设备上进行的在线自适应 shots 分配的首次已发表演示。

• IBM Aachen (N=20)： 相比均匀分配提高了 +17.0 ± 4.8 个百分点（3.5$\sigma$ 显著性）。
• IBM Berlin (N=30)： 在较高预算下提高了 +14.0 ± 8.5 个百分点。

4. 实验结果

合成与模拟设置

• 植入稀疏 KRR： 在具有稀疏解向量的合成数据上，随着 $N$ 从 225 扩展到 1000，AQKA（使用估计敏感度的目标填充）相比均匀分配实现了 +8 到 +25 个百分点的提升。
• 无噪声量子核： 这些增益转移到了无噪声的 4 量子比特 ZZFeatureMap 模拟中，相比均匀分配提高了 +13 到 +18 个百分点。
• 硬件重采样消融实验： 使用在 IBM Pittsburgh（156 量子比特）上测量的核并进行 shots 噪声重采样，AQKA 在 $B = n_{pairs}$ 时相比均匀分配实现了 +26.3 ± 6.1 个百分点的提升，在 $B = 4n_{pairs}$ 时实现了 +31.9 ± 7.2 个百分点的提升。

真实数据基准

• 乳腺癌（稠密 $\alpha$）： 在解向量稠密（非稀疏）的真实世界数据集上，AQKA 并未表现出统一的支配性。它具有竞争力，但显示出机制依赖的性能，这表明该方法的优势依赖于高水平的成对敏感度异质性。
• SVM 与 KRR： 论文指出，虽然理论框架扩展到 SVM，但由于支持集在噪声预热下的不稳定性，即插即用版本更为脆弱。在小 $N$、噪声预热的机制下，SVM 的 AQKA 可能表现不如均匀分配，而 KRR 版本则保持稳健。

5. 意义与主张

该论文声称填补了理论 shots 预算优化与 NISQ 硬件实际部署之间的空白。其主要意义在于：

1. 超越均匀分配： 证明了非均匀、敏感度感知的 shots 分配对于近期量子核学习至关重要，特别是在预算紧张时。
2. 硬件验证： 提供了在真实量子硬件上对自适应 shots 分配策略的首次多种子、实时在线验证，证明了理论增益能够经受住设备噪声和校准漂移的考验。
3. 机制意识： 确立了没有单一方法是普遍优越的；AQKA 是专门为预算受限、稀疏敏感度的机制设计的，这是当前硬件在操作层面上相关的区域。

作者在主张上保持谦逊，承认对于稠密敏感度问题或饱和预算，其他方法（如 Nyström）或均匀分配可能更可取。他们还指出了 SVM 即插即用噪声是当前需要未来工作（例如边缘稳定化获取）的局限性。