Junta 测试与 Gapped Group Testing

一个 $k$-junta 是只依赖 $n$ 个输入变量中至多 $k$ 个的布尔函数。本词条要解决的性质测试 (property testing) 问题是：给定对函数 $f$ 的黑盒查询能力，不要求找出函数的真值表，而只要求区分两种情况——$f$ 确实是 $k$-junta，或者 $f$ 与任何 $k$-junta 都至少在 $ϵ$ 比例的输入上取值不同。

量子算法解决这个问题的路线可以概括为三步：

1. 把”$f$ 远离所有 $k$-junta”翻译成”任意 $k$ 个变量之外仍留有可观的 influence / Fourier 质量”；
2. 把”有多少个变量具有某一档 influence”归约为一个新原语——gapped group testing (GGT)；
3. 用对抗界 (adversary bound) 的半定规划为 GGT 直接构造查询算法，并用对称群表示论把它实现得时间高效。

最终的查询复杂度是

$$\tilde{O}\left(\sqrt{k/ϵ}\right),$$

其中 $\tilde{O}$ 隐藏 $\log$ 因子。相比之下，早期的量子 tester（Zoo 267，Atıcı–Servedio）约需 $O(k/ϵ)$ 次查询——本词条的算法把对 $k$ 的依赖从线性压到了平方根。下面我们从问题的来历讲起。

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 的查询复杂度压到 $\tilde{O}(\sqrt{k/ϵ})$。Ambainis–Montanaro（Zoo 167）则研究了不带 gap、要求找出全部特殊项的 exact 版本，我们在第 6 节对比。

0.2 性质测试的约定：距离与 far promise

测试问题之所以”比学习容易”，是因为它放松了目标：不输出相关变量集合，只输出一个比特的判定。为了使判定良定义，必须规定两个输出对应的函数类之间有空隙——这就是 promise。

定义（距离）. 两个布尔函数 $f,g$ 的 normalized Hamming 距离为 $\mathrm{dist}(f,g)={\mathrm{Pr}}_x[f(x)\ne g(x)]=\frac{1}{2^n}|\{x:f(x)\ne g(x)\}|,$ 即 $x$ 均匀随机时两者取值不同的概率。

定义（$ϵ$-far）. 若对每一个 $k$-junta $g$ 都有 $\mathrm{dist}(f,g)\ge ϵ$，则称 $f$ 是 $ϵ$-far from $k$-juntas，简称”远离所有 $k$-junta”。

定义（junta tester）. 一个 $k$-junta tester 输入参数 $k$ 与 $ϵ$，通过查询黑盒 $f$（给 $x$ 得 $f(x)$）满足：

• 若 $f$ 是 $k$-junta，以至少 $2/3$ 的概率输出”接受”；
• 若 $f$ 是 $ϵ$-far from $k$-juntas，以至少 $2/3$ 的概率输出”拒绝”。

对既不满足前者也不满足后者的 $f$，输出任意。常数 $2/3$ 可用标准重复放大提升到 $1-\delta$，代价是乘 $O(\log \frac{1}{\delta })$。

注意这个 promise 是必要的：若 $f$ 与某个 $k$-junta 只在极少数输入上不同，任何查询算法都很难发现这些输入，区分两者本质上是大海捞针，测试也就失去了意义。

0.3 经典算法的瓶颈

经典 tester 的基本手段是随机取 $x$、翻转某个坐标看输出是否改变，以此”指控”某个变量是相关的。粗略地说，发现一个新相关变量的代价反比于该变量的 influence（第 1 节定义）；当相关变量很多、各自 influence 又可能低到 $ϵ/k$ 量级时，逐个发现它们的开销随 $k$ 线性（甚至更差）增长。量子的 Fourier sampling（第 2 节）能加速”发现”这一步，但同样受困于低 influence 变量的”收集问题”。真正的突破在于换一个问法：不逐个收集变量，而是批量地问”具有某档 influence 的变量，数目是至多 $k$ 个还是至少 $k+d$ 个”——这正是 gapped group testing，其量子查询复杂度 $\Theta (\sqrt{k/d})$ 由对抗界给出，且在大 gap 时比 Grover 式的平方加速还要好。

0.4 前置知识

本词条假设读者熟悉：量子态、测量与 Hadamard 变换（）；相位反冲与相位预言机（的 Deutsch–Jozsa）；Grover 迭代与振幅放大（），特别是”成功概率 $p$ 的子过程可用 $O(1/\sqrt{p})$ 次调用放大”这一结论。不需要 Fourier 分析的先修——下一节会把它从零建立。

1. 距离、相关变量与 influence

本节建立三个工具：单变量 influence、布尔函数的 Fourier 展开、以及”far promise $\Rightarrow$ 外部 influence 质量”这一关键引理。

1.1 单变量 influence

定义（influence）. 变量 $i\in [n]$ 对 $f$ 的 influence 是

${\mathrm{Inf}}_i(f)={\mathrm{Pr}}_x[f(x)\ne f(x\oplus e_i)],$

其中 $x$ 均匀随机，$e_i$ 是第 $i$ 位为 $1$ 的单位向量，$x\oplus e_i$ 表示把 $x$ 的第 $i$ 位取反。

直觉：${\mathrm{Inf}}_i(f)$ 度量”第 $i$ 个变量有多重要”——随机翻它一下，输出跟着变的概率越大，这个变量越要紧。两个极端：若 $i$ 是无关变量，$f(x\oplus e_i)=f(x)$ 恒成立，${\mathrm{Inf}}_i(f)=0$；若 $f$ 就是第 $i$ 位本身（dictator 函数），则输出必跟着变，${\mathrm{Inf}}_i(f)=1$。

对变量集合 $S\subseteq [n]$，也可以定义联合 influence：随机重洗 $S$ 内的坐标（$S$ 外保持不变），输出发生变化的概率。第 4 节实现 group-test 查询时用的正是这种”翻转一整个子集”的操作；它也可以用 Fourier 权重表达，但我们只需要上面的概率形式。

1.2 布尔函数的 Fourier 展开

把布尔函数的取值换成 $\pm 1$ 更方便做代数。定义相位函数

$F(x)=(-1{)}^{f(x)}\in \{+1,-1\},$

于是 $f(x)\ne f(x^{\prime })$ 等价于 $F(x)F(x^{\prime })=-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$ 个函数在均匀分布的内积 $⟨G,H⟩={\mathbb{E}}_x[G(x)H(x)]$ 下正交归一：对 $S\ne T$，存在某一位 $i$ 属于 $S△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]}\hat{F}(S){\chi }_S(x),\hat{F}(S)={\mathbb{E}}_x[F(x){\chi }_S(x)]=\frac{1}{2^n}{\sum }_{x}F(x){\chi }_S(x).$

系数 $\hat{F}(S)$ 称为 $F$ 的 Fourier 系数。由正交归一性立刻得到 Parseval 恒等式：

${\sum }_S\hat{F}(S{)}^2={\mathbb{E}}_x[F(x{)}^2]=1,$

最后一步因为 $F$ 取值 $\pm 1$。这个恒等式是 Fourier sampling 的根基：平方系数构成一个概率分布。

1.3 Influence 的 Fourier 表达

Lemma 1. ${\mathrm{Inf}}_i(f)=\sum _{S\ni i}\hat{F}(S{)}^2$：变量 $i$ 的 influence 恰好等于”含有 $i$ 的那些频率上的 Fourier 质量”。

证明。第一步，把指示函数写成代数式：$F(x)\ne F(x\oplus e_i)$ 时两者一正一负，差为 $\pm 2$，平方为 $4$；相等时差为 $0$。因此

$1[f(x)\ne f(x\oplus e_i)]=\frac{(F(x)-F(x\oplus e_i){)}^2}{4}.$

第二步，对 $x$ 取期望。展开平方，注意 $F^2=1$，以及”把 $x$ 换成 $x\oplus e_i$ 不改变均匀分布”（所以 ${\mathbb{E}}_x[F(x\oplus e_i{)}^2]=1$）：

${\mathrm{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}\hat{F}(S)\hat{F}(T){\mathbb{E}}_x[{\chi }_S(x){\chi }_T(x\oplus e_i)].$

由 ${\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\hat{F}(S{)}^2{\chi }_S(e_i)={\sum }_S\hat{F}(S{)}^2(-1{)}^{[i\in S]}.$

第四步，合并。用 Parseval，

${\mathrm{Inf}}_i(f)=\frac{1}{2}\left({\sum }_S\hat{F}(S{)}^2-{\sum }_S\hat{F}(S{)}^2(-1{)}^{[i\in S]}\right)={\sum }_{S\ni i}\hat{F}(S{)}^2,$

因为 $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，则 $\hat{F}(S)\ne 0$ 蕴含 $S\subseteq J$：Fourier 支持只出现在 $2^J$ 上。

证明。取任意 $S⊈J$，要证 $\hat{F}(S)=0$。存在 $i\in S\setminus J$。把求和按”第 $i$ 位的取值”配对：

$\hat{F}(S)=\frac{1}{2^n}{\sum }_{x}F(x){\chi }_S(x)=\frac{1}{2^n}{\sum }_{x:x_i=0}[F(x){\chi }_S(x)+F(x\oplus e_i){\chi }_S(x\oplus e_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$ 上。这给出一个直接的侦查手段：只要观测到任何 $\hat{F}(S)\ne 0$ 且 $S⊈J$ 的证据，就可以断言 $J$ 之外还有相关变量。第 2 节的 Fourier sampling 正是把这句话算法化。

1.5 Far promise 给出外部质量

测试问题的另一半是”far”情形。下面的引理把 ”$f$ 远离所有 $k$-junta” 翻译成一句可用的定量话：任意删掉 $k$ 个变量，剩下的变量 still 携带至少 $ϵ$ 的 influence 总量。

Lemma 3. 设 $f$ 是 $ϵ$-far from $k$-juntas。则对任意 $J\subseteq [n]$、$|J|\le k$，

${\sum }_{S⊈J}\hat{F}(S{)}^2\ge ϵ,\text{从而}{\sum }_{i\notin J}{\mathrm{Inf}}_i(f)\ge ϵ.$

证明。证明逆否命题的前半：若存在 $|J|\le k$ 使外部 Fourier 质量 $<ϵ$，则 $f$ 不是 $ϵ$-far。构造一个只依赖 $J$ 的近似函数：先把 $F$ 的 Fourier 展开截断到 $J$ 内，

$h(x)={\sum }_{S\subseteq J}\hat{F}(S){\chi }_S(x),$

再取符号 $g(x)=\frac{1-\mathrm{sign}(h(x))}{2}$（$h(x)=0$ 时任取一值）。$g$ 只通过 $x_J$ 依赖 $x$，所以 $g$ 是 $k$-junta。估计距离：当 $f(x)\ne g(x)$ 时 $F(x)$ 与 $h(x)$ 异号（或 $h(x)=0$），故 $|F(x)-h(x)|\ge |F(x)|=1$，即 $1[f\ne g]\le (F-h{)}^2$ 逐点成立。于是

$\mathrm{dist}(f,g)\le {\mathbb{E}}_x[(F-h{)}^2]={\sum }_{S⊈J}\hat{F}(S{)}^2<ϵ,$

中间的等号就是 Parseval：$F-h$ 的展开恰好由被截掉的项组成。这与 ”$f$ 是 $ϵ$-far” 矛盾，第一条不等式得证。

第二条由 Lemma 1 推出：

${\sum }_{i\notin J}{\mathrm{Inf}}_i(f)={\sum }_{i\notin J}{\sum }_{S\ni i}\hat{F}(S{)}^2\ge {\sum }_{S⊈J}\hat{F}(S{)}^2\ge ϵ,$

其中 $\ge$ 是因为每个 $S⊈J$ 至少含一个 $i\notin J$，其质量 $\hat{F}(S{)}^2$ 在左边的双重求和中至少出现一次（含多个外部变量时会重复计数，只会更大）。Q.E.D.

Lemma 3 是整个算法的”燃料”：无论 tester 已经锁定了哪个候选变量集 $J$（至多 $k$ 个），far 情形都保证 $J$ 之外还剩至少 $ϵ$ 的 influence 等待被发现。算法剩下的全部工作，就是高效地”收割”这些外部 influence。

2. Fourier sampling 怎样暴露变量

Fourier sampling 是量子算法探测布尔函数谱结构的标准原语，其线路与 Deutsch–Jozsa 算法（）几乎相同，区别只在输入态的制备。

线路。从 $|0^n⟩$ 出发：

1. 作用 $H^{\otimes n}$，得到均匀叠加 $\frac{1}{2^{n/2}}{\sum }_x|x⟩$；
2. 作用相位预言机 $O_f:|x⟩\mapsto (-1{)}^{f(x)}|x⟩$（由标准比特预言机 $|x⟩|b⟩\mapsto |x⟩|b\oplus f(x)⟩$ 把目标位置于 $|-⟩$ 即得，一次查询），得到

$\frac{1}{2^{n/2}}{\sum }_{x}F(x)|x⟩;$

3. 再作用 $H^{\otimes n}$，在计算基下测量。

第三步之后，结果 $y\in \{0,1{\}}^n$ 的振幅为（用 $H|x_i⟩$ 的矩阵元 $(-1{)}^{x_i{y}_i}/\sqrt{2}$ 逐项相乘再求和）

$⟨y|H^{\otimes n}\left(\frac{1}{2^{n/2}}{\sum }_{x}F(x)|x⟩\right)=\frac{1}{2^n}{\sum }_{x}F(x)(-1{)}^{x\cdot y}=\hat{F}(S_y),$

其中 $S_y=\{i:y_i=1\}$ 是 $y$ 的支持集，等号就是 $\hat{F}$ 的定义。因此测量结果是子集 $S\subseteq [n]$，且测得 $S$ 的概率为 $\hat{F}(S{)}^2$——Parseval 保证这些概率确实归一。一句话总结：Fourier sampling 用 $O(1)$ 次查询，从”Fourier 平方分布”中采一个样本。

Atıcı–Servedio 式 tester 的思路（Zoo 267）。维护一个候选相关变量集 $J$，反复做 Fourier sampling：

• 若 $f$ 是 $J^{\ast }$-junta（$|J^{\ast }|\le k$），由 Lemma 2 所有非零谱都在 $2^{J^{\ast }}$ 内，采样永远不会给出 $J^{\ast }$ 之外的变量；采样足够多次后若收集到的变量数 $\le k$，接受。
• 若 $f$ 是 $ϵ$-far 而当前 $|J|\le k$，由 Lemma 3 外部质量 ${\sum }_{S⊈J}\hat{F}(S{)}^2\ge ϵ$，即每次采样至少有概率 $ϵ$ 命中一个 $J$ 之外的频率，从而暴露一个新变量。期望 $O(1/ϵ)$ 次采样发现一个新变量；far 情形迟早收集到第 $k+1$ 个变量，此时拒绝。

发现 $k$ 个变量各需 $O(1/ϵ)$ 次采样，总查询约 $O(k/ϵ)$。

瓶颈在哪。这个分析对”发现变量”是有效的，但它本质上是一个 coupon collector：变量被逐个收集，每个变量都等到它被采中为止。设想 far 情形的 influence 分布很不均：可能有 $\Theta (k)$ 个变量各自只带 $\Theta (ϵ/k)$ 的 influence。外部质量摊到每次采样上只有 $ϵ$，而其中”命中某个特定低 influence 变量”的概率只有 $\Theta (ϵ/k)$——逐个收集所有这类变量需要 $\Omega (k\cdot (k/ϵ))$ 级别的乐观估计也救不回来（实际分析通过只收集到 $k$ 个为止来避免最坏情形，但 $O(k/ϵ)$ 的对 $k$ 线性依赖由此而来）。要突破对 $k$ 的线性依赖，必须放弃”逐个收集”，改成批量计数：一次性估计”具有某档 influence 的变量大约有多少个”。这正是下一节原语的动机。

3. Gapped Group Testing 原语

3.1 从 group testing 到 gapped 版本

经典的 group testing 模型：有一个未知集合 $A\subseteq [n]$（“特殊项”，比如人群中的感染者），算法可以查询任意子集 $S\subseteq [n]$，oracle 回答

$g_A(S)=1[S\cap A\ne \varnothing ],$

即”这一组里有没有特殊项”。一次查询检测一整个组，这是它优于逐项检查的原因。

本词条需要的是它的判定版本。Gapped group testing (GGT) 承诺 $|A|$ 落在两个不相交的区间之一：

$|A|\le k\text{或}|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$ 较小时，

$\mathrm{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]$，共 $\left(\genfrac{}{}{0ex}{}{n}{\le k}\right)+\left(\genfrac{}{}{0ex}{}{n}{\ge k+d}\right)$ 个）指派状态，空间是指数大的。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。

4.1 分桶与 pigeonhole

设 $f$ 是 $ϵ$-far。由 Lemma 3，任意候选集 $J$（$|J|\le k$）之外的变量携带总 influence 至少 $ϵ$。把 $J$ 之外的变量按 influence 大小分桶：第 $j$ 桶装 influence 落在

${\tau }_j\asymp \frac{2^jϵ}{k}$

附近的变量（即区间 $[{\tau }_j/2,{\tau }_j]$ 之类，常数因子不影响渐近）。值得考虑的尺度范围是从 $ϵ/k$（低于它的单桶贡献可忽略）到 $1$，所以桶数为

$j=0,1,\dots ,O\left(\log \frac{k}{ϵ}\right).$

鸽巢论证：每个桶对总外部 influence 的贡献约为”桶内变量数 $\times$ 该桶尺度”。设第 $j$ 桶有 $m_j$ 个变量，则 ${\sum }_j{m}_j{\tau }_j\ge ϵ$（总质量），而桶数只有 $O(\log (k/ϵ))$ 个。由平均原理，至少存在一个桶 $j$ 满足

$m_j{\tau }_j\gtrsim \frac{ϵ}{\log (k/ϵ)}⟹m_j\gtrsim \frac{ϵ/{\tau }_j}{\log (k/ϵ)}=\frac{k/2^j}{\log (k/ϵ)},$

其中最后一步代入 ${\tau }_j=2^jϵ/k$，即 $ϵ/{\tau }_j=k/2^j$。把对数因子吸进 $\gtrsim$ 记号，结论写成：

对某个桶 $j$，$J$ 之外至少有 $d_j\gtrsim k/2^j$ 个变量，每个的 influence 至少约为 ${\tau }_j$。

这是归约的关键产出：far 情形必然在某个尺度上”堆积”了大量变量。注意 $d_j{\tau }_j\gtrsim ϵ$ 对所有 $j$ 成立——这个乘积守恒是后面复杂度平衡的原因。

（严格地说还有第二种情形：大量 influence 极低的变量，单个低于最小桶的阈值，但数目远多于 $k$，其联合 influence 仍可达 $\Omega (ϵ)$——随机取一个小子集翻转就能以可检测的概率改变输出。Zoo 266 对这类”极低 influence 但数量庞大”的情形用随机小子集上的联合 influence 检测处理；思想相同，下面我们只展开第一种、也就是最典型的情形。）

4.2 把”桶内变量检测”实现为 group-test 查询

GGT 的 oracle 回答”子集 $S$ 是否含有特殊项”。这里”特殊项”就是第 $j$ 桶里的变量，$A$ 是桶内变量集合。我们需要用对 $f$ 的查询实现

$g_j(S)\approx 1[S\text{ 含有某个 influence 约 }{\tau }_j\text{ 的变量}].$

实现方法是翻转测试：均匀随机取 $x$，再随机重洗 $S$ 内的坐标得到 $x^{\prime }$，比较 $f(x)$ 与 $f(x^{\prime })$。若 $S$ 含有一个 influence $\ge {\tau }_j$ 的变量 $i$，那么仅翻转 $i$ 就有 $\ge {\tau }_j$ 的概率改变输出；随机重洗 $S$ 至少以相当的比例”翻到 $i$ 这一位”，因此

${\mathrm{Pr}}_{x,x^{\prime }}[f(x)\ne f(x^{\prime })]=\Omega ({\tau }_j).$

换句话说，“检测到一次输出变化”这个事件的成功概率 $p$ 是 $\Omega ({\tau }_j)$ 量级的。由振幅放大（成功概率 $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 ϵ$：

$\sqrt{\frac{k}{d_j{\tau }_j}}\lesssim \sqrt{\frac{k}{ϵ}}.$

每个桶的成本都平衡到同一个值 $\sqrt{k/ϵ}$——这正是取 $d_j\propto k/2^j$、${\tau }_j\propto 2^jϵ/k$ 这组”共轭”参数的目的：$d_j$ 随 $j$ 指数衰减（高 influence 桶变量少），${\tau }_j$ 随 $j$ 指数增长（高 influence 桶检测便宜），两种成本在乘积中精确抵消。桶数只有 $O(\log (k/ϵ))$ 个，再加上把 tester 成功率放大到常数所需的对数因子，全部被 $\tilde{O}$ 吸收，最终

$\tilde{O}\left(\sqrt{k/ϵ}\right)\text{次 }f\text{ 查询}.$

4.4 算法全貌与随机化

完整的 tester 可以这样理解：

1. 随机选取桶的尺度 $j$（共 $O(\log (k/ϵ))$ 种，均匀随机选一种即有 $\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$ 是 $ϵ$-far，由第 4.1 节存在某个堆积桶 $j^{\ast }$；随机选桶以 $\Omega (1/\log (k/ϵ))$ 的概率选中它，选中时 GGT 以常数概率回答”多”，重复 $O(\log )$ 轮即可把整体成功率提到常数——这些对数开销同样是 $\tilde{O}$ 的一部分。这就完成了 $\tilde{O}(\sqrt{k/ϵ})$ 查询 tester 的构造。

5. 时间高效实现

到目前为止讨论的都是查询复杂度。Adversary bound 保证查询算法的存在性，但把它编译成电路时有个明显障碍：GGT 算法的工作寄存器要索引所有子集 $S\subseteq [n]$，即 Hilbert 空间

$M^n=\mathrm{span}\{|S⟩: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⟩$ 看作逐个比特喂入的流，每读入一位就对当前的不可约模块标签做一次小的酉更新（每步只作用在 $O(\log n)$ 到 $O(\mathrm{poly}\log )$ 量级个辅助维度上，并需要操作一个 $n$ 位的 query register）。$n$ 位全部处理完后即完成一次所需反射，单次代价

$\tilde{O}(n).$

把它乘上查询数：总门复杂度

$\tilde{O}\left(n\sqrt{k/ϵ}\right),$

约等于查询数乘以”处理一个 $n$ 位查询寄存器”的最低线性成本。换言之，查询优势在至多近线性的每查询开销下转化成了时间优势——这正是本词条反复强调的”同时追踪 setup/update/check 成本”的一个正面例子：这里的 setup 与 update 都足够便宜，没有把 $\sqrt{k/ϵ}$ 的查询优势偷偷换掉。

6. 下界与 exact group testing 的区别

下界一侧。目前已知的量子查询下界来自 image-size testing / collision testing 类问题的归约：固定 $ϵ$ 时，junta testing 需要

$\Omega \left(k^{1/3}\right)$

次量子查询。它与上界 $\tilde{O}(\sqrt{k})=\tilde{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_3{x}_4),$

其中 $x_3{x}_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$ 影响），故 ${\mathrm{Inf}}_1(f)=1$。
• 变量 $2$：$f$ 根本不含 $x_2$，${\mathrm{Inf}}_2(f)=0$。
• 变量 $3$：$f(x\oplus e_3)\ne f(x)$ 当且仅当 $x_3{x}_4$ 变号，即 $x_4=1$（此时 $x_3$ 从 $0$ 到 $1$ 或反之，AND 值翻转）。$\mathrm{Pr}[x_4=1]=1/2$，故 ${\mathrm{Inf}}_3(f)=1/2$。
• 变量 $4$：同理，需要 $x_3=1$，${\mathrm{Inf}}_4(f)=1/2$。

第二步：算 Fourier 谱。 $F(x)=(-1{)}^{x_1\oplus x_3{x}_4}=(-1{)}^{x_1}(-1{)}^{x_3{x}_4}$。AND 的 $\pm 1$ 形式有标准展开（对四种 $(x_3,x_4)$ 逐点验证：$(0,0),(1,0),(0,1)$ 处得 $+1$，$(1,1)$ 处得 $-1$）

$(-1{)}^{x_3{x}_4}=\frac{1}{2}+\frac{1}{2}{\chi }_{\{3\}}(x)+\frac{1}{2}{\chi }_{\{4\}}(x)-\frac{1}{2}{\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△T}$：

$F(x)=\frac{1}{2}{\chi }_{\{1\}}+\frac{1}{2}{\chi }_{\{1,3\}}+\frac{1}{2}{\chi }_{\{1,4\}}-\frac{1}{2}{\chi }_{\{1,3,4\}}.$

所以非零 Fourier 系数恰有四个：$\hat{F}(\{1\})=\hat{F}(\{1,3\})=\hat{F}(\{1,4\})=\frac{1}{2}$，$\hat{F}(\{1,3,4\})=-\frac{1}{2}$。

第三步：逐项验证本词条的各个断言。

• Parseval：$4\times (\frac{1}{2}{)}^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\ni 1}\hat{F}(S{)}^2=4\times \frac{1}{4}=1={\mathrm{Inf}}_1$；${\sum }_{S\ni 3}\hat{F}(S{)}^2=2\times \frac{1}{4}=\frac{1}{2}={\mathrm{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_3{x}_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$（可猜对）。最优距离 $=\mathrm{Pr}[x_3=1]\cdot \frac{1}{2}=\frac{1}{4}$（取 $g=x_1$ 或 $g=x_1\oplus x_3$ 都达到）。
• 保留 $\{1,4\}$：与上对称，距离 $\frac{1}{4}$。

故 $\mathrm{dist}(f,2\text{-juntas})=\frac{1}{4}$：$f$ 是 $\frac{1}{4}$-far from 2-juntas。结论：对 $ϵ\le \frac{1}{4}$，$k=2$ 的 tester 应拒绝 $f$；对 $ϵ>\frac{1}{4}$，$f$ 不满足 far promise，tester 输出任意。这个例子说明 far 参数 $ϵ$ 是问题输入的一部分，“相关变量有 $k+1$ 个”与”远离所有 $k$-junta”是两回事——后者还要求这些变量合起来携带足够大的影响，而不仅仅是存在。

8. 小结与习题

小结。

• Junta testing 的 far promise 通过 Fourier 分析转化为定量资源：任意 $k$ 个变量之外仍留有至少 $ϵ$ 的 influence / Fourier 质量（Lemma 3）。
• Fourier sampling 能以常数次查询从平方谱分布中采样，Atıcı–Servedio 式 tester 靠逐个收集变量达到 $O(k/ϵ)$；但 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ϵ/k$ 分桶后，far 情形保证某桶堆积 $d_j\gtrsim k/2^j$ 个变量；GGT 查询数 $\sqrt{k/d_j}$ 与单次检测成本 $1/\sqrt{{\tau }_j}$ 因 $d_j{\tau }_j\gtrsim ϵ$ 而精确平衡，每桶成本同为 $\sqrt{k/ϵ}$，总计 $\tilde{O}(\sqrt{k/ϵ})$。
• 对称群的浅层表示分解（逐比特 Clebsch–Gordan 更新）使每次反射只需 $\tilde{O}(n)$ 时间，总门复杂度 $\tilde{O}(n\sqrt{k/ϵ})$，查询优势在近线性开销下转化为时间优势。
• 下界 $\Omega (k^{1/3})$（固定 $ϵ$）与上界之间仍有空隙；与 exact CGT 的 $O(k\log k)$ 相比，tester 靠”只判定、不学习”绕过了收集全部变量的 $k$ 级开销。

习题。

1. （Fourier 基础）证明 Lemma 2：$J$-junta 的 Fourier 支持只在 $2^J$ 上。进一步说明：$J$-junta 的非零 Fourier 系数至多 $2^{|J|}$ 个，因此 Fourier sampling 可能的测量结果至多 $2^k$ 种。
2. （谱计算）对第 7 节的例子 $f=x_1\oplus (x_3{x}_4)$，用定义与 Lemma 1 两种方法计算四个单变量 influence，验证它们一致；并计算总 influence ${\sum }_i{\mathrm{Inf}}_i(f)$，验证它等于 ${\sum }_S|S|\hat{F}(S{)}^2$。
3. （far $\Rightarrow$ 质量）补全 Lemma 3 的证明细节：说明为什么截断函数 $h$ 取符号后得到的 $g$ 是 $k$-junta，以及为什么 $1[f\ne g]\le (F-h{)}^2$ 逐点成立。
4. （经典基准）补全第 3.2 节的采样分析：设每次查询以概率 $p$ 独立放入每个下标，写出命中概率 $1-(1-p{)}^a$ 在 $pa$ 小时的近似，并说明 $p\approx 1/k$ 是区分 $a=k$ 与 $a=k+d$ 的最优选择，最终样本数为 $(k/d{)}^2$ 量级。
5. （复杂度比较）比较 exact combinatorial group testing 与 GGT 的输出信息量与复杂度：为什么”找出全部特殊项”不可能有 $\sqrt{k/d}$ 级别的算法？（提示：考虑输出本身包含的比特数。）由此解释 junta tester 为什么必须走”判定”而非”学习”路线。
6. （分桶平衡）补全第 4.1 节的 pigeonhole 论证：设 ${\sum }_j{m}_j{\tau }_j\ge ϵ$、桶数 $O(\log (k/ϵ))$，证明存在 $j$ 使 $m_j\gtrsim k/2^j$；再验证取 $d_j\asymp k/2^j$、${\tau }_j\asymp 2^jϵ/k$ 时 $\sqrt{k/d_j}\cdot 1/\sqrt{{\tau }_j}$ 与 $j$ 无关。

参考文献与 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。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/junta-group-testing
• 内容遵循 CC BY-NC-SA 4.0 许可协议