Improved Quantum Algorithms for Rényi Entropies Estimation

技术摘要：改进的 Rényi 熵估计量子算法

问题陈述
本文解决了估计未知离散概率分布 $p = (p_i)_{i=1}^n$ 的 Rényi 熵 $H_\alpha(p)$ 的基本问题。目标是使用尽可能少的对纯化量子算子（purified quantum oracle）的查询，计算 $H_\alpha(p)$ 的加性 $\epsilon$-近似。作者考虑了纯化量子查询访问模型，其中酉算子 $U_p$ 准备状态 $\sum_{i=1}^n \sqrt{p_i}|\phi_i\rangle_G|i\rangle_B$，这允许在算子调用之间进行相干访问和干涉，是一种比经典采样更强大的资源。

具体的挑战在于阶数参数 $\alpha$ 的非整数区间。对于整数阶 $\alpha > 1$，存在基于碰撞（collision-based）的估计器；而对于非整数阶，需要以高相对精度（由于熵定义中的对数变换）来估计幂和 $P_\alpha(p) = \sum p_i^\alpha$，而不仅仅是加性精度。先前的量子算法，如 Wang, Zhang, 和 Li [19] 以及 Chen 等人 [20]，所提供的上界在对分布规模 $n$ 和精度 $\epsilon$ 的依赖关系上并非最优。

方法论
作者改编并完善了由 Chen 等人 [20] 引入的多级估计框架（multi-level estimation framework）。该框架将概率区间 $[0, 1]$ 划分为几何递减的部分，并利用**量子奇异值变换（QSVT）**通过局部多项式逼近来估计分布的泛函。

关键的方法论创新包括：

1. 幂和的相对逼近： 与 Tsallis 熵（仅需幂和的加性逼近即可）不同，Rényi 熵要求对 $P_\alpha(p)$ 进行相对精度估计。作者通过利用幂和的大小，改进了多级框架以实现这一点。
2. 未知边界的二分查找： 算法最初假设已知 $P_\alpha(p)$ 的上界。为了消除这一要求，作者采用了一种二分查找策略，通过迭代细化上界，直到达到常数相对精度，随后进行高精度估计步骤。
3. 针对不同区间的不同初始状态：
   • 对于 $\alpha > 1$： 算法使用源自分布 $p$ 的标准状态准备。它通过基于已知 $P_\alpha(p)$ 上界 $R$ 设置几何区间，来处理变化的概率尺度。
   • 对于 $0 < \alpha < 1$： 作者引入了一种修改后的初始状态：标签的均匀叠加态（$\sum \frac{1}{\sqrt{n}}|i\rangle$）。这一改变避免了在 $0 < \alpha < 1$ 时使用局部多项式去逼近奇异函数 $p^{\alpha-1}$，因为这在接近零点时会产生问题。
4. 强化的下界构造： 对于 $0 < \alpha < 1$ 区间，作者构建了一个基于扰动“尾部质量（tail mass）”的下界论证，该质量来自于一个具有一个重输出和一个均匀轻尾的分布，而非通过比较点质量与带有小尾的分布。

主要贡献与结果

1. 改进了 $\alpha > 1$ 的上界：
   对于非整数 $\alpha > 1$，作者提出了一个查询复杂度为以下形式的算法：
   $$\tilde{O}\left( \frac{n^{\max\{1/2, 1-1/\alpha\}}}{\epsilon} \right)$$

   • 对于 $1 < \alpha < 2$，复杂度为 $\tilde{O}(\sqrt{n}/\epsilon)$。
   • 对于 $\alpha > 2$，复杂度为 $\tilde{O}(n^{1-1/\alpha}/\epsilon)$。
     这通过降低第一项中 $n$ 的指数，并在整个 $\alpha > 1$ 区间内实现了对 $1/\epsilon$ 的线性依赖，从而改进了 Wang 等人 [19] 的最优结果。对于 $1 < \alpha < 2$，其维度指数在忽略次多项式因子的情况下符合已知的量子下界。

2. 改进了 $0 < \alpha < 1$ 的上界：
   对于 $0 < \alpha < 1$，作者实现的查询复杂度为：
   $$\tilde{O}\left( \frac{n^{1/(2\alpha)}}{\epsilon^{\max\{1, 1/(2\alpha)\}}} \right)$$

   • 对于 $0 < \alpha \le 1/2$，复杂度为 $\tilde{O}((n/\epsilon)^{1/(2\alpha)})$。
   • 对于 $1/2 \le \alpha < 1$，复杂度为 $\tilde{O}(n^{1/(2\alpha)}/\epsilon)$。
     该结果改进了对 $1/\epsilon$ 的依赖关系（此前为两个上界的最小值），且没有增加对 $n$ 的依赖。

3. 强化的 $0 < \alpha < 1$ 下界：
   作者证明了 $0 < \alpha < 1$ 的一个新查询下界：
   $$\Omega\left( n^{\frac{1}{2\alpha} - o(1)} + \frac{n^{\frac{1}{2\alpha} - \frac{1}{2}}}{\epsilon^{\max\{1, 1/(2\alpha)\}}} \right)$$
   这强化了 Chen, Wang, 和 Zhang [23] 之前的下界中关于精度依赖项的部分。通过将这一新下界与他们的上界相结合，作者证明了他们的算法在 $0 < \alpha < 1$ 时达到了最优的精度依赖性（忽略对数因子）。

意义
本文声称解决了关于 Rényi 熵估计量子查询复杂度的开放问题，特别是关于分布规模 $n$ 与精度 $\epsilon$ 之间的权衡。通过将多级框架应用于 Rénei 熵特定的相对精度需求，并为不同的 $\alpha$ 区间引入定制的初始状态，作者建立了更紧凑的上界。此外，强化的 $0 < \alpha < 1$ 下界证实了其算法在精度依赖性上的最优性，识别了此类参数下量子估计的基本极限。这项工作强调了在量子泛函估计中偏差减少（bias reduction）与统计涨落（statistical fluctuations）的不同角色，并阐明了对于非整数阶 Rényi 熵，相干访问相对于独立采样的优势。