The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

技术摘要：关于阿贝尔态隐藏子群问题的最优样本与查询复杂度

问题陈述

本文研究了有限阿贝尔群的态隐藏子群问题（StateHSP）。这是标准隐藏子群问题（HSP）的量子推广，而 HSP 是包括 Shor 分解和 Simon 问题在内的算法的基础。

在标准的 HSP 中，算法查询一个隐藏子群 $H$ 的或目函数 $f: G \to X$，该函数在 $H$ 的陪集上为常数，而在其他陪集上互不相同。在 StateHSP 中，“隐藏函数”被替换为一个未知的量子态 $|\phi\rangle$ 和群 $G$ 的一个幺正表示 $R$。目标是识别隐藏子群 $H \le G$，使得：

1. 对称性： 对于所有 $h \in H$，满足 $R(h)|\phi\rangle = |\phi\rangle$。
2. 间隙（Gap）： 对于所有 $g \in G \setminus H$，满足 $|\langle\phi|R(g)|\phi\rangle| \le 1 - \epsilon$，其中 $\epsilon \in (0, 1]$ 是已知的承诺间隙（promise gap）。

本文研究了在两种不同的输入访问模型下解决该问题的复杂度：

1. 样本模型（Sample Model）： 算法可以访问 $t$ 个独立的 $|\phi\rangle$ 副本。
2. 查询模型（Query Model）： 算法可以相干地访问一个态制备幺正算符 $U_\phi$（其中 $U_\phi|0\rangle = |\phi\rangle$）及其逆算符 $U_\phi^\dagger$。

现有文献已经确定了样本模型下 $O(\log(|G|)/\epsilon)$ 个副本的上界，但留下了关于 $\epsilon$ 的最优依赖关系以及 $|H|$ 是否影响复杂度的悬而未决的问题。此外，StateHSP 的查询复杂度此前尚未被研究。

方法论

作者结合了量子算法技术、信息论下界和对抗者论证（adversary arguments）。

1. 算法框架（上界）：
核心策略是利用**弱傅里叶采样（weak Fourier sampling）**来生成对偶子群 $H^\perp$ 的元素。算法迭代地收集“增加跨度”的生成元（即不在当前已发现生成元之跨度内的 $H^\perp$ 元素），直到 $H^\perp$ 被完全生成，随后通过经典后处理（利用 $(H^\perp)^\perp = H$）恢复出 $H$。

• 自适应停止策略： 为了避免当 $|H|$ 未知时产生 $O(\log |G|)$ 的开销，作者引入了一种自适应预算机制。算法从一个较小的迭代预算开始，每当发现一个新的增加跨度的生成元时，便增加预算。这确保了复杂度与 $\log(|G/H|)$ 而非 $\log(|G|)$ 成比例。
• 样本模型实现： 算法对 $|\phi\rangle$ 的副本进行弱傅里叶采样。一个关键引理（引理 3.7）确立了：如果当前跨度 $K^\perp$ 是 $H^\perp$ 的真子群，那么采样到元素 $H^\perp \setminus K^\perp$ 的概率至少为 $\epsilon/2$。通过重复采样 $O(1/\epsilon)$ 次，可以高概率找到一个新的生成元。
• 查询模型实现： 作者利用了相干运行 $U_\phi$ 和 $U_\phi^\dagger$ 的能力。他们构建了一个子空间标识符（一个幺正算符 $U_\perp$），用于标记落在当前跨度 $K^\perp$ 之外的傅里叶样本。这种标记机制允许使用定点振幅放大（fixed-point amplitude amplification）（受 Gilyén 等人和 Yoder 等人启发），仅需 $O(1/\sqrt{\epsilon})$ 次查询即可将找到新生成元的概率从 $\epsilon/2$ 提升至接近 1。

2. 下界技术：

• 查询下界： 作者使用了对抗者方法（adversary method）（具体为 Belovs 的相对 $\gamma_2$ 范数形式）。他们构建了一族“分数填充的 Simon 态（Fractional Padded Simon's states）”。通过对 Simon 问题进行填充以改变 $|H|$，并引入一个将或目差异按 $\sqrt{\epsilon}$ 进行缩放的分数或目，他们证明了区分实例需要 $\Omega(\log(|G/H|)/\sqrt{\epsilon})$ 次查询。该界限对于具有共轭查询（$U_\phi^*, U_\phi^T$）和控制查询的情况依然成立。
• 样本下界： 作者使用了信息论工具，特别是 Fano 不等式和 Holevo 界。他们构建了一个困难的实例族，其中隐藏子群是从大量候选者中选出的。他们表明，每个副本提供的关于隐藏子群的信息至多为 $O(\epsilon)$ 比特。因此，即使使用任意的集体测量，识别子群以恒定概率所需的样本量也为 $\Omega(\log(|G/H|)/\epsilon)$。

核心贡献与结果

1. 紧凑的复杂度表征：
本文确定了阿贝尔 StateHSP 在两种模型下的复杂度，提供了在常数因子意义下匹配的上界和下界：

访问模型	复杂度	对参数的依赖关系
样本模型 (副本)	$\Theta\left(\frac{\log(|G/H|)}{\epsilon}\right)$	关于 $1/\epsilon$ 线性；取决于商群大小 $|G/H|$。
查询模型 (幺正算符)	$\Theta\left(\frac{\log(|G/H|)}{\sqrt{\epsilon}}\right)$	关于 $1/\epsilon$ 具有二次加速；取决于商群大小 $|G/H|$。

2. 对开放问题的解决：

• $1/\epsilon$ 的最优性： 本文证明了样本模型中的 $1/\epsilon$ 缩放是信息论必要的，如果不具备相干访问能力，则无法改进。
• 子群大小的作用： 复杂度取决于 $\log(|G/H|)$，而非 $\log(|G|)$。较大的隐藏子群（较小的商群）学习起来更容易。自适应停止策略在无需预知 $|H|$ 的情况下实现了这一点。
• 二次加速的来源： 文中指出，$\epsilon$ 的二次改进（从 $1/\epsilon$ 到 $1/\sqrt{\epsilon}$）完全源于对制备电路的相干访问（从而能够进行振幅放大）。下界对于强大的或目扩展（共轭和控制查询）依然成立，这表明振幅放大是该设定下所能获得的极大优势。

3. 应用：
作者展示了这些改进的界限如何转化为之前以 StateHSP 形式表述的特定对称性学习问题：

• 定位非纠缠性（Locating Unentanglement）： 识别多体态中的张量积切分。查询模型将对保真度间隙的缩放从 $1/\tilde{\epsilon}^2$ 提升至 $1/\tilde{\epsilon}$。
• 学习稳定器群（Learning Stabilizer Groups）： 恢复量子态的稳定器群。查询模型改善了对间隙参数 $\epsilon$ 的依赖关系。
• 识别平移对称性（Identifying Translation Symmetries）： 寻找多体态中隐藏的平移对称性。复杂度随不变平移的数量而非系统规模缩放。

重要性与主张

本文声称提供了完整且紧凑的表征，涵盖了阿贝尔 StateHSP。其重要性在于：

1. 阐明了或目访问的力量： 它精确隔离了相干访问态制备幺正算符与单纯访问副本之间所提供的计算优势。结果表明，虽然相干访问在间隙参数上提供了二次加速，但它不会改变对群结构的根本性的对数依赖关系。
2. 桥接 HSP 与学习： 通过将 HSP 推广到 StateHSP 并提供最优算法，这项工作将 Shor 算法的代数结构与现代量子学习任务（稳定器学习、纠缠检测）联系起来。
3. 方法论的严谨性： 作者提供的算法不仅在查询上是最优的，而且仔细界定了经典和量子门开销，确保了结果在实际高效实现中的相关性。

作者谦虚地指出，虽然他们的结果优化了特定应用的 StateHSP 归约，但用于下界的困难实例是专门为该归约构建的，可能并不直接反映特定物理问题（如稳定器学习）的结构。因此，为这些特定物理问题建立匹配的下界仍是一个开放的方向。此外，虽然暗示了逆幺正算符 $U_\phi^\dagger$ 对实现二次加速是必要的，但在没有逆算符的一般情况下，并未对此进行严格证明。