Junta 测试与 Gapped Group Testing：从变量影响到对抗界¶
一个 \(k\)-junta 是只依赖 \(n\) 个输入变量中至多 \(k\) 个的布尔函数。本课要解决的性质测试 (property testing) 问题是：给定对函数 \(f\) 的黑盒查询能力，不要求找出函数的真值表，而只要求区分两种情况——\(f\) 确实是 \(k\)-junta，或者 \(f\) 与任何 \(k\)-junta 都至少在 \(\epsilon\) 比例的输入上取值不同。
量子算法解决这个问题的路线可以概括为三步：
把"\(f\) 远离所有 \(k\)-junta"翻译成"任意 \(k\) 个变量之外仍留有可观的 influence / Fourier 质量"；
把"有多少个变量具有某一档 influence"归约为一个新原语——gapped group testing (GGT)；
用对抗界 (adversary bound) 的半定规划为 GGT 直接构造查询算法，并用对称群表示论把它实现得时间高效。
最终的查询复杂度是
其中 \(\widetilde O\) 隐藏 \(\log\) 因子。相比之下，早期的量子 tester（Zoo 267，Atıcı–Servedio）约需 \(O(k/\epsilon)\) 次查询——本课的算法把对 \(k\) 的依赖从线性压到了平方根。下面我们从问题的来历讲起。
本课知识点
Junta 与 far promise——能写出 \(k\)-junta、normalized Hamming 距离与 \(\epsilon\)-far 的定义，并解释 promise 空隙对测试问题为何必要。
Fourier 展开与 Parseval 恒等式——能把 \(F(x)=(-1)^{f(x)}\) 展开到正交归一的奇偶性基上，计算 Fourier 系数并用 Parseval 恒等式验证归一。
Influence 的 Fourier 表达——能用"翻转坐标"与"Fourier 质量"两种方法计算单变量 influence，并补全 Lemma 1 的四步推导。
Junta 的 Fourier 支持与外部质量——能证明 \(J\)-junta 的非零频率都含于 \(2^J\)（Lemma 2），并由 \(\epsilon\)-far 推出任意 \(k\) 个变量之外仍留至少 \(\epsilon\) 的 influence（Lemma 3）。
Fourier sampling 与收集瓶颈——能推导 Fourier sampling 测得 \(S\) 的概率为 \(\widehat F(S)^2\)，并解释 Atıcı–Servedio 式 tester 的 \(O(k/\epsilon)\) 复杂度及其 coupon collector 瓶颈。
GGT 原语与对抗界构造——能写出 GGT 的承诺与复杂度 \(\Theta(\sqrt{k/d})\)，并解释对抗界可行解、置换对称性压缩与 irrelevant variables 设计如何共同给出查询与时间都高效的算法。
Influence 分桶归约——能用分桶与鸽巢论证找出"堆积桶"，把桶内变量检测实现为带噪声 group-test 查询，并把每桶成本平衡到 \(\sqrt{k/\epsilon}\)。
复杂度对比与已知下界——能推导经典随机基准 \((k/d)^2\) 并与量子 \(\sqrt{k/d}\) 比较四次幂差距，能陈述下界 \(\Omega(k^{1/3})\) 并解释 tester "只判定、不学习"的设计原则。
0. 背景：Junta 从哪里来，为什么难测¶
0.1 学习理论中的 junta 问题¶
布尔函数 \(f:\{0,1\}^n\to\{0,1\}\) 可以建模许多对象：一个分类器、一个电路、一个生物网络（例如只有少量基因真正决定某种表型）。在这类模型里，\(n\) 往往很大，而真正起作用的变量——相关变量 (relevant variables)——很少。\(k\)-junta 就是"相关变量至多 \(k\) 个"的函数的正式名称：
定义（\(k\)-junta）. 若存在 \(J\subseteq[n]\)、\(|J|\le k\)，使得 \(f(x)\) 的值只由 \(x\) 在 \(J\) 中坐标（记作 \(x_J\)）决定，则称 \(f\) 是一个 \(k\)-junta。\(J\) 中的变量称为相关的，其余变量称为无关的。
例如 \(f(x)=x_1\oplus x_3\) 无论 \(n\) 多大都是 \(2\)-junta；\(n\) 个变量的奇偶性函数则是 \(n\)-junta，不是任何 \(k<n\) 的 junta。
junta 问题在经典学习理论中早已是核心难题：Mossel、O'Donnell 与 Servedio 等人的工作表明，即使只允许查询（而非随机样本），找出全部相关变量原则上约需 \(k\log n\) 量级的信息，而朴素做法要扫描全部 \(n\) 个变量。Fischer 等人 2004 年开创了 junta 的性质测试版本，Blais 随后给出了近最优的经典 tester。量子版本由 Atıcı 与 Servedio（Zoo 267）首先系统研究；Belovs（Zoo 268）用对抗界给出了对称 junta 的学习算法；本课的主结果来自 Ambainis、Belovs、Regev 与 de Wolf（Zoo 266），他们引入 gapped group testing 这一中间原语，把 tester 的查询复杂度压到 \(\widetilde O(\sqrt{k/\epsilon})\)。Ambainis–Montanaro（Zoo 167）则研究了不带 gap、要求找出全部特殊项的 exact 版本，我们在第 6 节对比。
0.2 性质测试的约定：距离与 far promise¶
测试问题之所以"比学习容易"，是因为它放松了目标：不输出相关变量集合，只输出一个比特的判定。为了使判定良定义，必须规定两个输出对应的函数类之间有空隙——这就是 promise。
定义（距离）. 两个布尔函数 \(f,g\) 的 normalized Hamming 距离为 $\(\operatorname{dist}(f,g)=\Pr_{x}[f(x)\neq g(x)]=\frac{1}{2^n}\bigl|\{x:f(x)\neq g(x)\}\bigr|,\)\( 即 \)x$ 均匀随机时两者取值不同的概率。
定义（\(\epsilon\)-far）. 若对每一个 \(k\)-junta \(g\) 都有 \(\operatorname{dist}(f,g)\ge\epsilon\)，则称 \(f\) 是 \(\epsilon\)-far from \(k\)-juntas，简称"远离所有 \(k\)-junta"。
定义（junta tester）. 一个 \(k\)-junta tester 输入参数 \(k\) 与 \(\epsilon\)，通过查询黑盒 \(f\)（给 \(x\) 得 \(f(x)\)）满足：
若 \(f\) 是 \(k\)-junta，以至少 \(2/3\) 的概率输出"接受"；
若 \(f\) 是 \(\epsilon\)-far from \(k\)-juntas，以至少 \(2/3\) 的概率输出"拒绝"。
对既不满足前者也不满足后者的 \(f\)，输出任意。常数 \(2/3\) 可用标准重复放大提升到 \(1-\delta\)，代价是乘 \(O(\log\frac1\delta)\)。
注意这个 promise 是必要的：若 \(f\) 与某个 \(k\)-junta 只在极少数输入上不同，任何查询算法都很难发现这些输入，区分两者本质上是大海捞针，测试也就失去了意义。
0.3 经典算法的瓶颈¶
经典 tester 的基本手段是随机取 \(x\)、翻转某个坐标看输出是否改变，以此"指控"某个变量是相关的。粗略地说，发现一个新相关变量的代价反比于该变量的 influence（第 1 节定义）；当相关变量很多、各自 influence 又可能低到 \(\epsilon/k\) 量级时，逐个发现它们的开销随 \(k\) 线性（甚至更差）增长。量子的 Fourier sampling（第 2 节）能加速"发现"这一步，但同样受困于低 influence 变量的"收集问题"。真正的突破在于换一个问法：不逐个收集变量，而是批量地问"具有某档 influence 的变量，数目是至多 \(k\) 个还是至少 \(k+d\) 个"——这正是 gapped group testing，其量子查询复杂度 \(\Theta(\sqrt{k/d})\) 由对抗界给出，且在大 gap 时比 Grover 式的平方加速还要好。
0.4 前置知识¶
本课假设读者熟悉：量子态、测量与 Hadamard 变换（ch01）；相位反冲与相位预言机（ch03 的 Deutsch–Jozsa）；Grover 迭代与振幅放大（ch03），特别是"成功概率 \(p\) 的子过程可用 \(O(1/\sqrt p)\) 次调用放大"这一结论。不需要 Fourier 分析的先修——下一节会把它从零建立。
1. 距离、相关变量与 influence¶
本节建立三个工具：单变量 influence、布尔函数的 Fourier 展开、以及"far promise \(\Rightarrow\) 外部 influence 质量"这一关键引理。
1.1 单变量 influence¶
定义（influence）. 变量 \(i\in[n]\) 对 \(f\) 的 influence 是
\[\operatorname{Inf}_i(f)=\Pr_{x}\bigl[f(x)\neq f(x\oplus e_i)\bigr],\]其中 \(x\) 均匀随机，\(e_i\) 是第 \(i\) 位为 \(1\) 的单位向量，\(x\oplus e_i\) 表示把 \(x\) 的第 \(i\) 位取反。
直觉：\(\operatorname{Inf}_i(f)\) 度量"第 \(i\) 个变量有多重要"——随机翻它一下，输出跟着变的概率越大，这个变量越要紧。两个极端：若 \(i\) 是无关变量，\(f(x\oplus e_i)=f(x)\) 恒成立，\(\operatorname{Inf}_i(f)=0\)；若 \(f\) 就是第 \(i\) 位本身（dictator 函数），则输出必跟着变，\(\operatorname{Inf}_i(f)=1\)。
对变量集合 \(S\subseteq[n]\)，也可以定义联合 influence：随机重洗 \(S\) 内的坐标（\(S\) 外保持不变），输出发生变化的概率。第 4 节实现 group-test 查询时用的正是这种"翻转一整个子集"的操作；它也可以用 Fourier 权重表达，但我们只需要上面的概率形式。
1.2 布尔函数的 Fourier 展开¶
把布尔函数的取值换成 \(\pm 1\) 更方便做代数。定义相位函数
于是 \(f(x)\neq f(x')\) 等价于 \(F(x)F(x')=-1\)。对每个子集 \(S\subseteq[n]\) 定义奇偶性基函数 (parity / character)
即 "\(S\) 内坐标的奇偶性" 的 \(\pm 1\) 版本（\(S=\varnothing\) 时 \(\chi_\varnothing\equiv 1\)）。这 \(2^n\) 个函数在均匀分布的内积 \(\langle G,H\rangle=\mathbb E_x[G(x)H(x)]\) 下正交归一：对 \(S\neq T\)，存在某一位 \(i\) 属于 \(S\triangle T\)，沿这一位配对 \(x\) 与 \(x\oplus e_i\) 可使 \(\chi_S(x)\chi_T(x)\) 成对抵消，故 \(\mathbb E_x[\chi_S\chi_T]=0\)；而 \(\mathbb E_x[\chi_S^2]=1\) 是平凡的。函数空间维数也是 \(2^n\)，所以它们构成一组正交归一基，任何 \(F\) 都有唯一展开
系数 \(\widehat F(S)\) 称为 \(F\) 的 Fourier 系数。由正交归一性立刻得到 Parseval 恒等式：
最后一步因为 \(F\) 取值 \(\pm 1\)。这个恒等式是 Fourier sampling 的根基：平方系数构成一个概率分布。
1.3 Influence 的 Fourier 表达¶
Lemma 1. \(\displaystyle\operatorname{Inf}_i(f)=\sum_{S\ni i}\widehat F(S)^2\)：变量 \(i\) 的 influence 恰好等于"含有 \(i\) 的那些频率上的 Fourier 质量"。
证明。第一步，把指示函数写成代数式：\(F(x)\neq F(x\oplus e_i)\) 时两者一正一负，差为 \(\pm 2\)，平方为 \(4\)；相等时差为 \(0\)。因此
第二步，对 \(x\) 取期望。展开平方，注意 \(F^2=1\)，以及"把 \(x\) 换成 \(x\oplus e_i\) 不改变均匀分布"（所以 \(\mathbb E_x[F(x\oplus e_i)^2]=1\)）：
第三步，计算关联项。代入 Fourier 展开：
由 \(\chi_T(x\oplus e_i)=\chi_T(x)\chi_T(e_i)\)（翻转第 \(i\) 位只在 \(i\in T\) 时给奇偶性添一个负号）以及基的正交归一性，\(\mathbb E_x[\chi_S\chi_T]=\delta_{S,T}\)，双重求和塌缩为
第四步，合并。用 Parseval，
因为 \(i\notin S\) 的项贡献 \((1-1)/2=0\)，\(i\in S\) 的项贡献 \((1+1)/2=1\)。Q.E.D.
这个引理把一个组合量（翻转坐标检测输出的概率）和一个谱量（Fourier 系数平方和）等同起来，是整篇教程反复使用的翻译器。
1.4 Junta 的 Fourier 支持¶
Lemma 2. 若 \(f\) 是 \(J\)-junta，则 \(\widehat F(S)\neq 0\) 蕴含 \(S\subseteq J\)：Fourier 支持只出现在 \(2^J\) 上。
证明。取任意 \(S\not\subseteq J\)，要证 \(\widehat F(S)=0\)。存在 \(i\in S\setminus J\)。把求和按"第 \(i\) 位的取值"配对：
由于 \(f\) 不依赖第 \(i\) 位，\(F(x\oplus e_i)=F(x)\)；而由于 \(i\in S\)，\(\chi_S(x\oplus e_i)=-\chi_S(x)\)。括号内两项相消，整个和为零。Q.E.D.
换句话说，junta 的"频谱"集中在一个低维子立方体 \(2^J\) 上。这给出一个直接的侦查手段：只要观测到任何 \(\widehat F(S)\neq 0\) 且 \(S\not\subseteq J\) 的证据，就可以断言 \(J\) 之外还有相关变量。第 2 节的 Fourier sampling 正是把这句话算法化。
1.5 Far promise 给出外部质量¶
测试问题的另一半是"far"情形。下面的引理把 "\(f\) 远离所有 \(k\)-junta" 翻译成一句可用的定量话：任意删掉 \(k\) 个变量，剩下的变量 still 携带至少 \(\epsilon\) 的 influence 总量。
Lemma 3. 设 \(f\) 是 \(\epsilon\)-far from \(k\)-juntas。则对任意 \(J\subseteq[n]\)、\(|J|\le k\)，
证明。证明逆否命题的前半：若存在 \(|J|\le k\) 使外部 Fourier 质量 \(<\epsilon\)，则 \(f\) 不是 \(\epsilon\)-far。构造一个只依赖 \(J\) 的近似函数：先把 \(F\) 的 Fourier 展开截断到 \(J\) 内，
再取符号 \(g(x)=\frac{1-\operatorname{sign}(h(x))}{2}\)（\(h(x)=0\) 时任取一值）。\(g\) 只通过 \(x_J\) 依赖 \(x\)，所以 \(g\) 是 \(k\)-junta。估计距离：当 \(f(x)\neq g(x)\) 时 \(F(x)\) 与 \(h(x)\) 异号（或 \(h(x)=0\)），故 \(|F(x)-h(x)|\ge |F(x)|=1\)，即 \(\mathbf 1[f\neq g]\le (F-h)^2\) 逐点成立。于是
中间的等号就是 Parseval：\(F-h\) 的展开恰好由被截掉的项组成。这与 "\(f\) 是 \(\epsilon\)-far" 矛盾，第一条不等式得证。
第二条由 Lemma 1 推出：
其中 \(\ge\) 是因为每个 \(S\not\subseteq J\) 至少含一个 \(i\notin J\)，其质量 \(\widehat F(S)^2\) 在左边的双重求和中至少出现一次（含多个外部变量时会重复计数，只会更大）。Q.E.D.
Lemma 3 是整个算法的"燃料"：无论 tester 已经锁定了哪个候选变量集 \(J\)（至多 \(k\) 个），far 情形都保证 \(J\) 之外还剩至少 \(\epsilon\) 的 influence 等待被发现。算法剩下的全部工作，就是高效地"收割"这些外部 influence。
2. Fourier sampling 怎样暴露变量¶
Fourier sampling 是量子算法探测布尔函数谱结构的标准原语，其线路与 Deutsch–Jozsa 算法（ch03）几乎相同，区别只在输入态的制备。
线路。从 \(|0^n\rangle\) 出发：
作用 \(H^{\otimes n}\)，得到均匀叠加 \(\frac{1}{2^{n/2}}\sum_x |x\rangle\)；
作用相位预言机 \(O_f:|x\rangle\mapsto(-1)^{f(x)}|x\rangle\)（由标准比特预言机 \(|x\rangle|b\rangle\mapsto|x\rangle|b\oplus f(x)\rangle\) 把目标位置于 \(|-\rangle\) 即得，一次查询），得到
再作用 \(H^{\otimes n}\)，在计算基下测量。
第三步之后，结果 \(y\in\{0,1\}^n\) 的振幅为（用 \(H|x_i\rangle\) 的矩阵元 \((-1)^{x_i y_i}/\sqrt2\) 逐项相乘再求和）
其中 \(S_y=\{i:y_i=1\}\) 是 \(y\) 的支持集，等号就是 \(\widehat F\) 的定义。因此测量结果是子集 \(S\subseteq[n]\)，且测得 \(S\) 的概率为 \(\widehat F(S)^2\)——Parseval 保证这些概率确实归一。一句话总结：Fourier sampling 用 \(O(1)\) 次查询，从"Fourier 平方分布"中采一个样本。
Atıcı–Servedio 式 tester 的思路（Zoo 267）。维护一个候选相关变量集 \(J\)，反复做 Fourier sampling：
若 \(f\) 是 \(J^*\)-junta（\(|J^*|\le k\)），由 Lemma 2 所有非零谱都在 \(2^{J^*}\) 内，采样永远不会给出 \(J^*\) 之外的变量；采样足够多次后若收集到的变量数 \(\le k\)，接受。
若 \(f\) 是 \(\epsilon\)-far 而当前 \(|J|\le k\)，由 Lemma 3 外部质量 \(\sum_{S\not\subseteq J}\widehat F(S)^2\ge\epsilon\)，即每次采样至少有概率 \(\epsilon\) 命中一个 \(J\) 之外的频率，从而暴露一个新变量。期望 \(O(1/\epsilon)\) 次采样发现一个新变量；far 情形迟早收集到第 \(k+1\) 个变量，此时拒绝。
发现 \(k\) 个变量各需 \(O(1/\epsilon)\) 次采样，总查询约 \(O(k/\epsilon)\)。
瓶颈在哪。这个分析对"发现变量"是有效的，但它本质上是一个 coupon collector：变量被逐个收集，每个变量都等到它被采中为止。设想 far 情形的 influence 分布很不均：可能有 \(\Theta(k)\) 个变量各自只带 \(\Theta(\epsilon/k)\) 的 influence。外部质量摊到每次采样上只有 \(\epsilon\)，而其中"命中某个特定低 influence 变量"的概率只有 \(\Theta(\epsilon/k)\)——逐个收集所有这类变量需要 \(\Omega(k\cdot(k/\epsilon))\) 级别的乐观估计也救不回来（实际分析通过只收集到 \(k\) 个为止来避免最坏情形，但 \(O(k/\epsilon)\) 的对 \(k\) 线性依赖由此而来）。要突破对 \(k\) 的线性依赖，必须放弃"逐个收集"，改成批量计数：一次性估计"具有某档 influence 的变量大约有多少个"。这正是下一节原语的动机。
3. Gapped Group Testing 原语¶
3.1 从 group testing 到 gapped 版本¶
经典的 group testing 模型：有一个未知集合 \(A\subseteq[n]\)（"特殊项"，比如人群中的感染者），算法可以查询任意子集 \(S\subseteq[n]\)，oracle 回答
即"这一组里有没有特殊项"。一次查询检测一整个组，这是它优于逐项检查的原因。
本课需要的是它的判定版本。Gapped group testing (GGT) 承诺 \(|A|\) 落在两个不相交的区间之一：
任务只是区分这两种情形，其中 \(d\ge 1\) 是 gap（无需找出 \(A\) 中的任何元素）。
主结果（Zoo 266）：在 \(d\le k\) 时，GGT 的量子查询复杂度为
上界由下文的 adversary 构造给出，下界也来自 adversary 方法，两者匹配到常数。
3.2 为什么这个复杂度值得关注¶
先看经典基准。经典随机算法的自然策略是：每次独立地以概率 \(p\) 把每个下标放入 \(S\)，查询 \(g_A(S)\)，重复多次后比较命中频率。记 \(|A|=a\)。当 \(pa\) 较小时，
即单次查询的命中概率约为 \(pa\)。两种情形（\(a=k\) 与 \(a=k+d\)）的命中率差 \(\Delta\approx pd\)；而每次查询是方差 \(\approx pa\) 的 Bernoulli 变量，要把两个均值分开，由中心极限定理需要的样本数约为
最后调 \(p\)：若 \(p\ll 1/k\)，命中率 \(pk\ll 1\)，绝大多数查询都返回 \(0\)，效率低；若 \(p\gg 1/k\)，两种情形的命中率都饱和到接近 \(1\)，无法区分。最优在 \(p\approx 1/k\) 处取得，代入得样本数 \(\approx k/((1/k)d^2)=(k/d)^2\)。所以经典随机复杂度约为 \((k/d)^2\)（忽略对数）。
对比量子上界 \((k/d)^{1/2}\)：在参数 \(k/d\) 上，经典是 \(2\) 次幂、量子是 \(1/2\) 次幂——比值是四次幂的差距 (quartic gap)，比 Grover 式的"平方加速"（\(2\) 对 \(1\)）还要夸张。特别是当 \(d\ge\sqrt k\) 时，量子只需 \(O(k^{1/4})\) 甚至更少的查询，而经典仍需 \(\Omega((k/d)^2)\)。例如 \(d=\Theta(k)\)（区分 \(|A|\le k\) 与 \(|A|\ge 2k\)）时量子查询是常数级的，而经典需要 \(\Theta(1)\) 次再乘上……不，代入公式：经典 \((k/d)^2=\Theta(1)\)——这个端点两者都是常数。四次幂差距在中间尺度最大：取 \(d=\sqrt k\)，经典约 \(k\) 次，量子约 \(k^{1/4}\) 次。
（读者可能会问：为什么不是 Grover 的 \(\sqrt{\cdot}\) 直接给出 \((k/d)\)？注意这里的 oracle 输入是一整个子集 \(S\) 而不是单个下标，"标记态"的结构是置换对称下的承诺问题，不能直接套用无序搜索的框架；算法必须从承诺问题的结构里再榨出一层加速，这就是下面 adversary 构造的内容。）
3.3 Adversary SDP 与对称性压缩¶
Zoo 266 的上界不是"设计一个电路再分析"，而是先证明对抗界 (adversary bound) 的可行性：对抗方法是量子查询复杂度的通用下界技术，其对偶形式（dual adversary SDP，与 span program 等价）的可行解同时就是一个查询算法的存在性证明——这也是本章前面几课（span program、ordered search）反复使用的对偶框架。
朴素的 dual adversary 向量需要对每个输入（这里是每个 \(A\subseteq[n]\)，共 \(\binom{n}{\le k}+\binom{n}{\ge k+d}\) 个）指派状态，空间是指数大的。Zoo 266 的两个关键观察把它压到多项式尺寸：
置换对称性。oracle \(g_A(S)\) 的值只依赖于 \(|A|\) 与 \(|S\cap A|\)；交换 \([n]\) 的元素不改变问题。因此可以要求 adversary 向量继承对称群 \(S_n\) 的置换对称性，把指数大的子集空间分解为少量 \(S_n\) 的不可约表示 (irreducible representations) 模块，只需在每个模块上给出可行向量。这是"对称性压缩"的标准操作，与 collision 问题的下界证明（本章 collision 一课）同源。
"Irrelevant variables"设计。构造允许在一部分输入 \(S\) 上 adversary 条件不施加约束（形象地说，这些 \(S\) 上的 oracle 值可以"任意"），同时仍保持 adversary 界正确。这个保留条款对 junta 归约至关重要：第 4 节把"检测 influence"实现为 group-test 查询时，得到的 oracle 是带噪声的——在某些查询上它的回答既不保证 \(0\) 也不保证 \(1\)。带 irrelevant inputs 的 GGT 构造恰好能容忍这种不确定性，这是该构造区别于普通 GGT 分析的地方，也是整条归约链能闭合的技术关键。
由 adversary 上界等于（广义）量子查询复杂度这一事实，可行解立刻给出使用 \(O(\sqrt{k/d})\) 次查询的算法；其电路形式是一对双反射 (two reflections) 交替作用的迭代，结构上与振幅放大类似（两个反射复合成旋转），只是反射的轴由 adversary 向量而非均匀叠加给出。匹配的下界 \(\Omega(\sqrt{k/d})\) 同样从 SDP 的可行性读出，所以 \(\Theta(\sqrt{k/d})\) 是紧的。
4. Influence 分桶归约¶
现在把 junta testing 归约到 GGT。核心想法：按 influence 的尺度把外部变量分桶，对每一桶调用一次 GGT。
4.1 分桶与 pigeonhole¶
设 \(f\) 是 \(\epsilon\)-far。由 Lemma 3，任意候选集 \(J\)（\(|J|\le k\)）之外的变量携带总 influence 至少 \(\epsilon\)。把 \(J\) 之外的变量按 influence 大小分桶：第 \(j\) 桶装 influence 落在
附近的变量（即区间 \([\tau_j/2,\tau_j]\) 之类，常数因子不影响渐近）。值得考虑的尺度范围是从 \(\epsilon/k\)（低于它的单桶贡献可忽略）到 \(1\)，所以桶数为
鸽巢论证：每个桶对总外部 influence 的贡献约为"桶内变量数 \(\times\) 该桶尺度"。设第 \(j\) 桶有 \(m_j\) 个变量，则 \(\sum_j m_j\tau_j\ge\epsilon\)（总质量），而桶数只有 \(O(\log(k/\epsilon))\) 个。由平均原理，至少存在一个桶 \(j\) 满足
其中最后一步代入 \(\tau_j=2^j\epsilon/k\)，即 \(\epsilon/\tau_j=k/2^j\)。把对数因子吸进 \(\gtrsim\) 记号，结论写成：
对某个桶 \(j\)，\(J\) 之外至少有 $\(d_j\gtrsim k/2^j\)\( 个变量，每个的 influence 至少约为 \)\tau_j$。
这是归约的关键产出：far 情形必然在某个尺度上"堆积"了大量变量。注意 \(d_j\tau_j\gtrsim\epsilon\) 对所有 \(j\) 成立——这个乘积守恒是后面复杂度平衡的原因。
（严格地说还有第二种情形：大量 influence 极低的变量，单个低于最小桶的阈值，但数目远多于 \(k\)，其联合 influence 仍可达 \(\Omega(\epsilon)\)——随机取一个小子集翻转就能以可检测的概率改变输出。Zoo 266 对这类"极低 influence 但数量庞大"的情形用随机小子集上的联合 influence 检测处理；思想相同，下面我们只展开第一种、也就是最典型的情形。）
4.2 把"桶内变量检测"实现为 group-test 查询¶
GGT 的 oracle 回答"子集 \(S\) 是否含有特殊项"。这里"特殊项"就是第 \(j\) 桶里的变量，\(A\) 是桶内变量集合。我们需要用对 \(f\) 的查询实现
实现方法是翻转测试：均匀随机取 \(x\)，再随机重洗 \(S\) 内的坐标得到 \(x'\)，比较 \(f(x)\) 与 \(f(x')\)。若 \(S\) 含有一个 influence \(\ge\tau_j\) 的变量 \(i\)，那么仅翻转 \(i\) 就有 \(\ge\tau_j\) 的概率改变输出；随机重洗 \(S\) 至少以相当的比例"翻到 \(i\) 这一位"，因此
换句话说，"检测到一次输出变化"这个事件的成功概率 \(p\) 是 \(\Omega(\tau_j)\) 量级的。由振幅放大（ch03：成功概率 \(p\) 的子过程可用 \(O(1/\sqrt p)\) 次调用把成功振幅提升到常数），用
次 \(f\) 查询即可把"\(S\) 是否触发了输出变化"判定到常数置信度——这就是一次带噪声的 group-test 查询的成本。两点说明：
噪声从何而来：\(f\) 里桶外变量（其他尺度的相关变量）也会贡献输出变化，所以 \(g_j\) 的回答并不干净；这正是第 3.3 节 "irrelevant variables" 保留条款要吸收的东西——GGT 构造允许部分查询的回答任意，adversary 界依然成立。
判定的是"含或不含"，这与 GGT 的 oracle 语义完全一致：\(|A|\) 就是桶内变量的数目。
4.3 复杂度平衡¶
现在把账算清。对桶 \(j\) 调用 GGT，区分"桶内变量至多 \(k\) 个"（junta 情形：相关变量总共至多 \(k\) 个，任何桶至多 \(k\) 个）与"至少 \(k+d_j\) 个"（far 情形在该桶的承诺）。查询数为
每次实现成本 \(O(1/\sqrt{\tau_j})\) 次 \(f\) 查询，故该桶总成本
代入第 4.1 节的乘积守恒 \(d_j\tau_j\gtrsim\epsilon\)：
每个桶的成本都平衡到同一个值 \(\sqrt{k/\epsilon}\)——这正是取 \(d_j\propto k/2^j\)、\(\tau_j\propto 2^j\epsilon/k\) 这组"共轭"参数的目的：\(d_j\) 随 \(j\) 指数衰减（高 influence 桶变量少），\(\tau_j\) 随 \(j\) 指数增长（高 influence 桶检测便宜），两种成本在乘积中精确抵消。桶数只有 \(O(\log(k/\epsilon))\) 个，再加上把 tester 成功率放大到常数所需的对数因子，全部被 \(\widetilde O\) 吸收，最终
4.4 算法全貌与随机化¶
完整的 tester 可以这样理解：
随机选取桶的尺度 \(j\)（共 \(O(\log(k/\epsilon))\) 种，均匀随机选一种即有 \(\Omega(1/\log)\) 概率选中"堆积"的那个桶）；
以第 4.2 节的翻转测试为带噪声 oracle，运行 GGT 算法，区分 \(|A|\le k\) 与 \(|A|\ge k+d_j\)；
若 GGT 判定"变量数 \(\ge k+d_j\)"，拒绝（相关变量超过 \(k\) 个，\(f\) 不可能是 \(k\)-junta）；重复若干轮都未拒绝则接受。
正确性的两个方向：若 \(f\) 是 \(k\)-junta，相关变量总共至多 \(k\) 个，任何桶都不会触发"多"分支，GGT 恒回答"少"，算法以高概率接受。若 \(f\) 是 \(\epsilon\)-far，由第 4.1 节存在某个堆积桶 \(j^*\)；随机选桶以 \(\Omega(1/\log(k/\epsilon))\) 的概率选中它，选中时 GGT 以常数概率回答"多"，重复 \(O(\log)\) 轮即可把整体成功率提到常数——这些对数开销同样是 \(\widetilde O\) 的一部分。这就完成了 \(\widetilde O(\sqrt{k/\epsilon})\) 查询 tester 的构造。
5. 时间高效实现¶
到目前为止讨论的都是查询复杂度。Adversary bound 保证查询算法的存在性，但把它编译成电路时有个明显障碍：GGT 算法的工作寄存器要索引所有子集 \(S\subseteq[n]\)，即 Hilbert 空间
维数是 \(2^n\)。如果直接在这个空间上实现双反射（每次迭代要对整个对角 adversary 矩阵做相位翻转），每步的代价可能是 \(2^n\) 量级的——查询优势会被时间开销完全吃掉。
解法是再次利用第 3.3 节已经用过的对称性。\(M^n\) 承载对称群 \(S_n\) 的自然置换表示（置换下标就是置换基矢），而双反射算子与所有置换对易，因此按 Schur 引理，它们在 \(S_n\) 的不可约分解上是分块对角的：真正"非平凡"的部分只出现在少数几个低维同型分量 (isotypic components) 上，其余大块上反射就是恒等或简单的相位。所以实现反射只需要浅层的表示分解，把计算基矢变换到按不可约模块组织的基，而不是在 \(2^n\) 维空间上做完整变换。
具体地，可以用类似 Schur–Weyl transform 的逐比特 Clebsch–Gordan 更新：把子集 \(|S\rangle\) 看作逐个比特喂入的流，每读入一位就对当前的不可约模块标签做一次小的酉更新（每步只作用在 \(O(\log n)\) 到 \(O(\mathrm{poly}\log)\) 量级个辅助维度上，并需要操作一个 \(n\) 位的 query register）。\(n\) 位全部处理完后即完成一次所需反射，单次代价
把它乘上查询数：总门复杂度
约等于查询数乘以"处理一个 \(n\) 位查询寄存器"的最低线性成本。换言之，查询优势在至多近线性的每查询开销下转化成了时间优势——这正是本章反复强调的"同时追踪 setup/update/check 成本"的一个正面例子：这里的 setup 与 update 都足够便宜，没有把 \(\sqrt{k/\epsilon}\) 的查询优势偷偷换掉。
6. 下界与 exact group testing 的区别¶
下界一侧。目前已知的量子查询下界来自 image-size testing / collision testing 类问题的归约：固定 \(\epsilon\) 时，junta testing 需要
次量子查询。它与上界 \(\widetilde O(\sqrt k)=\widetilde O(k^{1/2})\) 之间仍有 \(k^{1/6}\) 的空隙，闭合这个 gap 是公开问题。需要提醒读者：本课的对抗界对 GGT 这个原语是紧的（\(\Theta(\sqrt{k/d})\) 上下界匹配），但 junta tester 只是 GGT 的一个应用——归约本身未必保持紧性，所以原语紧不代表整个 tester 的 \(\sqrt k\) 无法再改进。
与 exact group testing 的对比。经典的组合 group testing 以及 Ambainis–Montanaro（Zoo 167）研究的 exact combinatorial group testing 要求找出全部特殊项（承诺至多 \(k\) 个），其量子查询复杂度为 \(O(k\log k)\)。对比三种任务：
Exact CGT：输出整个集合 \(A\)，代价 \(O(k\log k)\)——信息量最大，对 \(k\) 近线性；
GGT：只判定 \(|A|\) 落在区间的哪一侧，代价 \(\Theta(\sqrt{k/d})\)——信息量最小（一个比特），换来了对 \(k\) 的平方根（gap 大时更好）；
Junta tester：内部调用的是后者，所以它从不输出完整的相关变量集，只输出接受/拒绝。这也是为什么它能比任何"必须先找齐变量"的策略更便宜：如果先把 \(k\) 个相关变量全部学出来再判定，仅学习一步就至少要 \(k\) 级别的查询，\(\sqrt k\) 无从谈起。
7. 小例子（完整计算）¶
取 \(n=4\)、
其中 \(x_3x_4\) 是 AND。\(f\) 只依赖变量 \(1,3,4\)，是 \(3\)-junta，相关集 \(J=\{1,3,4\}\)，变量 \(2\) 是无关变量。我们把第 1、2 节的量全部算一遍。
第一步：直接按定义算 influence。 \(x\) 在 \(16\) 个输入上均匀。
变量 \(1\)：翻 \(x_1\) 必改变 \(x_1\oplus(\cdots)\) 的值（\(\oplus\) 的另一项不受 \(x_1\) 影响），故 \(\operatorname{Inf}_1(f)=1\)。
变量 \(2\)：\(f\) 根本不含 \(x_2\)，\(\operatorname{Inf}_2(f)=0\)。
变量 \(3\)：\(f(x\oplus e_3)\neq f(x)\) 当且仅当 \(x_3x_4\) 变号，即 \(x_4=1\)（此时 \(x_3\) 从 \(0\) 到 \(1\) 或反之，AND 值翻转）。\(\Pr[x_4=1]=1/2\)，故 \(\operatorname{Inf}_3(f)=1/2\)。
变量 \(4\)：同理，需要 \(x_3=1\)，\(\operatorname{Inf}_4(f)=1/2\)。
第二步：算 Fourier 谱。 \(F(x)=(-1)^{x_1\oplus x_3x_4}=(-1)^{x_1}(-1)^{x_3x_4}\)。AND 的 \(\pm1\) 形式有标准展开（对四种 \((x_3,x_4)\) 逐点验证：\((0,0),(1,0),(0,1)\) 处得 \(+1\)，\((1,1)\) 处得 \(-1\)）
其中 \(\chi_S(x)=(-1)^{\sum_{i\in S}x_i}\)。两边乘 \(\chi_{\{1\}}=(-1)^{x_1}\)，用 \(\chi_S\chi_T=\chi_{S\triangle T}\)：
所以非零 Fourier 系数恰有四个：\(\widehat F(\{1\})=\widehat F(\{1,3\})=\widehat F(\{1,4\})=\tfrac12\)，\(\widehat F(\{1,3,4\})=-\tfrac12\)。
第三步：逐项验证本课的各个断言。
Parseval：\(4\times(\tfrac12)^2=1\)。✓
Lemma 2（支持只在 \(2^J\) 内）：四个非零频率 \(\{1\},\{1,3\},\{1,4\},\{1,3,4\}\) 都是 \(J=\{1,3,4\}\) 的子集，没有任何一个含变量 \(2\)。因此 Fourier sampling（第 2 节）无论运行多少次，测量结果 \(S\) 永远不含 2——无关变量在谱上完全隐形。✓
Lemma 1（influence 的 Fourier 表达）：\(\sum_{S\ni1}\widehat F(S)^2=4\times\tfrac14=1=\operatorname{Inf}_1\)；\(\sum_{S\ni3}\widehat F(S)^2=2\times\tfrac14=\tfrac12=\operatorname{Inf}_3\)；变量 \(4\) 同变量 \(3\)；变量 \(2\) 不在任何非零频率中，和为 \(0\)。与第一步完全吻合。✓
第四步：看 promise 的两个方向。 用 \(k=3\) 测，\(f\) 本身就是 \(3\)-junta，tester 应接受。用 \(k=2\) 测呢？"依赖 \(3\) 个变量"这句话本身并不足以满足 far promise——必须实际计算 \(f\) 到最近的 \(2\)-junta 的距离。候选的相关集只有三种选法（变量 2 无用）：
保留 \(\{3,4\}\)：任何只依赖 \((x_3,x_4)\) 的函数猜 \(x_1\oplus(x_3x_4)\)，对每个 \((x_3,x_4)\) 都要在不知道 \(x_1\) 的情况下猜一个含 \(x_1\) 的值，恰好一半概率猜错，距离 \(1/2\)。
保留 \(\{1,3\}\)：对每组 \((x_1,x_3)\)，真实输出随 \(x_4\) 变化的情况是 \(x_3=1\) 时 \(f=x_1\oplus x_4\)（\(x_4\) 均匀时输出均匀，怎么猜都错一半），\(x_3=0\) 时 \(f=x_1\)（可猜对）。最优距离 \(=\Pr[x_3=1]\cdot\tfrac12=\tfrac14\)（取 \(g=x_1\) 或 \(g=x_1\oplus x_3\) 都达到）。
保留 \(\{1,4\}\)：与上对称，距离 \(\tfrac14\)。
故 \(\operatorname{dist}(f,2\text{-juntas})=\tfrac14\)：\(f\) 是 \(\tfrac14\)-far from 2-juntas。结论：对 \(\epsilon\le\tfrac14\)，\(k=2\) 的 tester 应拒绝 \(f\)；对 \(\epsilon>\tfrac14\)，\(f\) 不满足 far promise，tester 输出任意。这个例子说明 far 参数 \(\epsilon\) 是问题输入的一部分，"相关变量有 \(k+1\) 个"与"远离所有 \(k\)-junta"是两回事——后者还要求这些变量合起来携带足够大的影响，而不仅仅是存在。
8. 小结¶
小结。
Junta testing 的 far promise 通过 Fourier 分析转化为定量资源：任意 \(k\) 个变量之外仍留有至少 \(\epsilon\) 的 influence / Fourier 质量（Lemma 3）。
Fourier sampling 能以常数次查询从平方谱分布中采样，Atıcı–Servedio 式 tester 靠逐个收集变量达到 \(O(k/\epsilon)\)；但 coupon collector 结构使它对低 influence 变量低效，对 \(k\) 的依赖是线性的。
Gapped group testing 只判定特殊项数目落在 \(|A|\le k\) 还是 \(|A|\ge k+d\)，量子查询复杂度是紧的 \(\Theta(\sqrt{k/d})\)（\(d\le k\)），由 dual adversary SDP 的可行解给出；置换对称性把构造压缩到少量 \(S_n\) 不可约模块，"irrelevant variables"设计容忍带噪声 oracle。当 \(d\ge\sqrt k\) 时与经典 \((k/d)^2\) 形成四次幂级别的差距。
把外部变量按 influence 尺度 \(\tau_j\asymp 2^j\epsilon/k\) 分桶后，far 情形保证某桶堆积 \(d_j\gtrsim k/2^j\) 个变量；GGT 查询数 \(\sqrt{k/d_j}\) 与单次检测成本 \(1/\sqrt{\tau_j}\) 因 \(d_j\tau_j\gtrsim\epsilon\) 而精确平衡，每桶成本同为 \(\sqrt{k/\epsilon}\)，总计 \(\widetilde O(\sqrt{k/\epsilon})\)。
对称群的浅层表示分解（逐比特 Clebsch–Gordan 更新）使每次反射只需 \(\widetilde O(n)\) 时间，总门复杂度 \(\widetilde O(n\sqrt{k/\epsilon})\)，查询优势在近线性开销下转化为时间优势。
下界 \(\Omega(k^{1/3})\)（固定 \(\epsilon\)）与上界之间仍有空隙；与 exact CGT 的 \(O(k\log k)\) 相比，tester 靠"只判定、不学习"绕过了收集全部变量的 \(k\) 级开销。
练习题¶
练习 1【Junta 与 far promise】（→ 0.2 节）
基础：写出 \(k\)-junta 与 \(\epsilon\)-far from \(k\)-juntas 的定义；判断 \(f(x)=x_1\oplus x_3\) 是几 junta，并说明 \(n\) 个变量的奇偶性函数为何不是任何 \(k<n\) 的 junta。
基础：设 \(n=2\)、\(f(x)=x_1\)、\(g(x)=x_2\)，用距离的定义计算 \(\operatorname{dist}(f,g)\)。
进阶：设 \(f\) 是 \(k\)-junta，\(g\) 与 \(f\) 只在一个输入上取值不同（于是 \(g\) 一般不是 \(k\)-junta，也不满足 \(\epsilon\)-far）。论证：任何想可靠区分 \(f\) 与 \(g\) 的查询算法都必须先定位那个唯一不同的输入，其代价与无序搜索同阶；由此解释 promise 空隙为何必要。
提示：定位唯一不同的输入正是"大海捞针"式的搜索问题。
练习 2【Fourier 展开与 Parseval 恒等式】（→ 1.2 节）
基础：对 \(n=2\) 的 AND（\(f(x)=x_1x_2\)），写出 \(F=(-1)^f\) 的全部四个 Fourier 系数，并验证 Parseval 恒等式。
进阶：证明奇偶性基的正交性：对 \(S\neq T\)，取 \(i\in S\triangle T\)，沿第 \(i\) 位把 \(x\) 与 \(x\oplus e_i\) 配对，证明 \(\mathbb E_x[\chi_S(x)\chi_T(x)]=0\)。
提示：配对的两项中 \(\chi_S\chi_T\) 恰好相差一个负号，成对相消。
练习 3【Influence 的 Fourier 表达】（→ 1.3 节）
基础：按定义 \(\operatorname{Inf}_i(f)=\Pr_x[f(x)\neq f(x\oplus e_i)]\) 计算第 7 节例子 \(f=x_1\oplus(x_3x_4)\) 的四个单变量 influence。
进阶：用第 7 节算出的 Fourier 谱经 Lemma 1 重新计算这四个 influence，验证与第 1 题一致；再计算总 influence \(\sum_i\operatorname{Inf}_i(f)\)，并验证它等于 \(\sum_S|S|\widehat F(S)^2\)。
提示：四个非零频率 \(\{1\},\{1,3\},\{1,4\},\{1,3,4\}\) 的大小分别为 \(1,2,2,3\)。
练习 4【Junta 的 Fourier 支持与外部质量】（→ 1.4 节）
基础：分别陈述 Lemma 2 与 Lemma 3，并说明二者各自支撑 tester 正确性的哪一个方向（junta 情形接受 / far 情形拒绝）。
进阶：证明 Lemma 2：\(J\)-junta 的 Fourier 支持只在 \(2^J\) 上。进一步说明：\(J\)-junta 的非零 Fourier 系数至多 \(2^{|J|}\) 个，因此 Fourier sampling 可能的测量结果至多 \(2^k\) 种。
进阶：补全 Lemma 3 的证明细节：说明为什么截断函数 \(h\) 取符号后得到的 \(g\) 是 \(k\)-junta，以及为什么 \(\mathbf 1[f\neq g]\le(F-h)^2\) 逐点成立。
提示：第 2 题取 \(i\in S\setminus J\) 沿第 \(i\) 位配对求和；第 3 题注意 \(f(x)\neq g(x)\) 时 \(F(x)\) 与 \(h(x)\) 异号。
练习 5【Fourier sampling 与收集瓶颈】（→ 第 2 节）
基础：写出 Fourier sampling 的三步线路；对第 7 节的例子 \(f=x_1\oplus(x_3x_4)\)，列出全部可能的测量结果及各自概率，并指出哪个变量永远不会出现。
进阶：从第三步的振幅表达式出发，证明测得子集 \(S\) 的概率恰为 \(\widehat F(S)^2\)；据此说明 far 情形下每次采样至少以 \(\epsilon\) 的概率命中当前候选集 \(J\) 之外的频率。
进阶：解释 Atıcı–Servedio 式 tester 的总查询数为何是 \(O(k/\epsilon)\)，coupon collector 结构又为何使它难以突破对 \(k\) 的线性依赖。
提示：第三步的振幅就是 \(\widehat F(S_y)\)；命中 \(J\) 外频率的概率恰是外部 Fourier 质量（Lemma 3）。
练习 6【GGT 原语与对抗界构造】（→ 3.1 节）
基础：写出 group-testing oracle 的语义 \(g_A(S)=\mathbf 1[S\cap A\neq\varnothing]\) 与 GGT 的两种承诺情形，陈述 \(d\le k\) 时的量子查询复杂度，并说出它与 exact CGT（要求输出整个集合 \(A\)）的目标差异。
进阶：解释 dual adversary SDP 的可行解为何本身就是查询算法的存在性证明，置换对称性如何把指数多的 adversary 向量压缩到少量 \(S_n\) 不可约模块，以及 "irrelevant variables" 保留条款为何能容忍带噪声的 oracle。
进阶：说明为什么在 \(2^n\) 维子集空间上直接实现双反射会吃掉查询优势，而逐比特 Clebsch–Gordan 更新能把单次反射的代价降到 \(\widetilde O(n)\)、总门复杂度降到 \(\widetilde O(n\sqrt{k/\epsilon})\)。
提示：\(g_A(S)\) 的值只依赖 \(|A|\) 与 \(|S\cap A|\)，可要求 adversary 向量继承 \(S_n\) 的置换对称性。
练习 7【Influence 分桶归约】（→ 4.1 节）
基础：取 \(\epsilon=0.01\)、\(k=1000\)：写出桶尺度 \(\tau_j\asymp 2^j\epsilon/k\) 的取值范围与桶数，并对 \(j=0,4,8\) 列出 \(\tau_j\) 与堆积规模 \(d_j\gtrsim k/2^j\)，验证 \(d_j\tau_j\asymp\epsilon\)。
进阶：解释翻转测试如何把"子集 \(S\) 含有第 \(j\) 桶变量"实现为成功率 \(\Omega(\tau_j)\) 的子过程，振幅放大为何使一次 group-test 查询只需 \(O(1/\sqrt{\tau_j})\) 次 \(f\) 查询，以及噪声从何而来。
进阶：补全第 4.1 节的 pigeonhole 论证：设 \(\sum_j m_j\tau_j\ge\epsilon\)、桶数 \(O(\log(k/\epsilon))\)，证明存在 \(j\) 使 \(m_j\gtrsim k/2^j\)；再验证取 \(d_j\asymp k/2^j\)、\(\tau_j\asymp 2^j\epsilon/k\) 时 \(\sqrt{k/d_j}\cdot 1/\sqrt{\tau_j}\) 与 \(j\) 无关。
提示：平均原理给出某个桶 \(m_j\tau_j\gtrsim\epsilon/\log(k/\epsilon)\)，再代入 \(\epsilon/\tau_j=k/2^j\)。
练习 8【复杂度对比与已知下界】（→ 第 6 节）
基础：取 \(d=\sqrt k\)，分别写出经典随机算法与量子算法的 GGT 查询数作为 \(k/d\) 的幂，并说明为什么称之为四次幂差距；再固定 \(\epsilon\)，写出 junta testing 已知的量子下界与上界，并指出二者之间的空隙。
进阶：补全第 3.2 节的采样分析：设每次查询以概率 \(p\) 独立放入每个下标，写出命中概率 \(1-(1-p)^a\) 在 \(pa\) 小时的近似，并说明 \(p\approx1/k\) 是区分 \(a=k\) 与 \(a=k+d\) 的最优选择，最终样本数为 \((k/d)^2\) 量级。
进阶：比较 exact combinatorial group testing 与 GGT 的输出信息量与复杂度：为什么"找出全部特殊项"不可能有 \(\sqrt{k/d}\) 级别的算法？由此解释 junta tester 为什么必须走"判定"而非"学习"路线。
提示：第 2 题注意单次查询是均值 \(\approx pa\) 的 Bernoulli 试验，区分两种情形靠差 \(\Delta\approx pd\)；第 3 题考虑输出本身包含的比特数。
参考文献与 Zoo 覆盖¶
Zoo 编号 266：Ambainis、Belovs、Regev 与 de Wolf, Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.
Zoo 编号 267：Atıcı 与 Servedio, Quantum Algorithms for Learning and Testing Juntas.
Zoo 编号 268：Aleksandrs Belovs, Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound.
Zoo 编号 167：Ambainis--Montanaro exact combinatorial group testing。