技术摘要：针对重尾噪声随机优化的量子加速

问题陈述

本文研究如下随机优化问题：
$$\min_{x \in X \subseteq \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P_{f,x}} [F(x; \xi)]$$
其中 $f$ 可能为非凸函数。核心挑战在于存在重尾梯度噪声。与传统假设方差有界的分析不同，本研究在假设 1.1 下运行，即随机梯度 $\nabla F(x; \xi)$ 满足：
$$\mathbb{E}[\|\nabla F(x; \xi) - \nabla f(x)\|^p] \leq \sigma^p$$
对于某些 $p \in (1, 2]$。该假设意味着当 $p < 2$ 时，方差可能为无穷大，使得标准的有界方差量子估计器和经典的梯度裁剪方法不再最优或无法适用。

此类设定下的现有经典方法（例如梯度裁剪、归一化 SGD）在非凸问题中受到 $\Omega(\epsilon^{-\frac{3p-2}{p-1}})$ 的下界限制，在凸问题中受到 $\Omega(\epsilon^{-\frac{p}{p-1}})$ 的下界限制。本文研究了量子计算是否能在这种重尾机制下提供可证明的加速，由于此前缺乏针对重尾分布的多变量量子均值估计器，这一问题在以往是开放性的。

方法论

1. 量子均值估计器

所提算法的基础是开发新型量子均值估计器，用于处理具有有界 $p$ 阶中心矩的 $d$ 维随机变量。

• 量子重尾均值估计器 (QHTME)：

  • 机制： 遵循“中心化—截断—估计”的过程。
    1. 中心化： 使用经典重尾估计器 (CHTME) 获取均值 $\mu$ 的粗略估计 $\zeta$。将变量中心化为 $Y = X - \zeta$。
    2. 截断： 截断样本中 $\|Y\| > B$ 的部分，以创建一个有界变量 $Z_B$。阈值 $B$ 的选择旨在控制偏差。
    3. 估计： 对 $Z_B$ 应用有界方差量子均值估计器 (QEstimator)，然后加回 $\zeta$。
  • 复杂度： 实现误差 $\epsilon$ 的查询复杂度为 $\tilde{O}(\sqrt{d} (\sigma/\epsilon)^{\frac{p}{2(p-1)}})$。在低维机制下（$d \lesssim (\sigma/\epsilon)^{\frac{p}{p-1}}$），这优于最优经典复杂度 $\tilde{O}((\sigma/\epsilon)^{\frac{p}{p-1}})$。

• 量子无偏重尾均值估计器 (QUHTME)：

  • 动机： QHTME 是有偏的，这限制了其在需要无偏梯度的框架（如投影 SGD）中的应用。
  • 机制： 扩展了多层蒙特卡洛 (MLMC) 技术。它构建了一个具有受控 $p$ 阶原始矩的修正估计器 $QHTME^+$，并将其嵌入到广义 MLMC 框架中。
  • 复杂度： 提供一个期望查询复杂度为 $\tilde{O}(\sqrt{d} (\sigma/\epsilon)^{\frac{p}{2(p-1)}})$ 的无偏估计。

2. 量子随机优化算法

利用这些估计器，作者提出了两种优化方法：

• QNSGD（量子归一化 SGD）： 用于非凸优化。

  • 更新规则： $x_{t+1} = x_t - \eta \frac{g_t}{\|g_t\|}$，其中 $g_t$ 是由 QHTME 生成的梯度估计。
  • 收敛性： 以概率 $1-\delta$ 找到 $\epsilon$-驻点（即 $\|\nabla f(x)\| \leq \epsilon$）。
  • 查询复杂度： $\tilde{O}(\sqrt{d} \epsilon^{-\frac{5p-4}{2p-2}})$。

• QPSGD（量子投影 SGD）： 用于凸优化。

  • 更新规则： $x_{t+1} = \Pi_X(x_t - \eta g_t)$，其中 $g_t$ 是来自 QUHTME 的无偏梯度估计。
  • 收敛性： 找到期望次优性 $\leq \epsilon$ 的解。
  • 查询复杂度： $\tilde{O}(\sqrt{d} \epsilon^{-\frac{3p-2}{2(p-1)}} + \epsilon^{-2})$。

关键结果与下界

量子下界

本文建立了量子下界，以证明所提估计器的最优性：

• 维度无关： 对于 $p \in (1, 4/3]$，任何量子算法都需要 $\Omega((\sigma/\epsilon)^{\frac{p}{2(p-1)}})$ 次查询。
• 维度相关： 对于 $p \in (4/3, 2]$ 且 $1 \leq d \leq (\sigma/\epsilon)^2$，下界为 $\Omega(d^{\frac{3p-4}{4(p-1)}} (\sigma/\epsilon)^{\frac{p}{2(p-1)}})$。
• 高维： 当 $d \geq (\sigma/\epsilon)^2$ 时，下界回归至 $\Omega((\sigma/\epsilon)^2)$，继承了有界方差的限制。

这些界限证实了 QHTME 和 QUHTME 在关于 $\sigma$ 和 $\epsilon$ 的依赖关系上（在 $d$ 为常数时）在对数因子范围内是优化的，并且对于 $p > 4/3$，非平凡的 $d$ 依赖性是不可避免的。

与经典界限的比较

所提量子算法在特定机制下优于经典下界：

• 非凸： 当 $d \lesssim \epsilon^{-\frac{p}{p-1}}$ 时，QNSGD 优于经典下界 $\Omega(\epsilon^{-\frac{3p-2}{p-1}})$。
• 凸： 当 $d \lesssim \epsilon^{-\frac{2-p}{p-1}}$ 时，QPSGD 优于经典下界 $\Omega(\epsilon^{-\frac{p}{p-1}})$。

重要性与主张

本文声称解决了关于重尾噪声随机优化是否存在量子加速这一开放性问题。其主要贡献包括：

1. 算法原语： 首次提出了针对多变量重尾随机变量的量子均值估计器（QHTME 和 QUHTME），推广了以往的一元或有界方差的结果。
2. 最优性： 证明了这些估计器在 $\sigma$ 和 $\epsilon$ 方面的依赖关系在对数因子范围内是优化的，并给出了对于 $p > 4/3$ 的紧密维度相关下界。
3. 优化加速： 证明了这些估计器在低维机制下，对于非凸和凸随机优化均能产生可证明的量子查询复杂度加速。

作者明确指出，这些结果是理论查询复杂度结果。他们并未声称在近期的硬件上具有直接的实际优势，并指出所需的相干算子访问和电路深度需要容错量子计算机。其意义在于确立了在重尾噪声（这在大型语言模型和强化学习等现代机器学习应用中十分普遍）环境下，进行鲁棒随机优化的量子算法的理论极限与可能性。