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

给定两个未知分布 \(P,Q\)，只允许反复采样，怎样判断它们"相近"还是"相远"？这类问题称为分布性质测试 (distribution property testing)：我们不想恢复整张分布表——那需要 \(\Omega(N)\) 量级的样本才能逐点读准——只想对某个整体性质给出"是/否"判定，并希望用的样本（或 oracle 查询）越少越好。这种"判定代替学习"的哲学正是性质测试的出发点：当 \(N\) 巨大时，完整描述分布既不可能也不必要，真正有价值的往往是一个整体结论，例如"这台设备的输出噪声分布是否与标定值一致"。

这类任务的经典瓶颈很直观：造成两分布差异的元素可能极其稀有——某个元素只承担 \(1/N\) 量级的概率质量，经典采样平均要 \(\Theta(N)\) 次才能见到它一次。而在相干 sampler oracle 模型下，我们可以对"哪些随机种子产生元素 \(i\)"这一谓词做量子计数 (quantum counting)，并用振幅估计 (amplitude estimation) 加速 Monte Carlo 平均，从而获得多项式级的查询加速。

本课推导三件事：

  • 把 \(L_1\) 距离 \(\|P-Q\|_1\) 改写成混合分布下一个有界函数的期望（这是整个算法的代数核心）；

  • 用嵌套的量子计数与 heavy/light 分桶，在固定精度下以 \(\widetilde O(\sqrt N)\) 次查询估计一般两分布的 \(L_1\) 距离（该模型下经典需要 \(\Omega(N)\)）；

  • 对两个特殊 promise——uniformity（\(P\) 是否均匀）与 orthogonality（\(P,Q\) 支持集是否不交）——用碰撞概率（二阶矩）把查询数进一步压到 \(O(N^{1/3})\)（经典下界为 \(\Omega(N^{1/2})\)）。

历史上，量子计数由 Brassard、Høyer 与 Tapp 在 1998 年系统建立（Zoo 16），它把 Grover 迭代变成一台"振幅读数器"：对标记比例未知的搜索问题，先对 Grover 算子做相位估计读出标记比例，再据此决定迭代次数。Bravyi、Harrow 与 Hassidim 在 2009 年把这套工具引入分布测试，给出了本课的主要结果（Zoo 117）：他们观察到 sampler oracle 恰好提供了"对分布做相干读数"的接口，使一系列经典上需要线性样本的测试任务获得平方根级乃至更好的加速。Montanaro 在 2015 年把"振幅估计加速 Monte Carlo"整理为一般框架（Zoo 265），本课第 6 节采用他的统一视角回望分布测试。读者应已掌握本站第 3 章的 Grover 搜索与相位估计；量子计数本质上就是"对 Grover 迭代算子做相位估计"，这里只引用其误差结论，不重新推导。

最后提醒本章的记账方式：与第 11 章其他课一致，我们只数 oracle 查询次数，不把电路深度、经典后处理或数据结构维护计入；文中会明确指出哪些结论是模型依赖的。

各节安排。 第 1 节钉死输入模型；第 2 节证明全课的代数核心（\(L_1\) 距离的期望表示）；第 3 节解决单点概率估计与多尺度预算，得到一般 \(L_1\) 估计的 \(\widetilde O(\sqrt N)\)；第 4、5 节分别在 uniformity 与 orthogonality 两个 promise 问题上用碰撞矩做到 \(O(N^{1/3})\)；第 6 节退后一步，把一切嵌入量子 Monte Carlo 的统一框架；第 7 节是一个可完整手算的数值例子。

本课知识点

  1. 可逆 sampler oracle 模型——能写出 sampler oracle 的定义并计算元素的原像比例 \(p_i\)，说明"经典调用即测量"与"保持叠加"两种用法的信息差别，并解释复杂度结论为何必须先绑定输入模型。

  2. L1 距离的混合分布期望表示——能推导 Lemma 1，把 \(\|P-Q\|_1\) 改写成混合分布 \(R\) 下有界函数 \(g\) 的期望，并解释概率权重与 \(g\) 的分母精确抵消的原因。

  3. 单点概率的量子计数与误差刻度——能解释量子计数误差 \(O(\sqrt{p_i}/T+1/T^2)\) 中两项的含义，按目标精度换算所需查询数 \(T\)，并说明 heavy/light 分桶与截断估计器如何控制总 bias。

  4. Uniformity 测试与碰撞概率——能证明 \(C(P)-1/N=\|P-U\|_2^2\)，用 Cauchy–Schwarz 把 \(L_1\) 偏离换算成碰撞盈余，并对成本 \(f(r)=r+N/r^2\) 完成预算平衡得到 \(O(N^{1/3})\)。

  5. Orthogonality 测试与跨分布碰撞——能解释交叉碰撞矩 \(\sum_ip_iq_i\) 为何是支持集不交的精确判据，对成本 \(f(r)=r+\sqrt{N/r}\) 完成预算平衡，并说明 promise 的 gap 为何决定可判定性。

  6. 量子 Monte Carlo 统一框架——能推导经典 Monte Carlo 的 \(1/\epsilon^2\) 壁垒与振幅估计的 \(1/\epsilon\) 精度依赖，并解释分布测试为何要在模板内部再嵌一层量子计数。

  7. 数值实例验证——能在具体分布上完整计算 \(L_1\) 距离、混合分布、逐点 \(g\) 值与碰撞矩，逐项验证 Lemma 1、Lemma 2 与 Cauchy–Schwarz 链。

1. 输入模型先于复杂度

讨论查询复杂度之前，必须先钉死输入模型——同一个"分布"用不同方式交给算法，结论完全不同。这是分布测试文献中反复强调、却最容易被忽略的一点。

一点经典背景。 在纯样本模型下，经典性质测试在两千年前后发展出一套成熟理论：人们发现许多判定问题并不需要 \(\Theta(N)\) 个样本——例如 uniformity 用 \(O(\sqrt N)\) 个样本即可测试（靠数碰撞），但两分布的一般 \(L_1\) 距离估计却逃脱不了线性样本。换言之，"判定"与"估计"、以及"特殊 promise"与"一般情形"之间的样本复杂度可以相差悬殊。本课的量子结果恰好沿着同一条分界线推进：能借助二阶矩结构的特殊问题，量子加速更彻底（\(N^{1/3}\) 对 \(\sqrt N\)）；只能逐点比较的一般问题，量子只给出平方根级加速（\(\sqrt N\) 对 \(N\)）。

定义（可逆 sampler oracle）。 分布 \(P\) 定义在 \([N]=\{1,\dots,N\}\) 上。称酉算子 \(O_P\) 是 \(P\) 的 sampler oracle，如果它作用在种子寄存器 \(s\in[S]\) 与输出寄存器上，满足

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

并且均匀随机取种子时恰好复现分布 \(P\)：

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

换句话说，\(P\) 由一个确定性函数 \(P:[S]\to[N]\) 加上均匀种子生成；\(p_i\) 就是元素 \(i\) 的原像比例。\(O_Q\) 类似地刻画 \(Q\)。这个模型并不空泛：任何"用均匀随机比特驱动一个经典采样电路"的实用随机数生成器，都可逆化后成为这样的 oracle（经典可逆计算的标准构造，把每步的随机比特保留在种子寄存器中即可）。

一个微型实例。 取 \(S=4\)、\(N=2\)，令 \(P(0)=P(1)=P(2)=1\)、\(P(3)=2\)，则 \(p_1=3/4\)、\(p_2=1/4\)——这是一枚偏差 \(3/4\) 的硬币，用两个均匀比特实现。\(O_P\) 是作用在 \(2+1\) 个量子比特上的置换（把 \(|s,0\rangle\) 映到 \(|s,P(s)\rangle\)、其余基矢任意延拓成可逆映射）。制备 \(\frac12\sum_{s=0}^{3}|s,0\rangle\)、调用 \(O_P\) 后，输出寄存器为 \(|1\rangle\) 的振幅平方和恰为 \(3/4\)：量子计数要读的就是这个数。

这个模型有两种退化用法和一种"过强"变体，必须区分清楚：

  • 经典调用 = 测量。把 \(|s,0\rangle\) 制备好（甚至可以叠加制备）、调用 \(O_P\)、然后测量两个寄存器，等价于经典地抽一个 \(s\) 再输出 \(P(s)\)。所以该模型下的经典算法就是普通的样本算法，量子算法可用的信息严格不比它少——量子优势必须来自相干操作，而不是来自模型本身多给了什么。

  • 量子用法 = 保持叠加。量子算法可以制备 \(\frac{1}{\sqrt S}\sum_s|s,0\rangle\)，调用一次 \(O_P\) 得到

\[ \frac{1}{\sqrt S}\sum_s|s,P(s)\rangle, \]

然后对谓词 \([P(s)=i]\) 做相位翻转标记。被标记种子的振幅平方和恰为 \(p_i\)，于是 amplitude estimation / 量子计数能把 \(p_i\) "读"出来。这是经典采样做不到的操作：经典样本一次只暴露一个 \((s,P(s))\) 对，而相干叠加把全部 \(S\) 个原像的比例压缩进一个振幅，等待被相位估计读出。

  • 若只给若干已测量的样本，上述相干操作完全无法实现——没有 \(O_P\) 这台可逆机器，就没有叠加可保持，本课所有算法立即失效。若直接给 amplitude encoding \(\sum_i\sqrt{p_i}|i\rangle\)，则是另一个不同且可能更强的模型：它绕过种子结构，直接暴露概率的平方根，可能让某些任务（如用 swap test 估计 \(\sum_i\sqrt{p_iq_i}\)）变得更容易。因此引用任何复杂度结论前，先确认它属于哪个模型。

要估计的量。 本课用 \(L_1\) 距离（全变差距离的 2 倍）衡量两分布的差异：

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

上界 \(2\) 在支持集完全不交时取到：此时对每个 \(i\) 都有 \(|p_i-q_i|=p_i+q_i\)，求和得 \(\sum_ip_i+\sum_iq_i=2\)。\(L_1\) 距离有明确的操作含义——\(\frac12\|P-Q\|_1\) 是用一次抽样区分两分布的最优优势——因此它是分布测试中最常用的距离。

测试问题通常带 promise：承诺要么 \(\|P-Q\|_1\le a\)，要么 \(\|P-Q\|_1\ge b\)，其中 gap \(b-a>0\) 为常数。gap 是常数不等于精度免费：估计器本身的加性精度必须小于 \(b-a\) 才能区分两情形，精度对复杂度的影响必须单独写进表达式，不能藏在 \(O\) 里。

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

朴素思路是"逐元素估计 \(p_i,q_i\) 再相加"：\(N\) 个未知量，每个都要估到 \(\epsilon/N\) 精度才能让总和误差不超过 \(\epsilon\)，代价随 \(N\) 线性甚至更高地膨胀。绕开它的关键一步，是把这 \(N\) 项和改写成单个有界随机变量的期望——期望正是 Monte Carlo 方法（及其量子加速）的标准处理对象：一个有界量的均值可以用与 \(N\) 无关的样本数估到常数精度。

定义混合分布 \(R\) 与逐点比值函数 \(g\)：

\[ r_i=\frac{p_i+q_i}{2}, \qquad g(i)=\frac{2|p_i-q_i|}{p_i+q_i}\quad(\text{对 }r_i>0). \]

\(R\) 就是"掷一枚均匀硬币，正面从 \(P\) 采样、反面从 \(Q\) 采样"所得的分布，因此从 \(R\) 采样在操作上毫无困难（两个 sampler 都有，各以一半概率调用即可）。\(g(i)\) 度量的是元素 \(i\) 处两分布的相对差异：分子是该点的绝对差异，分母把差异按该点的总质量归一化。

Lemma 1. \(g(i)\in[0,2]\)，且

\[ \mathbb E_{i\sim R}[g(i)]=\|P-Q\|_1. \]

证明。 先证有界性。\(g(i)\ge0\) 显然。对 \(g(i)\le2\)，注意非负数满足三角不等式的退化形式 \(|p_i-q_i|\le p_i+q_i\)（因为 \(p_i-q_i\le p_i\le p_i+q_i\)，同理 \(q_i-p_i\le p_i+q_i\)），于是

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

再证恒等式。把期望按定义展开，代入 \(r_i\) 与 \(g(i)\)：

\[ \mathbb E_{i\sim R}[g(i)] =\sum_{i:\,r_i>0}r_i\,g(i) =\sum_{i:\,r_i>0}\frac{p_i+q_i}{2}\cdot\frac{2|p_i-q_i|}{p_i+q_i} =\sum_{i:\,r_i>0}|p_i-q_i|. \]

第二步只是代入；第三步约去公共因子 \(\frac{p_i+q_i}{2}\)——这正是把 \(g\) 定义成"除以 \(p_i+q_i\)"的原因：概率权重 \(r_i\) 与 \(g\) 的分母精确抵消。最后，\(r_i=0\) 意味着 \(p_i=q_i=0\)（两者都非负），这些 \(i\) 对 \(\|P-Q\|_1\) 的贡献本来就是 \(0\)，所以求和可以补回全体 \(i\)：

\[ \sum_{i:\,r_i>0}|p_i-q_i|=\sum_{i=1}^N|p_i-q_i|=\|P-Q\|_1. \]

Q.E.D.

这个恒等式为什么有用。 它把"\(N\) 个未知量的和"变成"一个取值在 \([0,2]\) 的随机变量的均值"。后者是标量估计问题：不断从 \(R\) 采样 \(i\)、在 \(i\) 处求值 \(g(i)\)、取平均，就能逼近 \(\|P-Q\|_1\)，所需样本数由 \(g\) 的界决定而非由 \(N\) 决定。有界性在这里承担双重职责：对经典 Monte Carlo，它界定方差；对量子 amplitude estimation，有界（可旋转进一个辅助比特）是编码的前提。

算法骨架因此是两层结构：

  1. 外层：随机选择 \(P\) 或 \(Q\)（各 \(1/2\) 概率）并采样 \(i\sim R\)，最后对所有得到的 \(g(i)\) 值估计均值；

  2. 内层：对抽到的这个具体的 \(i\)，估计 \(p_i\) 与 \(q_i\)，代入算出 \(g(i)\)。

第 3 节处理内层，第 6 节处理外层的加速。这里已经能看出难点所在：\(g(i)\) 不是一个可以直接查询的黑盒函数——它依赖未知概率 \(p_i,q_i\)，内层估计的误差会传播成外层均值的偏差（bias）。注意 bias 与方差是两回事：采样平均能压方差，却压不掉系统性的偏差；控制内层误差到外层 bias 的传播，正是算法的核心技术部分。

另外说明一下精度目标。对判定问题（promise 为 \(\|P-Q\|_1\le a\) 或 \(\ge b\)），把 \(\mathbb E_R[g]\) 估到小于 \(b-a\) 的加性精度即可下结论，不需要相对精度；由于 \(g\) 取值于 \([0,2]\)，常数加性精度是有意义的目标——这正是"期望表示"相对于"逐项求和"省钱的根本原因。

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

固定 \(i\)。在态 \(\frac{1}{\sqrt S}\sum_s|s,P(s)\rangle\) 上，谓词 \(P(s)=i\) 的成功概率恰好是 \(p_i\)（第 1 节的原像比例）。对它做量子计数（Grover 迭代 + 相位估计），约 \(T\) 次 oracle 调用后得到估计 \(\widetilde p_i\)，误差典型包含两项：

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

逐项理解这个界：

  • 第一项 \(\sqrt{p_i}/T\) 是"相对误差"项。它随 \(\sqrt{p_i}\) 缩放：要把它压到加性精度 \(\delta\)，需要 \(T\sim\sqrt{p_i}/\delta\)；要压到相对精度 \(c\)（即误差 \(\le cp_i\)），需要 \(T\sim1/(c\sqrt{p_i})\)。注意 \(1/\sqrt{p_i}\) 这个因子：\(p_i\) 越小，相对精确估计越贵。这不是实现的拙劣，而是振幅估计的本征刻度——Grover 角度 \(\arcsin\sqrt{p_i}\approx\sqrt{p_i}\) 本身随 \(p_i\) 变小而变小，相位估计要分辨它就得付出反比的迭代次数。

  • 第二项 \(1/T^2\) 是绝对地板。即使 \(p_i=0\)，有限相位分辨率的读出误差也以 \(1/T^2\) 量级存在。当 \(p_i\ll1/T^2\) 时它取代第一项成为主导。

由此得到全课最重要的设计原则：不能对所有 \(i\) 要求同一精度。算一笔账：若某元素 \(p_i\approx1/N\)，对它要求常数相对精度就要 \(T\sim\sqrt N\) 次调用；\(N\) 个这样的元素逐个处理，总成本 \(N^{3/2}\)，比经典还差。解决办法是 heavy/light 分桶加截断估计：

  • 分桶。按 \(r_i=\frac{p_i+q_i}{2}\) 的数量级把元素分层。由 Markov 不等式，满足 \(r_i\ge\tau\) 的元素至多有 \(\sum_i r_i/\tau=1/\tau\) 个（注意 \(\sum_i r_i=\frac{1+1}{2}=1\)）：质量大的元素很少，可以逐个精估，总预算是"个数少"与"单价贵"的乘积，可控。

  • 轻元素。\(r_i\) 很小的元素单点估计误差大，但它们被 \(R\) 抽中的概率也小，对期望 \(\mathbb E_R[g]\) 的总贡献天然受控——期望误差是每个点的误差再乘以 \(r_i\) 加权，而 \(g\) 本身有界（Lemma 1），所以轻元素上允许粗糙的估计。

  • 截断估计器。实际操作的是

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

即把估计值直接代入 \(g\) 的公式。危险点在分母：当 \(\widetilde p_i+\widetilde q_i\) 极小时，比值的微小扰动会被放大，bias 失控。处理办法是分母太小时换用一个有偏但有界的替代值（例如直接输出一个保守常数）：引入的偏差被 \(g\) 的整体有界性 \([0,2]\) 与该点的小权重 \(r_i\) 双重压制，层层求和后总 bias 控制在常数精度以内。

一个数值感觉。 取 \(N=10^6\)。质量 \(p_i\approx1\) 的重元素（至多几个）用常数次调用就能估到常数相对精度；质量 \(p_i\approx1/N\) 的元素用 \(T\sim\sqrt N=10^3\) 次调用才能估到常数相对精度——单点确实贵，但这样的"临界元素"同时满足两个缓解条件：被 \(R\) 抽中的概率只有 \(10^{-6}\) 量级，且算法对它们并不要求相对精确（粗糙估计 + 有界截断即可）。\(\widetilde O(\sqrt N)\) 的总量级正来自这一最难点，其余档位都更便宜。

外层均值 \(\mathbb E_R[g]\) 同样用 amplitude estimation 加速（第 6 节展开）。还有一个标准的收尾步骤：单次估计的成功概率只需是常数（如 \(2/3\)），独立重复 \(O(\log\frac1\delta)\) 次取中位数即可把成功概率提到 \(1-\delta\)；这个对数因子连同精度因子一起被 \(\widetilde O\) 吸收。把各层的精度预算按上述原则分配、连乘求和，固定加性精度下的总查询数为

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

其中 \(\widetilde O\) 隐藏精度参数与对数因子。这个 \(\sqrt N\) 不是"一次查询读出整张分布表"：它来自内层量子计数的 \(1/\sqrt{p_i}\) 刻度、分桶层数、外层振幅估计三者预算的乘积平衡。粗略地说，最难处理的元素质量在 \(1/N\) 量级，对它们做有意义分辨的量子计数成本正是 \(\sqrt N\) 量级，其余元素更便宜，总成本由这一档主导。

作为对照，同一 oracle 模型下经典算法估计一般两分布的 \(L_1\) 距离需要 \(\Omega(N)\) 级调用——直觉是差异可能藏在某个质量 \(1/N\) 的元素上，经典采样本质上是逐一"撞见"元素，\(\Omega(N)\) 次之前根本无法保证见到它，更无法判断 \(P\) 与 \(Q\) 在该点是否有差异。量子计数把"撞见"换成"对原像比例做相干读数"，省掉了逐个遭遇的开销。

4. Uniformity 与二阶碰撞矩

现在看第一个带 promise 的特殊问题：uniformity testing——判定 \(P\) 是均匀分布 \(U\)（\(U_i=1/N\)），还是 \(\|P-U\|_1\ge\epsilon\)。一般 \(L_1\) 估计的 \(\widetilde O(\sqrt N)\) 在这里可以被进一步压低，关键在于换一个二阶检验量：不再逐点比较，而是比较整体的"集中程度"。

定义（碰撞概率）。 从 \(P\) 独立抽两个样本，它们相等的概率

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

称为碰撞概率，也就是分布的 \(L_2\) 范数平方。对均匀分布，\(C(U)=\sum_i1/N^2=1/N\)。直觉上，分布越集中，两个独立样本越容易撞上，\(C(P)\) 越大；均匀分布是最"散"的分布，碰撞概率应当最小。下面的引理把这句直觉变成恒等式。

Lemma 2.

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

特别地 \(C(P)\ge1/N\)，等号当且仅当 \(P=U\)。

证明。 把平方展开，逐项求和：

\[ \sum_i\left(p_i-\frac1N\right)^2 =\sum_i\left(p_i^2-\frac{2p_i}{N}+\frac1{N^2}\right) =\sum_i p_i^2-\frac{2}{N}\sum_i p_i+\frac{1}{N^2}\cdot N. \]

利用归一化 \(\sum_i p_i=1\)，后两项合并为 \(-\frac{2}{N}+\frac{1}{N}=-\frac1N\)，于是

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

由于右端是平方和，它非负，且为 \(0\) 当且仅当每个 \(p_i=1/N\)。Q.E.D.

Lemma 2 说：偏离均匀的程度被碰撞概率的盈余精确度量，而且 \(L_2\) 盈余对"小的、分散的偏离"比 \(L_1\) 更敏感（平方把负偏差也翻成正贡献）。两个距离之间由 Cauchy–Schwarz 不等式衔接：若 \(\|P-U\|_1\ge\epsilon\)，则

\[ \epsilon^2 \le\left(\sum_i\left|p_i-\frac1N\right|\right)^2 \le N\sum_i\left(p_i-\frac1N\right)^2 =N\,\|P-U\|_2^2, \]

第二个不等号是 Cauchy–Schwarz \((\sum_i1\cdot|x_i|)^2\le(\sum_i1^2)(\sum_ix_i^2)\) 对 \(x_i=p_i-1/N\) 的直接应用。整理得

\[ C(P)=\frac1N+\|P-U\|_2^2\ge\frac1N+\frac{\epsilon^2}{N}. \]

于是 uniformity testing 化归为一个碰撞率分辨问题：区分 \(C(P)=1/N\)（均匀）与 \(C(P)\ge1/N+\epsilon^2/N\)（\(\epsilon\)-远）。注意分辨窗口只有 \(\epsilon^2/N\)——绝对量很小，这是问题的难点。代入数字感觉一下：\(N=10^6\)、\(\epsilon=0.1\) 时窗口为 \(\epsilon^2/N=10^{-8}\)，即要在 \(10^{-6}\) 的基线上分辨出百分之一量级的相对盈余。但碰撞概率有一个 \(L_1\) 没有的优势：它是成对事件的概率，谓词"两个种子产生同一输出"（即 \(P(s)=P(s')\)）可以在种子对上直接定义并做量子计数，而不需要先逐点知道任何 \(p_i\)。逐点 \(L_1\) 估计必须先认出"是哪个元素"，碰撞估计只需要认出"是不是同一个"。

量子算法分两步：

  • 少量抽样捕捉 heavy elements。先抽约 \(r\) 个样本，凡质量足够大的元素会以高概率在样本中现身（质量 \(\gtrsim1/r\) 的元素在 \(r\) 次抽样中几乎必然出现），对它们单独处理：逐个量子计数估计其 \(p_i\)，算出对 \(C(P)\) 的贡献 \(\sum p_i^2\)。

  • 轻元素上估计二阶矩。剩余元素单个概率小（粗略地 \(\lesssim1/r\)），对它们在"成对碰撞"谓词上做 collision finding / 量子计数，直接估计总量 \(\sum_{i\text{ 轻}}p_i^2\)，而不必逐个估计 \(p_i\)——绕开逐点分辨正是节省的来源。

预算平衡（启发式记账，忽略精度与对数因子）：重元素部分的成本随 \(r\) 增长（抽样 \(r\) 次，再对至多 \(r\) 量级的现身元素各做计数），记为 \(r\) 量级；轻元素部分的可分辨盈余随 \(r\) 衰减——单个轻元素质量不超过 \(1/r\)，而 \(N\) 个元素的总碰撞贡献粗略按 \(N\cdot(1/r)^2=N/r^2\) 缩放，检测成本与之反相关，记为 \(N/r^2\) 量级。总成本取

\[ f(r)=r+\frac{N}{r^2}, \]

求极小：\(f'(r)=1-2N/r^3=0\) 给出 \(r^3=2N\)，即

\[ r\asymp N^{1/3},\qquad f(r)\asymp N^{1/3}. \]

平衡点上两项同阶——这是"两参数预算取最优"的一般特征：若一项随 \(r\) 递增、一项随 \(r\) 递减，极小值必在两者相等处附近（递增项再压就亏，递减项再压也亏）。于是固定 \(\epsilon\) 下 uniformity testing 的查询数为

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

而经典下界为 \(\Omega(N^{1/2})\)。经典侧也有个直观的对照：碰撞本身就稀有——均匀分布下大约 \(\sqrt N\) 个样本才期望出现第一次碰撞（生日悖论），要把碰撞率的基线测准到 \(1/N\) 级别的分辨率，经典算法必须积累足够多的碰撞事件，把统计涨落压到窗口 \(\epsilon^2/N\) 以下，这迫使样本数达到 \(\sqrt N\) 量级。量子算法用相干计数取代"数碰撞次数"，把同一分辨任务的代价再降一档：从 \(N^{1/2}\) 到 \(N^{1/3}\)。

两点补充说明。其一，这里给出的是判定算法：输出"均匀"或"\(\epsilon\)-远"，允许常数错误概率（再按第 3 节的中位数技巧放大）；若改成把 \(C(P)\) 估计出来，精度的 \(\epsilon\) 依赖要单独分析。其二，本节的成本分解与 \(r\) 的选取是模型与实现依赖的启发式描述；严格的多尺度预算分配（包括 \(\epsilon\) 的确切指数）见参考文献中 Bravyi–Harrow–Hassidim 的原文。

5. Orthogonality 与跨分布碰撞

第二个特殊问题：orthogonality testing——判定 \(P\) 与 \(Q\) 的支持集是否不相交（例如：两台设备产生的故障码集合是否完全不重叠）。检验量是跨分布碰撞概率（交叉二阶矩）

\[ \sum_{i=1}^N p_iq_i=\Pr_{i\sim P,\,j\sim Q}[i=j], \]

等号由独立性直接展开：\(\Pr[i=j]=\sum_k\Pr[i=k]\Pr[j=k]=\sum_kp_kq_k\)。

为什么它是正交性的精确判据。 每一项 \(p_iq_i\ge0\)，非负项之和为 \(0\) 当且仅当每项都为 \(0\)，即对每个 \(i\) 都有 \(p_i=0\) 或 \(q_i=0\)——这正是支持集不交的定义。所以

\[ P,Q\text{ 支持集不交}\iff\sum_ip_iq_i=0. \]

反过来，若承诺 overlap \(\sum_ip_iq_i\) 足够大（"far from orthogonal"一侧的 promise），交叉碰撞矩就是一个等待被检测的正信号。

算法。 把第 4 节的"同分布碰撞"换成"跨分布命中"：

  • 建表（setup）。从 \(P\) 抽取并存储约 \(r\) 个代表元素，构成查找表。这一步花 \(r\) 次采样。

  • 量子搜索命中（Grover）。在 \(Q\) 的 sampler 的种子空间上做振幅放大：谓词取"\(Q(s)\) 落在表中"。一个均匀随机的 \(Q\) 种子命中表的概率是 \(\sum_{i\in\text{表}}q_i\)；启发式地，若两分布的质量大致摊在 \([N]\) 上、表覆盖了约 \(r\) 个元素，这个命中比例在 \(r/N\) 量级，Grover 搜索找到命中种子的成本因而是 \(\sqrt{N/r}\) 量级（Grover 迭代次数反比于目标振幅的平方根，见第 3 章）。

预算平衡（同样为启发式记账）：setup 成本 \(r\) 随表长线性增长，Grover 成本 \(\sqrt{N/r}\) 随表长下降——表越大，单次搜索越便宜，但建表越贵。总成本

\[ f(r)=r+\sqrt{\frac{N}{r}}. \]

令两项同阶求解：\(r=\sqrt{N/r}\)，两边平方得 \(r^2=N/r\)，即 \(r^3=N\)。也可用求导验证：\(f'(r)=1-\frac{\sqrt N}{2}r^{-3/2}=0\) 给出 \(r^{3/2}=\sqrt N/2\)，同样 \(r\asymp N^{1/3}\)。代回得两项均为 \(N^{1/3}\) 量级，总查询

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

严格算法还需分桶：重元素天然容易被表命中（它们的 \(q_i\) 大），轻元素则贡献大量小概率命中，逐层分配 Grover 预算后再平衡，结论仍是 \(r=N^{1/3}\) 这个指数。

查询成本与时间成本。 与本章其他课一样，\(O(N^{1/3})\) 数的是 oracle 调用。建表一步还隐含 \(r\) 规模的存储与查找开销：种子命中判定"\(Q(s)\in\text{表}\)"需要对表做检索，若用无序查找会带来额外因子，用有序结构或哈希则摊还到对数级。这些不改变查询复杂度指数，但把"查询优势"兑现为"时间优势"时必须单独记账。

Promise 条款必须说清楚。 若两分布只在总质量 \(2^{-N}\) 上重叠，任何固定精度的测试都不要求——也不可能廉价地——发现这点质量：命中概率 \(2^{-N}\) 意味着 Grover 搜索也要 \(\sqrt{2^N}\) 次迭代才能看到它一次，这与"正交"在指数级查询内不可区分。因此复杂度结论只对"orthogonal vs. far from orthogonal"这种带常数级 gap 的 promise 问题成立：是 gap 的大小而不是"是否严格正交"决定查询数。这一点对所有分布测试任务都适用——promise 的 gap 一旦允许随 \(N\) 指数缩小，多项式查询的结论立即失效。

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

退一步看，本课所有内层、外层估计都套着同一个模板。许多统计量可以写成有界随机变量的期望

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

经典 Monte Carlo 的做法：独立采样 \(X_1,\dots,X_m\)，输出经验均值 \(\hat\mu=\frac1m\sum_kf(X_k)\)。由于 \(f\in[0,1]\)，单个样本的方差 \(\operatorname{Var}[f]=\mathbb E[f^2]-\mu^2\le\mathbb E[f]-\mu^2=\mu(1-\mu)\le1/4\)，经验均值的标准差为

\[ \sqrt{\frac{\operatorname{Var}[f]}{m}}\le\frac{1}{2\sqrt m}. \]

要把它压到 \(\epsilon\) 以下需要 \(m=O(1/\epsilon^2)\) 个样本——这就是著名的"\(1/\epsilon^2\) 壁垒"：\(\epsilon\) 每精确一位，样本数变为 100 倍。

量子 Monte Carlo：若采样过程（即 sampler oracle）与 \(f\) 的求值都能相干、可逆地实现，就可以制备一个叠加态，使某个标志子空间的振幅平方恰为 \(\mu\)——先把 \(X\) 按分布叠加制备，再按 \(f(x)\) 把一个辅助比特从 \(|0\rangle\) 向 \(|1\rangle\) 旋转相应角度，辅助比特为 \(1\) 的总概率正是 \(\mathbb E[f]\)。然后对 \(\mu\) 做 amplitude estimation：读出误差从"\(1/\sqrt{m}\) 型统计涨落"换成"\(1/T\) 型相位分辨率"，误差 \(\epsilon\) 只需 \(O(1/\epsilon)\) 次调用——对精度依赖是平方加速。Montanaro 的框架（Zoo 265）把这条从具体到一般的路线整理清楚，并讨论了在矩条件更弱的情形下仍能保留的加速。

分布测试为什么不能只引用平方加速口号。 套用模板需要 \(f\) 可相干求值，而第 2 节选出的 \(f=g\) 依赖未知概率 \(p_i,q_i\) 本身——我们没有一个现成的 \(g\) oracle，每算一次 \(g(i)\) 都要现场跑量子计数（第 3 节），其成本随 \(r_i\) 的数量级剧烈变化。于是不得不在模板内部再嵌一层：内层概率估计 + heavy/light 分桶 + 截断偏差控制。本课的价值正在于展示：当目标函数不是黑盒、而是要边估计边求值时，怎样把 Monte Carlo 加速保下来——以及为此付出的代价如何体现在 \(\widetilde O(\sqrt N)\) 这类表达式的每个因子里。

作为对照，若 \(f\) 真是黑盒（例如 \(f\) 由一段可逆经典电路给出），嵌套层消失，\(\mu=\mathbb E[f]\) 的估计就是干净的 \(O(1/\epsilon)\)：制备叠加 \(\sum_x\sqrt{p_x}|x\rangle\)，受控旋转写入 \(f(x)\)，一次 amplitude estimation 收尾。第 4、5 节的碰撞矩估计之所以能做到与 \(\epsilon\) 几乎无关的 \(N^{1/3}\)（固定 \(\epsilon\)），恰恰是因为碰撞谓词"两输出相等"是现成的黑盒，不需要内层概率估计。

7. 小例子

取 \(N=4\) 上的两个分布

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

第一步：\(L_1\) 距离。 逐项算 \(|p_i-q_i|\)：

\[ |1/2-1/2|+|1/2-0|+|0-1/2|+|0-0| =0+\frac12+\frac12+0=1, \]

即 \(\|P-Q\|_1=1\)（满量程 2 的一半：两分布差得很远）。

第二步：混合分布。 \(r_i=(p_i+q_i)/2\) 逐分量给出

\[ R=\left(\frac{1/2+1/2}{2},\,\frac{1/2+0}{2},\,\frac{0+1/2}{2},\,\frac{0+0}{2}\right) =(1/2,\,1/4,\,1/4,\,0), \]

验证归一化：\(1/2+1/4+1/4+0=1\)。

第三步：逐点 \(g\) 值。

\[ g(1)=\frac{2|1/2-1/2|}{1/2+1/2}=0,\qquad g(2)=\frac{2|1/2-0|}{1/2+0}=\frac{1}{1/2}=2,\qquad g(3)=\frac{2|0-1/2|}{0+1/2}=2. \]

元素 1 上两分布完全一致（相对差异为 0）；元素 2、3 各被其中一个分布独占（相对差异取到 Lemma 1 允许的最大值 2）。

第四步：验证期望恒等式。

\[ \mathbb E_{i\sim R}[g(i)] =\tfrac12\cdot0+\tfrac14\cdot2+\tfrac14\cdot2=1=\|P-Q\|_1. \]

第五步：验证碰撞恒等式（Lemma 2）。 \(P\) 的碰撞概率 \(C(P)=(1/2)^2+(1/2)^2=1/2\)，而

\[ \|P-U\|_2^2 =\left(\tfrac12-\tfrac14\right)^2+\left(\tfrac12-\tfrac14\right)^2 +\left(0-\tfrac14\right)^2+\left(0-\tfrac14\right)^2 =4\cdot\tfrac1{16}=\tfrac14 =C(P)-\tfrac14, \]

与 Lemma 2 一致（\(1/N=1/4\)）。再检查 Cauchy–Schwarz 链：\(\|P-U\|_1=1\)，故 \(\epsilon^2/N=1/4\)，恰等于 \(\|P-U\|_2^2=1/4\)——本例中四个 \(|p_i-1/4|\) 全相等，Cauchy–Schwarz 取到等号，说明这一步放缩在最坏情形下是紧的。

第六步：交叉碰撞矩。 \(\sum_ip_iq_i=\frac12\cdot\frac12=\frac14>0\)——orthogonality 测试会报告"非正交"，与两分布共享元素 1 的事实一致；而元素 2、3 的错配（\(p_2q_2=p_3q_3=0\)）对交叉碰撞毫无贡献，却被 \(L_1\) 距离完整捕捉。

第七步：走到极端情形。 把 \(Q\) 换成 \(Q'=(0,0,1/2,1/2)\)，则每个 \(i\) 都有 \(p_iq'_i=0\)，交叉碰撞矩为 \(0\)——严格正交；同时 \(\|P-Q'\|_1=\sum_i(p_i+q'_i)=2\)，取到 \(L_1\) 距离的最大值。两个极端指标在此一致，但第 5 节的 promise 条款提醒的正是中间地带：若 \(Q'\) 把质量的 \(2^{-N}\) 悄悄挪进 \(P\) 的支持集，交叉碰撞矩从 \(0\) 变为 \(2^{-N}\)，"正交"被严格破坏，却没有任何多项式查询的算法需要（或能够）察觉。

这个例子还显示态 overlap 不能直接代替 \(L_1\)：两分布在元素 1 上共享一半质量，若只看"共同的峰值"会以为它们很接近，但 \(L_1\) 距离为 1，差异全部来自其余支持质量的错配。这也是为什么第 1 节强调输入模型：amplitude encoding 态的内积感知的是 \(\sum_i\sqrt{p_iq_i}\) 式的逐点重叠，与 \(L_1\) 是两种不同的几何，混用模型会得到互相矛盾的"结论"。

8. 小结

  • 模型先行：相干 sampler oracle 允许对某元素的 preimage 比例做量子计数；已测量的经典样本不够用，amplitude encoding 又是另一个（可能更强的）模型。复杂度结论必须先绑定模型。

  • 代数核心：\(L_1\) 距离是混合分布 \(R\) 下有界比值函数 \(g(i)=2|p_i-q_i|/(p_i+q_i)\) 的期望，概率权重与 \(g\) 的分母精确抵消（Lemma 1）。

  • 量子计数的刻度：估计 \(p_i\) 的成本按 \(1/\sqrt{p_i}\) 缩放，故不能对每个元素要求同一精度；heavy/light 分桶把"贵但少"与"便宜但糙"的元素分开记账，截断估计器把总 bias 压在常数精度内。

  • 复杂度结论：一般 \(L_1\) 估计 \(\widetilde O(\sqrt N)\)（经典 \(\Omega(N)\)）；uniformity 与 orthogonality 借碰撞矩做到 \(O(N^{1/3})\)（经典 \(\Omega(N^{1/2})\)）。

  • 预算平衡的方法论：setup 成本随参数 \(r\) 增、检测成本随 \(r\) 减，令两项同阶解出 \(r\)——本课两处都得到 \(r\asymp N^{1/3}\)。

  • Promise 条款：所有结论针对常数级 gap；若 overlap 可以小到 \(2^{-N}\)，多项式查询的结论立即失效。

练习题

练习 1【可逆 sampler oracle 模型】（→ 1 节）

  1. 取 \(S=8\)、\(N=4\)，设 \(P\) 把种子 \(\{0,1,2\}\) 映到元素 1、\(\{3,4,5\}\) 映到元素 2、\(\{6,7\}\) 映到元素 3（元素 4 无原像）。写出 \(O_P|s,0\rangle=|s,P(s)\rangle\) 的作用方式，计算每个元素的原像比例 \(p_i\) 并验证 \(\sum_ip_i=1\)；再说明制备均匀种子叠加、调用 \(O_P\) 后只测量输出寄存器，得到的是什么分布。

  2. （模型辨析）构造一对分布 \(P,Q\)，使 Hellinger 距离平方 \(\sum_i(\sqrt{p_i}-\sqrt{q_i})^2\) 很小，但 \(L_1\) 距离为常数级。用你构造的例子解释：为什么必须先声明输入模型（经典样本 / sampler oracle / amplitude encoding），再谈复杂度？

提示：让一个分布在某个元素上集中大部分质量，另一个把这部分质量摊到大量稀有元素上——同样的总差异摊得越开，逐点 \(\sqrt{\ }\) 偏差越小。

练习 2【L1 距离的混合分布期望表示】（→ 2 节）

  1. 对 \(P=(2/3,\,1/3)\)、\(Q=(1/3,\,2/3)\) 写出混合分布 \(R\) 与逐点 \(g\) 值，计算 \(\mathbb E_{i\sim R}[g(i)]\) 并验证它等于 \(\|P-Q\|_1\)。

  2. （直接验证）补全 Lemma 1 的细节：证明对任意非负 \(p,q\) 有 \(|p-q|\le p+q\)，从而 \(g(i)\in[0,2]\)；并说明求和范围从 \(\{i:r_i>0\}\) 扩大到 \([N]\) 为什么不改变等式两边的值。

提示：\(r_i=0\) 意味着 \(p_i\) 与 \(q_i\) 只能同时为 \(0\)。

练习 3【单点概率的量子计数与误差刻度】（→ 3 节）

  1. 设 \(p_i=10^{-4}\)、要求相对精度 \(c=0.1\)（即误差 \(\le cp_i\)）。利用 \(T\sim1/(c\sqrt{p_i})\) 计算所需查询数的量级，并检验误差公式 \(O(\sqrt{p_i}/T+1/T^2)\) 中哪一项在该 \(T\) 下主导。

  2. （嵌套结构）第 3 节的总查询 \(\widetilde O(\sqrt N)\) 依赖 \(N\) 而不只依赖精度 \(\epsilon\)。结合量子计数误差 \(O(\sqrt{p_i}/T+1/T^2)\) 解释：这个 \(N\) 依赖从哪一步进来？如果两分布都被承诺为"每个 \(p_i,q_i\) 要么为 0 要么 \(\ge\delta\)"，\(\widetilde O(\sqrt N)\) 中的 \(\sqrt N\) 应被替换成什么？

提示：最贵的一档是质量 \(\approx1/N\) 的元素，其量子计数成本为 \(\sqrt N\) 量级；把这一档的质量下限提到 \(\delta\) 后再重算。

练习 4【Uniformity 测试与碰撞概率】（→ 4 节）

  1. 取 \(N=4\)、\(P=(1/2,\,1/4,\,1/4,\,0)\)：计算 \(C(P)\) 与 \(\|P-U\|_2^2\)，验证 Lemma 2；再计算 \(\|P-U\|_1=\epsilon\)，并检验 Cauchy–Schwarz 链 \(\epsilon^2\le N\|P-U\|_2^2\) 在本例中是否取等、与正文取等的例子差在哪里。

  2. （恒等式）设 \(P\) 为 \([N]\) 上任意分布。直接展开证明 \(C(P)-1/N=\|P-U\|_2^2\)，并由此推出 \(C(P)\ge1/N\)、等号当且仅当 \(P=U\)。进一步证明：对任意两分布，\(\sum_ip_iq_i\le\frac12(C(P)+C(Q))\)。

提示：第二问对每个 \(i\) 用 \((p_i-q_i)^2\ge0\) 后求和。

练习 5【Orthogonality 测试与跨分布碰撞】（→ 5 节）

  1. 对 \(P=(1/2,\,1/2,\,0)\)、\(Q=(1/2,\,0,\,1/2)\) 计算交叉碰撞矩 \(\sum_ip_iq_i\)，判定支持集是否不交，并计算 \(\|P-Q\|_1\) 作对照。

  2. （预算平衡）对总成本 \(f(r)=r+\sqrt{N/r}\)，分别用"令两项相等"与"求导"两种方法求最优 \(r\)，验证 \(r\asymp N^{1/3}\) 且 \(f(r)\asymp N^{1/3}\)。再把 \(f\) 换成 \(r+N/r^2\)（第 4 节）重做一遍。总结：为什么平衡点处两项总是同阶？

  3. （Promise 的作用）第 5 节断言：overlap 为 \(2^{-N}\) 时多项式查询的测试不存在。用 Grover 迭代次数与命中概率的关系定量说明这一点，并解释为什么"orthogonal vs. overlap \(\ge c\)（\(c\) 为常数）"这个 promise 恰好绕开了该障碍。

提示：命中概率 \(\alpha\) 对应的 Grover 成本约为 \(1/\sqrt\alpha\)；令 \(\alpha=2^{-N}\) 算一算。

练习 6【量子 Monte Carlo 统一框架】（→ 6 节）

  1. 由 \(\operatorname{Var}[f]\le\mu(1-\mu)\le1/4\) 推出经典 Monte Carlo 估计 \(\mu=\mathbb E[f]\) 需要 \(m=O(1/\epsilon^2)\) 个样本；再写出振幅估计把精度依赖压到 \(O(1/\epsilon)\) 的机制（相位分辨率取代统计涨落）。

  2. 解释为什么分布测试的 \(L_1\) 估计不能直接套用 Monte Carlo 模板（\(g\) 不是黑盒、需要内层量子计数与 heavy/light 分桶），而第 4、5 节的碰撞矩估计却能几乎做到与 \(\epsilon\) 无关。

提示：碰撞谓词"两个输出相等"是现成可查询的黑盒，\(g(i)\) 却依赖未知的 \(p_i,q_i\)。

练习 7【数值实例验证】（→ 7 节）

  1. 对 \(P=(1/3,\,1/3,\,1/3,\,0)\)、\(Q=(1/3,\,1/3,\,0,\,1/3)\) 仿照正文步骤计算混合分布 \(R\)、逐点 \(g\) 值与 \(\mathbb E_{i\sim R}[g(i)]\)，并验证期望恒等式。

  2. 把正文例中的 \(Q\) 换成 \(Q'=(0,\,0,\,1/2,\,1/2)\)：验证交叉碰撞矩为 \(0\)、\(\|P-Q'\|_1=2\)（满量程），并说明这对应 orthogonality 测试的哪一个输出。

  3. 对正文的 \(P=(1/2,\,1/2,\,0,\,0)\)、\(Q=(1/2,\,0,\,1/2,\,0)\) 计算态重叠 \(\sum_i\sqrt{p_iq_i}\)，与 \(\|P-Q\|_1=1\) 对照，解释为什么 amplitude encoding 的内积几何不能直接代替 \(L_1\) 距离。

提示：两分布共享元素 1 的一半质量，重叠由 \(\sqrt{p_1q_1}\) 主导，而错配质量只体现在 \(L_1\) 里。

参考文献