# 分布统计差异测试：量子计数、碰撞概率与 $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$。

## 参考文献

- Zoo 编号 117：Sergey Bravyi、Aram Harrow 与 Avinatan Hassidim, [Quantum Algorithms for Testing Properties of Distributions](https://arxiv.org/abs/0907.3920).
- Zoo 编号 16：Brassard--Høyer--Tapp, [Quantum Counting](https://arxiv.org/abs/quant-ph/9805082).
- Zoo 编号 265：Ashley Montanaro, [Quantum Speedup of Monte Carlo Methods](https://arxiv.org/abs/1504.06987).