Quantum Approximate Counting with Bernoulli Oracles

技术摘要：基于伯努利算子的量子近似计数

1. 问题定义

本文研究了在标准成员算子（membership oracle）被伯努利算子（Bernoulli oracle）取代的情境下的量子近似计数问题。

• 标准设定： 在经典和标准量子计数中，成员算子确定性地为集合中的元素标记为 0 或 1。目标是在加性误差 $\epsilon$ 内估计标记为 1 的元素比例 $\rho$。量子算法相对于经典采样实现了二次加速，其查询复杂度为 $\Theta(\sqrt{\rho}/\epsilon)$，而经典采样为 $\Theta(\rho/\epsilon^2)$。
• 伯努利算子设定： 作者考虑了一种更现实的场景，即标签是概率性的。算法可以访问 $m$ 个具有未知偏差 $p_1, \dots, p_m \in [0, 1]$ 的伯努利分布 $D = \{D_1, \dots, D_m\}$。
  • 如果 $p_i \ge 1/2 + \Delta$，则称该分布为**正向（positive）**分布。
  • 如果 $p_i \le 1/2 - \Delta$，则称该分布为**负向（negative）**分布。
  • 目标是在加性误差 $\epsilon$ 内估计正向分布的比例 $\rho$。
  • 量子算子 $O$ 作用于索引寄存器 $A$ 和辅助寄存器 $B, C$ 为：
    $$O |i\rangle_A |\vec{0}\rangle_{B,C} = |i\rangle_A \left( \sqrt{p_i} |1\rangle_B |\phi_{i,1}\rangle_C + \sqrt{1-p_i} |0\rangle_B |\phi_{i,0}\rangle_C \right)$$

该模型推广了有界误差算子（bounded-error oracle）（其中每次查询以常数概率 $p_e \ge 9/10$ 返回正确标签，对应 $\Delta = 2/5$）以及标准的成员算子（其中 $\Delta = 1/2$）。

2. 方法论

本文通过对上界和下界采用不同的技术手段，建立了查询复杂度的上界和下界。

上界技术：
主要的挑战在于，如果不破坏量子叠加态，仅凭有限次数的查询无法完美判定一个特定分布是正向还是负向。标准的误差规约（通过重复实验并取中位数）需要测量，而测量会破坏量子振幅估计所需的相干性。

为了解决这一问题，作者提出了一个三阶段算法：

1. 通过 QSVT 进行相干误差规约： 为了避免测量，算法使用**量子奇异值变换（QSVT）**来相干地放大偏差间隙（bias gap）。通过使用阶数为 $O(\frac{1}{\Delta} \log \frac{1}{\epsilon})$ 的多项式来逼近阶跃函数，算法转换状态使得：
   • 如果 $p_i \ge 1/2 + \Delta$，则测量 $|1\rangle$ 的概率变为 $\ge 1 - \epsilon$。
   • 如果 $p_i \le 1/2 - \Delta$，则测量 $|1\rangle$ 的概率变为 $\le \epsilon$。
     该子程序称为 RST（鲁棒单分布变换），它在整个相干层内执行误差规约，从而保留了索引寄存器上的叠加态。
2. 两阶段自适应振幅估计： 将 RST 子程序嵌入到自适应振幅估计方案中。
   • 第一阶段： 获取 $\rho$ 的粗略估计。
   • 第二阶段： 如果 $\rho$ 不可忽略，则利用粗略估计来校准第二次更精细估计运行的精度。这避免了在 $\rho$ 非常小时浪费资源进行高精度估计。
3. 置信度提升： 整个过程重复 $\Theta(\log(1/\delta))$ 次，并取中位数以将成功概率提升至 $1-\delta$。

下界技术：
作者通过将估计问题归约为一个复合决策问题：Count $\circ$ DD 来证明下界。

• 外层函数 (Count)： 一个标准的布尔函数，用于判断一个 $m$ 位比特串的汉明重量是 $\rho m$ 还是 $(\rho + \epsilon)m$。
• 内层函数 (DD)： 一个平均情况下的问题，即在给定 $R$ 个独立样本的情况下，区分两个未知的分布 $P$ 和 $Q$。

作者引入了一种新的量子对抗方法组合定理（composition theorem for the quantum adversary method），其方向为布尔覆盖平均情况（Boolean-over-average-case）。标准的组合定理处理的是“布尔覆盖布尔”或“平均情况覆盖布尔”，而这项工作处理的是相反的方向（布尔外层，平均情况内层）。

• 障碍 1（内层非均匀性）： 不同块之间的内积并不保证相等。作者构造了特定的内层对抗矩阵，使得每个块的内积都等于 1，从而确保了兼容性。
• 障碍 2（外层失配）： 对于一般的布尔函数，外层的均匀分布向量并不与对抗矩阵的主特征向量对齐。作者表明，对于特定的“Count”函数（一个 0-1 矩阵），全 1 向量为谱范数提供了足够的下界，从而解决了失配问题。

3. 关键结果

本文对具有伯努利算子的量子计数提供了近乎完整的查询复杂度表征。

上界 (定理 1.2)：
存在一种量子算法，可以在成功概率为 $1-\delta$ 的条件下，以如下查询复杂度估计 $\rho$ 的加性误差 $\epsilon$：
$$\tilde{O}\left( \left( \frac{\sqrt{\rho}}{\Delta \epsilon} + \frac{1}{\Delta \sqrt{\epsilon}} \right) \log \frac{1}{\delta} \right)$$

• 这实现了相对于经典采样复杂度 $\Theta(\frac{\rho}{\Delta^2 \epsilon^2})$ 的二次加速。
• 对于有界误差算子的特例（$\Delta = \Theta(1)$），该界限简化为 $\tilde{O}(\frac{\sqrt{\rho}}{\epsilon} + \frac{1}{\sqrt{\epsilon}})$。

下界 (定理 1.3)：
任何以 $2/3$ 的成功概率在误差 $\epsilon$ 内估计 $\rho$ 的量子算法都需要：
$$\Omega\left( \frac{\sqrt{\rho}}{\Delta \epsilon} \right)$$
次查询。

• 该下界在整个 $\Delta$ 范围内，在忽略对数因子的情况下与上界相匹配。
• 对于有界误差算子（$\Delta = \Theta(1)$），下界为 $\Omega(\frac{\sqrt{\rho}}{\epsilon})$。

包含链：
本文建立了一个算子层级结构：成员算子 $\subset$ 有界误差算子 $\subset$ 伯努利算子。

• 当 $\Delta = 1/2$ 时，针对伯努利算子的结果恢复了标准的量子计数界限。
• 当 $\Delta = 2/5$ 时，结果刻画了有界误差算子量子计数的复杂度，这是一个此前被研究过但在该特定语境下尚未完全刻画的问题。

4. 重要性与主张

作者声称这项工作为概率标签下的量子近似计数提供了本质完整的复杂度表征。

• 加速效应的泛化： 该工作证明，只要偏差间隙 $\Delta$ 已知，即使算子返回的是概率性样本而非确定性标签，量子计数的二次加速依然稳健。
• 相干误差规约： 本文引入了一种利用 QSVT 进行相干误差规约的技术，避免了由于将经典误差规约与量子振幅估计结合而导致的叠加态坍缩。
• 新的组合定理： 下界的推导引入了一种全新的、针对“布尔覆盖平均情况”方向的量子对抗方法组合定理，克服了此前阻碍此类分析的特定结构性障碍（内层非均匀性和外层失配）。
• 有界误差算子的刻画： 作为直接推论，本文确定了有界误差算子量子计数的查询复杂度，显示其规模为 $\tilde{O}(\sqrt{\rho}/\epsilon)$，在忽略对数因子的情况下与标准成员算子规模一致。

论文最后指出两个开放性问题：是否可以移除上界中的对数因子，以及在采样模型（算法接收随机的索引对和样本）而非此处使用的自适应查询模型下，复杂度会如何变化。