# Junta 测试与 Gapped Group Testing：从变量影响到对抗界 一个 $k$-junta 是只依赖 $n$ 个输入变量中至多 $k$ 个的布尔函数。本课要解决的**性质测试 (property testing)** 问题是：给定对函数 $f$ 的黑盒查询能力，不要求找出函数的真值表，而只要求区分两种情况——$f$ 确实是 $k$-junta，或者 $f$ 与任何 $k$-junta 都至少在 $\epsilon$ 比例的输入上取值不同。 量子算法解决这个问题的路线可以概括为三步： 1. 把"$f$ 远离所有 $k$-junta"翻译成"任意 $k$ 个变量之外仍留有可观的 influence / Fourier 质量"； 2. 把"有多少个变量具有某一档 influence"归约为一个新原语——**gapped group testing (GGT)**； 3. 用**对抗界 (adversary bound)** 的半定规划为 GGT 直接构造查询算法，并用对称群表示论把它实现得时间高效。 最终的查询复杂度是 $$ \widetilde O\!\left(\sqrt{k/\epsilon}\right), $$ 其中 $\widetilde O$ 隐藏 $\log$ 因子。相比之下，早期的量子 tester（Zoo 267，Atıcı–Servedio）约需 $O(k/\epsilon)$ 次查询——本课的算法把对 $k$ 的依赖从线性压到了平方根。下面我们从问题的来历讲起。 :::{admonition} 本课知识点 :class: tip 1. **[Junta 与 far promise](#junta-far-promise)**——能写出 $k$-junta、normalized Hamming 距离与 $\epsilon$-far 的定义，并解释 promise 空隙对测试问题为何必要。 2. **[Fourier 展开与 Parseval 恒等式](#fourier-parseval)**——能把 $F(x)=(-1)^{f(x)}$ 展开到正交归一的奇偶性基上，计算 Fourier 系数并用 Parseval 恒等式验证归一。 3. **[Influence 的 Fourier 表达](#influence-fourier-formula)**——能用"翻转坐标"与"Fourier 质量"两种方法计算单变量 influence，并补全 Lemma 1 的四步推导。 4. **[Junta 的 Fourier 支持与外部质量](#junta-support-external-mass)**——能证明 $J$-junta 的非零频率都含于 $2^J$（Lemma 2），并由 $\epsilon$-far 推出任意 $k$ 个变量之外仍留至少 $\epsilon$ 的 influence（Lemma 3）。 5. **[Fourier sampling 与收集瓶颈](#fourier-sampling)**——能推导 Fourier sampling 测得 $S$ 的概率为 $\widehat F(S)^2$，并解释 Atıcı–Servedio 式 tester 的 $O(k/\epsilon)$ 复杂度及其 coupon collector 瓶颈。 6. **[GGT 原语与对抗界构造](#ggt-primitive-adversary)**——能写出 GGT 的承诺与复杂度 $\Theta(\sqrt{k/d})$，并解释对抗界可行解、置换对称性压缩与 irrelevant variables 设计如何共同给出查询与时间都高效的算法。 7. **[Influence 分桶归约](#influence-bucketing-reduction)**——能用分桶与鸽巢论证找出"堆积桶"，把桶内变量检测实现为带噪声 group-test 查询，并把每桶成本平衡到 $\sqrt{k/\epsilon}$。 8. **[复杂度对比与已知下界](#complexity-comparison-junta-group-testing)**——能推导经典随机基准 $(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 **定义（距离）**. 两个布尔函数 $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 权重表达，但我们只需要上面的概率形式。 (fourier-parseval)= ### 1.2 布尔函数的 Fourier 展开 把布尔函数的取值换成 $\pm 1$ 更方便做代数。定义相位函数 $$F(x)=(-1)^{f(x)}\in\{+1,-1\},$$ 于是 $f(x)\neq f(x')$ 等价于 $F(x)F(x')=-1$。对每个子集 $S\subseteq[n]$ 定义**奇偶性基函数 (parity / character)** $$\chi_S(x)=(-1)^{\sum_{i\in S}x_i},$$ 即 "$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$ 都有唯一展开 $$F(x)=\sum_{S\subseteq[n]}\widehat F(S)\,\chi_S(x),\qquad \widehat F(S)=\mathbb E_x\bigl[F(x)\chi_S(x)\bigr]=\frac{1}{2^n}\sum_x F(x)\chi_S(x).$$ 系数 $\widehat F(S)$ 称为 $F$ 的 **Fourier 系数**。由正交归一性立刻得到 **Parseval 恒等式**： $$\sum_{S}\widehat F(S)^2=\mathbb E_x[F(x)^2]=1,$$ 最后一步因为 $F$ 取值 $\pm 1$。这个恒等式是 Fourier sampling 的根基：平方系数构成一个概率分布。 (influence-fourier-formula)= ### 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$。因此 $$\mathbf 1[f(x)\neq f(x\oplus e_i)]=\frac{\bigl(F(x)-F(x\oplus e_i)\bigr)^2}{4}.$$ 第二步，对 $x$ 取期望。展开平方，注意 $F^2=1$，以及"把 $x$ 换成 $x\oplus e_i$ 不改变均匀分布"（所以 $\mathbb E_x[F(x\oplus e_i)^2]=1$）： $$\operatorname{Inf}_i(f)=\mathbb E_x\left[\frac{F(x)^2-2F(x)F(x\oplus e_i)+F(x\oplus e_i)^2}{4}\right]=\frac{2-2\,\mathbb E_x[F(x)F(x\oplus e_i)]}{4}=\frac{1-\mathbb E_x[F(x)F(x\oplus e_i)]}{2}.$$ 第三步，计算关联项。代入 Fourier 展开： $$\mathbb E_x[F(x)F(x\oplus e_i)]=\sum_{S,T}\widehat F(S)\widehat F(T)\,\mathbb E_x\bigl[\chi_S(x)\chi_T(x\oplus e_i)\bigr].$$ 由 $\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}$，双重求和塌缩为 $$\sum_{S}\widehat F(S)^2\,\chi_S(e_i)=\sum_{S}\widehat F(S)^2(-1)^{[i\in S]}.$$ 第四步，合并。用 Parseval， $$\operatorname{Inf}_i(f)=\frac{1}{2}\left(\sum_{S}\widehat F(S)^2-\sum_{S}\widehat F(S)^2(-1)^{[i\in S]}\right)=\sum_{S\ni i}\widehat F(S)^2,$$ 因为 $i\notin S$ 的项贡献 $(1-1)/2=0$，$i\in S$ 的项贡献 $(1+1)/2=1$。Q.E.D. 这个引理把一个组合量（翻转坐标检测输出的概率）和一个谱量（Fourier 系数平方和）等同起来，是整篇教程反复使用的翻译器。 (junta-support-external-mass)= ### 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$ 位的取值"配对： $$\widehat F(S)=\frac{1}{2^n}\sum_x F(x)\chi_S(x)=\frac{1}{2^n}\sum_{x:\,x_i=0}\Bigl[F(x)\chi_S(x)+F(x\oplus e_i)\chi_S(x\oplus e_i)\Bigr].$$ 由于 $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$， $$\sum_{S\not\subseteq J}\widehat F(S)^2\ge\epsilon,\qquad\text{从而}\qquad \sum_{i\notin J}\operatorname{Inf}_i(f)\ge\epsilon.$$ **证明**。证明逆否命题的前半：若存在 $|J|\le k$ 使外部 Fourier 质量 $<\epsilon$，则 $f$ 不是 $\epsilon$-far。构造一个只依赖 $J$ 的近似函数：先把 $F$ 的 Fourier 展开截断到 $J$ 内， $$h(x)=\sum_{S\subseteq J}\widehat F(S)\,\chi_S(x),$$ 再取符号 $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$ 逐点成立。于是 $$\operatorname{dist}(f,g)\le \mathbb E_x[(F-h)^2]=\sum_{S\not\subseteq J}\widehat F(S)^2<\epsilon,$$ 中间的等号就是 Parseval：$F-h$ 的展开恰好由被截掉的项组成。这与 "$f$ 是 $\epsilon$-far" 矛盾，第一条不等式得证。 第二条由 Lemma 1 推出： $$\sum_{i\notin J}\operatorname{Inf}_i(f)=\sum_{i\notin J}\sum_{S\ni i}\widehat F(S)^2\ge \sum_{S\not\subseteq J}\widehat F(S)^2\ge\epsilon,$$ 其中 $\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。 (fourier-sampling)= ## 2. Fourier sampling 怎样暴露变量 Fourier sampling 是量子算法探测布尔函数谱结构的标准原语，其线路与 Deutsch–Jozsa 算法（ch03）几乎相同，区别只在输入态的制备。 **线路**。从 $|0^n\rangle$ 出发： 1. 作用 $H^{\otimes n}$，得到均匀叠加 $\frac{1}{2^{n/2}}\sum_x |x\rangle$； 2. 作用相位预言机 $O_f:|x\rangle\mapsto(-1)^{f(x)}|x\rangle$（由标准比特预言机 $|x\rangle|b\rangle\mapsto|x\rangle|b\oplus f(x)\rangle$ 把目标位置于 $|-\rangle$ 即得，一次查询），得到 $$\frac{1}{2^{n/2}}\sum_x F(x)\,|x\rangle;$$ 3. 再作用 $H^{\otimes n}$，在计算基下测量。 第三步之后，结果 $y\in\{0,1\}^n$ 的振幅为（用 $H|x_i\rangle$ 的矩阵元 $(-1)^{x_i y_i}/\sqrt2$ 逐项相乘再求和） $$\langle y|H^{\otimes n}\left(\frac{1}{2^{n/2}}\sum_x F(x)|x\rangle\right)=\frac{1}{2^n}\sum_x F(x)(-1)^{x\cdot y}=\widehat F(S_y),$$ 其中 $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 原语 (ggt-primitive-adversary)= ### 3.1 从 group testing 到 gapped 版本 经典的 **group testing** 模型：有一个未知集合 $A\subseteq[n]$（"特殊项"，比如人群中的感染者），算法可以查询任意子集 $S\subseteq[n]$，oracle 回答 $$g_A(S)=\mathbf 1[S\cap A\neq\varnothing],$$ 即"这一组里有没有特殊项"。一次查询检测一整个组，这是它优于逐项检查的原因。 本课需要的是它的判定版本。**Gapped group testing (GGT)** 承诺 $|A|$ 落在两个不相交的区间之一： $$|A|\le k\qquad\text{或}\qquad |A|\ge k+d,$$ 任务只是区分这两种情形，其中 $d\ge 1$ 是 **gap**（无需找出 $A$ 中的任何元素）。 **主结果**（Zoo 266）：在 $d\le k$ 时，GGT 的量子查询复杂度为 $$\Theta\!\left(\sqrt{k/d}\right).$$ 上界由下文的 adversary 构造给出，下界也来自 adversary 方法，两者匹配到常数。 ### 3.2 为什么这个复杂度值得关注 先看经典基准。经典随机算法的自然策略是：每次独立地以概率 $p$ 把每个下标放入 $S$，查询 $g_A(S)$，重复多次后比较命中频率。记 $|A|=a$。当 $pa$ 较小时， $$\Pr[g_A(S)=1]=1-(1-p)^a\approx pa,$$ 即单次查询的命中概率约为 $pa$。两种情形（$a=k$ 与 $a=k+d$）的命中率差 $\Delta\approx pd$；而每次查询是方差 $\approx pa$ 的 Bernoulli 变量，要把两个均值分开，由中心极限定理需要的样本数约为 $$\frac{\text{方差}}{\Delta^2}\approx\frac{pa}{(pd)^2}\approx\frac{k}{p\,d^2}.$$ 最后调 $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 的两个关键观察把它压到多项式尺寸： 1. **置换对称性**。oracle $g_A(S)$ 的值只依赖于 $|A|$ 与 $|S\cap A|$；交换 $[n]$ 的元素不改变问题。因此可以要求 adversary 向量继承对称群 $S_n$ 的置换对称性，把指数大的子集空间分解为少量 $S_n$ 的**不可约表示 (irreducible representations)** 模块，只需在每个模块上给出可行向量。这是"对称性压缩"的标准操作，与 collision 问题的下界证明（本章 collision 一课）同源。 2. **"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**。 (influence-bucketing-reduction)= ### 4.1 分桶与 pigeonhole 设 $f$ 是 $\epsilon$-far。由 Lemma 3，任意候选集 $J$（$|J|\le k$）之外的变量携带总 influence 至少 $\epsilon$。把 $J$ 之外的变量按 influence 大小分桶：第 $j$ 桶装 influence 落在 $$\tau_j\asymp\frac{2^j\epsilon}{k}$$ 附近的变量（即区间 $[\tau_j/2,\tau_j]$ 之类，常数因子不影响渐近）。值得考虑的尺度范围是从 $\epsilon/k$（低于它的单桶贡献可忽略）到 $1$，所以桶数为 $$j=0,1,\dots,O\!\left(\log\frac{k}{\epsilon}\right).$$ **鸽巢论证**：每个桶对总外部 influence 的贡献约为"桶内变量数 $\times$ 该桶尺度"。设第 $j$ 桶有 $m_j$ 个变量，则 $\sum_j m_j\tau_j\ge\epsilon$（总质量），而桶数只有 $O(\log(k/\epsilon))$ 个。由平均原理，至少存在一个桶 $j$ 满足 $$m_j\tau_j\gtrsim\frac{\epsilon}{\log(k/\epsilon)}\quad\Longrightarrow\quad m_j\gtrsim\frac{\epsilon/\tau_j}{\log(k/\epsilon)}=\frac{k/2^j}{\log(k/\epsilon)},$$ 其中最后一步代入 $\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$ 的查询实现 $$g_j(S)\approx\mathbf 1[S\text{ 含有某个 influence 约 }\tau_j\text{ 的变量}].$$ 实现方法是**翻转测试**：均匀随机取 $x$，再随机重洗 $S$ 内的坐标得到 $x'$，比较 $f(x)$ 与 $f(x')$。若 $S$ 含有一个 influence $\ge\tau_j$ 的变量 $i$，那么仅翻转 $i$ 就有 $\ge\tau_j$ 的概率改变输出；随机重洗 $S$ 至少以相当的比例"翻到 $i$ 这一位"，因此 $$\Pr_{x,x'}[f(x)\neq f(x')]=\Omega(\tau_j).$$ 换句话说，"检测到一次输出变化"这个事件的**成功概率** $p$ 是 $\Omega(\tau_j)$ 量级的。由振幅放大（ch03：成功概率 $p$ 的子过程可用 $O(1/\sqrt p)$ 次调用把成功振幅提升到常数），用 $$O\!\left(1/\sqrt{\tau_j}\right)$$ 次 $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\!\left(\sqrt{k/d_j}\right)\ \text{次 group-test 查询},$$ 每次实现成本 $O(1/\sqrt{\tau_j})$ 次 $f$ 查询，故该桶总成本 $$O\!\left(\sqrt{\frac{k}{d_j}}\cdot\frac{1}{\sqrt{\tau_j}}\right)=O\!\left(\sqrt{\frac{k}{d_j\tau_j}}\right).$$ 代入第 4.1 节的乘积守恒 $d_j\tau_j\gtrsim\epsilon$： $$\sqrt{\frac{k}{d_j\tau_j}}\lesssim\sqrt{\frac{k}{\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$ 吸收，最终 $$\widetilde O\!\left(\sqrt{k/\epsilon}\right)\ \text{次 }f\text{ 查询}.$$ ### 4.4 算法全貌与随机化 完整的 tester 可以这样理解： 1. 随机选取桶的尺度 $j$（共 $O(\log(k/\epsilon))$ 种，均匀随机选一种即有 $\Omega(1/\log)$ 概率选中"堆积"的那个桶）； 2. 以第 4.2 节的翻转测试为带噪声 oracle，运行 GGT 算法，区分 $|A|\le k$ 与 $|A|\ge k+d_j$； 3. 若 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 空间 $$M^n=\operatorname{span}\{|S\rangle:S\subseteq[n]\},$$ 维数是 $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$ 位全部处理完后即完成一次所需反射，单次代价 $$\widetilde O(n).$$ 把它乘上查询数：总门复杂度 $$\widetilde O\!\left(n\sqrt{k/\epsilon}\right),$$ 约等于查询数乘以"处理一个 $n$ 位查询寄存器"的最低线性成本。换言之，**查询优势在至多近线性的每查询开销下转化成了时间优势**——这正是本章反复强调的"同时追踪 setup/update/check 成本"的一个正面例子：这里的 setup 与 update 都足够便宜，没有把 $\sqrt{k/\epsilon}$ 的查询优势偷偷换掉。 (complexity-comparison-junta-group-testing)= ## 6. 下界与 exact group testing 的区别 **下界一侧**。目前已知的量子查询下界来自 image-size testing / collision testing 类问题的归约：固定 $\epsilon$ 时，junta testing 需要 $$\Omega\!\left(k^{1/3}\right)$$ 次量子查询。它与上界 $\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$、 $$f(x_1,x_2,x_3,x_4)=x_1\oplus(x_3x_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$） $$(-1)^{x_3x_4}=\frac12+\frac12\chi_{\{3\}}(x)+\frac12\chi_{\{4\}}(x)-\frac12\chi_{\{3,4\}}(x),$$ 其中 $\chi_S(x)=(-1)^{\sum_{i\in S}x_i}$。两边乘 $\chi_{\{1\}}=(-1)^{x_1}$，用 $\chi_S\chi_T=\chi_{S\triangle T}$： $$F(x)=\frac12\chi_{\{1\}}+\frac12\chi_{\{1,3\}}+\frac12\chi_{\{1,4\}}-\frac12\chi_{\{1,3,4\}}.$$ 所以非零 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 节](#junta-far-promise)） 1. 基础：写出 $k$-junta 与 $\epsilon$-far from $k$-juntas 的定义；判断 $f(x)=x_1\oplus x_3$ 是几 junta，并说明 $n$ 个变量的奇偶性函数为何不是任何 $k 提示：定位唯一不同的输入正是"大海捞针"式的搜索问题。 **练习 2【Fourier 展开与 Parseval 恒等式】**（→ [1.2 节](#fourier-parseval)） 1. 基础：对 $n=2$ 的 AND（$f(x)=x_1x_2$），写出 $F=(-1)^f$ 的全部四个 Fourier 系数，并验证 Parseval 恒等式。 2. 进阶：证明奇偶性基的正交性：对 $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 节](#influence-fourier-formula)） 1. 基础：按定义 $\operatorname{Inf}_i(f)=\Pr_x[f(x)\neq f(x\oplus e_i)]$ 计算第 7 节例子 $f=x_1\oplus(x_3x_4)$ 的四个单变量 influence。 2. 进阶：用第 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 节](#junta-support-external-mass)） 1. 基础：分别陈述 Lemma 2 与 Lemma 3，并说明二者各自支撑 tester 正确性的哪一个方向（junta 情形接受 / far 情形拒绝）。 2. 进阶：证明 Lemma 2：$J$-junta 的 Fourier 支持只在 $2^J$ 上。进一步说明：$J$-junta 的非零 Fourier 系数至多 $2^{|J|}$ 个，因此 Fourier sampling 可能的测量结果至多 $2^k$ 种。 3. 进阶：补全 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)） 1. 基础：写出 Fourier sampling 的三步线路；对第 7 节的例子 $f=x_1\oplus(x_3x_4)$，列出全部可能的测量结果及各自概率，并指出哪个变量永远不会出现。 2. 进阶：从第三步的振幅表达式出发，证明测得子集 $S$ 的概率恰为 $\widehat F(S)^2$；据此说明 far 情形下每次采样至少以 $\epsilon$ 的概率命中当前候选集 $J$ 之外的频率。 3. 进阶：解释 Atıcı–Servedio 式 tester 的总查询数为何是 $O(k/\epsilon)$，coupon collector 结构又为何使它难以突破对 $k$ 的线性依赖。 > 提示：第三步的振幅就是 $\widehat F(S_y)$；命中 $J$ 外频率的概率恰是外部 Fourier 质量（Lemma 3）。 **练习 6【GGT 原语与对抗界构造】**（→ [3.1 节](#ggt-primitive-adversary)） 1. 基础：写出 group-testing oracle 的语义 $g_A(S)=\mathbf 1[S\cap A\neq\varnothing]$ 与 GGT 的两种承诺情形，陈述 $d\le k$ 时的量子查询复杂度，并说出它与 exact CGT（要求输出整个集合 $A$）的目标差异。 2. 进阶：解释 dual adversary SDP 的可行解为何本身就是查询算法的存在性证明，置换对称性如何把指数多的 adversary 向量压缩到少量 $S_n$ 不可约模块，以及 "irrelevant variables" 保留条款为何能容忍带噪声的 oracle。 3. 进阶：说明为什么在 $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 节](#influence-bucketing-reduction)） 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$。 2. 进阶：解释翻转测试如何把"子集 $S$ 含有第 $j$ 桶变量"实现为成功率 $\Omega(\tau_j)$ 的子过程，振幅放大为何使一次 group-test 查询只需 $O(1/\sqrt{\tau_j})$ 次 $f$ 查询，以及噪声从何而来。 3. 进阶：补全第 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 节](#complexity-comparison-junta-group-testing)） 1. 基础：取 $d=\sqrt k$，分别写出经典随机算法与量子算法的 GGT 查询数作为 $k/d$ 的幂，并说明为什么称之为四次幂差距；再固定 $\epsilon$，写出 junta testing 已知的量子下界与上界，并指出二者之间的空隙。 2. 进阶：补全第 3.2 节的采样分析：设每次查询以概率 $p$ 独立放入每个下标，写出命中概率 $1-(1-p)^a$ 在 $pa$ 小时的近似，并说明 $p\approx1/k$ 是区分 $a=k$ 与 $a=k+d$ 的最优选择，最终样本数为 $(k/d)^2$ 量级。 3. 进阶：比较 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](https://arxiv.org/abs/1507.03126). - Zoo 编号 267：Atıcı 与 Servedio, [Quantum Algorithms for Learning and Testing Juntas](https://arxiv.org/abs/0707.3479). - Zoo 编号 268：Aleksandrs Belovs, [Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound](https://arxiv.org/abs/1311.6777). - Zoo 编号 167：Ambainis--Montanaro exact combinatorial group testing。