分布统计差异测试：量子计数、碰撞概率与 \(L_1\) 距离

给定两个未知分布 \(P,Q\)，怎样判断它们相近还是相远？若只能经典采样，精确找到造成差异的稀有元素很昂贵；相干 sampler oracle 允许对“哪些随机种子产生元素 \(i\)”做量子计数，并用振幅估计加速 Monte Carlo 平均。本课推导 \(L_1\) 距离估计的核心恒等式，以及 uniformity、orthogonality 为何可进一步做到 \(O(N^{1/3})\) 查询。

1. 输入模型先于复杂度

分布定义在 \([N]\)。给定可逆 sampler

\[ O_P|s,0\rangle=|s,P(s)\rangle, \qquad s\in[S], \]

使

\[ p_i=\Pr_{s\sim U[S]}[P(s)=i]. \]

\(O_Q\) 类似。经典调用后测量就是普通样本；量子算法可保持 \(s\) 的叠加，并对谓词

\[ [P(s)=i] \]

做 amplitude estimation。若只给若干已经测量的样本，不能实现这些算法；若直接给 amplitude encoding \(\sum_i\sqrt{p_i}|i\rangle\)，则又是不同且可能更强的模型。

目标距离采用

\[ \|P-Q\|_1=\sum_{i=1}^N|p_i-q_i|. \]

常见 promise 是距离至多 \(a\) 或至少 \(b>a\)，其中 gap 为常数；精度依赖必须单独写入复杂度。

2. 将 \(L_1\) 距离写成混合分布期望

令

\[ r_i=\frac{p_i+q_i}{2}. \]

对 \(r_i>0\) 定义

\[ g(i)=\frac{2|p_i-q_i|}{p_i+q_i}\in[0,2]. \]

则

\[ \mathbb E_{i\sim R}[g(i)] =\sum_i\frac{p_i+q_i}{2} \frac{2|p_i-q_i|}{p_i+q_i} =\|P-Q\|_1. \]

因此一次外层实验可先随机选择 \(P\) 或 \(Q\) 并采样 \(i\)，再估计该点的 \(p_i,q_i\)，输出 \(g(i)\)；最后估计均值。

3. 单点概率怎样量子估计

固定 \(i\)，谓词 \(P(s)=i\) 的成功概率就是 \(p_i\)。量子计数在约 \(T\) 次 oracle 调用后给出幅度估计，误差典型包含

\[ O\!\left(\frac{\sqrt{p_i}}T+\frac1{T^2}\right). \]

相对误差在极小 \(p_i\) 上很贵，所以算法不能给每个 \(i\) 都用同一精度。它先按 \(p_i+q_i\) 的数量级分桶：质量大的元素少、可精估；质量小的元素单点误差大，但被 \(R\) 抽到的总贡献受控。截断估计

\[ \widetilde g(i)= \frac{2|\widetilde p_i-\widetilde q_i|} {\widetilde p_i+\widetilde q_i} \]

并在分母太小时用有偏但有界替代，能把总 bias 控制在常数精度内。

外层均值也可由 amplitude estimation 加速。综合多尺度预算，固定加性精度下总查询约为

\[ \widetilde O(\sqrt N), \]

而该 oracle 模型下经典需要 \(\Omega(N)\) 级调用来估计一般两分布的 \(L_1\) 距离。这里省略号隐藏精度与对数因子，不代表一次查询恢复整张分布表。

4. Uniformity 与二阶碰撞矩

测试 \(P\) 是否均匀，令 \(U_i=1/N\)。碰撞概率

\[ C(P)=\Pr_{i,j\sim P}[i=j] =\sum_i p_i^2 \]

满足

\[ C(P)-\frac1N =\sum_i\left(p_i-\frac1N\right)^2 =\|P-U\|_2^2. \]

若 \(\|P-U\|_1\ge\epsilon\)，Cauchy--Schwarz 给出

\[ \|P-U\|_2^2\ge\epsilon^2/N. \]

所以 uniformity 可化为检测略高于 \(1/N\) 的碰撞率。量子算法先少量抽样捕捉 heavy elements，再在剩余轻元素上用 collision finding/quantum counting 估计二阶矩；两部分在样本数约 \(N^{1/3}\) 处平衡，得到固定 \(\epsilon\) 下

\[ O(N^{1/3}) \]

查询，而经典下界为 \(\Omega(N^{1/2})\)。

5. Orthogonality 与跨分布碰撞

若 \(P,Q\) 支持集不交，则

\[ \sum_i p_iq_i=0. \]

若承诺 overlap 足够大，该交叉碰撞矩为正。算法从一个分布抽取并存储约 \(r\) 个代表，再在另一个 sampler 的种子空间做量子搜索，寻找输出落入该表的种子。重元素容易被表命中，轻元素则有大量小概率贡献；分桶后设置成本 \(r\) 与 Grover 成本平衡于 \(r=N^{1/3}\)，同样得到 \(O(N^{1/3})\)。

必须说明 promise：若两分布只在总质量 \(2^{-N}\) 上重叠，任何固定精度测试都不要求发现它；“orthogonal vs. far from orthogonal”的 gap 决定查询数。

6. 与量子 Monte Carlo 的统一视角

许多统计量可写成

\[ \mu=\mathbb E[f(X)],\qquad0\le f\le1. \]

经典 Monte Carlo 为误差 \(\epsilon\) 需 \(O(1/\epsilon^2)\) 样本；若采样过程与 \(f\) 可相干、可逆实现，amplitude estimation 通常降为 \(O(1/\epsilon)\) 次调用。分布测试额外困难在于 \(f\) 本身依赖未知 \(p_i,q_i\)，所以需要内层概率估计和 heavy/light 分解，不能只引用平方加速口号。

7. 小例子

取

\[ P=(1/2,1/2,0,0),\qquad Q=(1/2,0,1/2,0). \]

则

\[ \|P-Q\|_1=1. \]

混合分布 \(R=(1/2,1/4,1/4,0)\)。\(g(1)=0\)，\(g(2)=g(3)=2\)，故

\[ \mathbb E_R[g] =\tfrac12\cdot0+\tfrac14\cdot2+\tfrac14\cdot2=1. \]

该例也显示态 overlap 不能直接代替 \(L_1\)：两分布共享第一项，但差异来自其余支持质量。

8. 小结与习题

  • 相干 sampler 允许对某元素的 preimage 比例做量子计数。

  • \(L_1\) 距离是混合分布下一个有界比值函数的期望。

  • Heavy/light 分桶避免对极小概率一律要求相对精确。

  • Uniformity 与 orthogonality 可由碰撞矩在 \(N^{1/3}\) 查询内测试。

  1. 验证 \(g(i)\in[0,2]\) 及期望恒等式。

  2. 推导 uniformity 的碰撞概率公式。

  3. 构造两个 Hellinger 距离相近但 \(L_1\) 结构不同的分布，说明为何模型要明确。

  4. 解释嵌套 amplitude estimation 为什么不只依赖精度，还依赖 \(N\)。

参考文献