# Junta 测试与 Gapped Group Testing：从变量影响到对抗界

一个 $k$-junta 只依赖 $n$ 个输入变量中的至多 $k$ 个。我们不要求找出函数真值表，而只区分“确为 $k$-junta”和“与任何 $k$-junta 至少相差 $\epsilon$ 比例输入”。量子算法把“有多少变量具有某档 influence”化为 gapped group testing，再用对抗 SDP 构造查询算法，达到

$$
\widetilde O(\sqrt{k/\epsilon})
$$

查询。

## 1. 距离、相关变量与 influence

给定

$$
f:\{0,1\}^n\to\{0,1\}.
$$

变量 $i$ 的 influence 为

$$
\operatorname{Inf}_i(f)
=\Pr_x[f(x)\ne f(x\oplus e_i)].
$$

对变量集合 $S$ 可定义随机翻转 $S$ 内坐标造成输出变化的概率，或用 Fourier 权重表达其联合 influence。

若存在 $J\subseteq[n]$、$|J|\le k$，使 $f(x)$ 只由 $x_J$ 决定，则所有 $i\notin J$ influence 为 0。若 $f$ 与任意 $k$-junta 的 normalized Hamming 距离至少 $\epsilon$，那么删去任意 $k$ 个变量后，剩余 Fourier/influence 质量仍至少为 $\Omega(\epsilon)$。

## 2. Fourier sampling 怎样暴露变量

令相位函数

$$
F(x)=(-1)^{f(x)}
$$

并制备

$$
\frac1{2^{n/2}}
\sum_xF(x)|x\rangle.
$$

做 $H^{\otimes n}$ 后测得子集 $S\subseteq[n]$ 的概率为

$$
\widehat F(S)^2.
$$

若 $f$ 是 $J$-junta，Fourier 支持只出现在 $S\subseteq J$；测得 $J$ 外索引立即证明相关变量超过当前候选集。早期 tester 反复 Fourier sampling 并积累变量，查询约 $O(k/\epsilon)$。问题是很多额外变量可能各自 influence 很小，逐个“coupon collector”效率低。

## 3. Gapped Group Testing 原语

未知集合 $A\subseteq[n]$，group-test oracle

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

Gapped 版本承诺

$$
|A|\le k
\quad\text{或}\quad
|A|\ge k+d,
$$

只需判断哪种。其量子查询复杂度为

$$
\Theta(\sqrt{k/d}),\qquad d\le k.
$$

这个公式显示大 gap 时可超过通常的平方加速：当 $d\ge\sqrt k$，经典随机复杂度约 $(k/d)^2$（忽略对数），量子为 $(k/d)^{1/2}$，在参数幂上形成 quartic gap。

算法不是普通 Grover。作者直接构造 dual adversary SDP 的可行向量，利用输入只依赖 $|A|$ 的置换对称性，把指数大的子集空间分解成少量 $S_n$ 不可约模块；对应双反射算法实现查询。特殊的“irrelevant variables”设计允许某些 $S$ 上 oracle 值任意，仍保持 adversary 正确，这对 junta 归约中的噪声很关键。

## 4. Influence 分桶归约

若 $f$ 远离所有 $k$-junta，额外变量总 influence 至少 $\epsilon$。按尺度分桶：第 $j$ 桶含 influence 约

$$
\tau_j\asymp\frac{2^j\epsilon}{k}
$$

的变量。对 $O(\log(k/\epsilon))$ 个桶之一，必有以下结构：

1. 至少
   $$
   d_j\gtrsim k/2^j
   $$
   个额外变量，每个 influence 至少 $\tau_j$；或
2. 远多于 $k$ 个极低 influence 变量，其随机小子集具有可检测的联合 influence。

给定查询子集 $S$，用常数/振幅放大次数的 $f$ 查询判断“$S$ 是否含该桶的 influential variable”，得到带 irrelevant/noisy inputs 的 group-test oracle。GGT 以

$$
O(\!\sqrt{k/d_j})
$$

次此类测试区分 relevant-variable 数至多 $k$ 与至少 $k+d_j$。每次 influence 检测约含 $1/\sqrt{\tau_j}$ 的放大成本；代入 $d_j,\tau_j$ 后各桶总成本平衡到

$$
\widetilde O(\sqrt{k/\epsilon}).
$$

随机选择桶/尺度并放大成功率覆盖全部远实例。

## 5. 时间高效实现

Adversary bound 保证查询算法存在，但直接对 $2^n$ 个子集基态做反射可能指数慢。这里子集 Hilbert 空间

$$
M^n=\operatorname{span}\{|S\rangle:S\subseteq[n]\}
$$

承载对称群 $S_n$ 的自然置换表示。算法只需浅层表示分解，而非完整正则表示 QFT；类似 Schur--Weyl transform 的逐比特 Clebsch--Gordan 更新可在

$$
\widetilde O(n)
$$

时间实现一次所需反射。总门复杂度

$$
\widetilde O(n\sqrt{k/\epsilon}),
$$

约是查询数乘处理 $n$ 位 query register 的最低线性成本。

## 6. 下界与 exact group testing 的区别

由 image-size/collision testing 约化可得固定 $\epsilon$ 下

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

量子下界，尚未与 $\widetilde O(\sqrt k)$ 上界闭合。

Exact combinatorial group testing 要找出所有至多 $k$ 个特殊项；Ambainis--Montanaro 给 $O(k\log k)$ 查询。GGT 只比较基数区间，因而可以是 $\sqrt{k/d}$。Junta tester 使用的是带 gap 的判定原语，不会输出完整 relevant-variable 集。

## 7. 小例子

$$
f(x_1,x_2,x_3,x_4)=x_1\oplus(x_3x_4)
$$

是 3-junta，相关集 $J=\{1,3,4\}$；变量 2 influence 为 0。Fourier sampling 的任何非零系数支持都不含 2。若测试 $k=2$，函数不一定在给定 $\epsilon$ 下远离所有 2-junta，需要计算最佳近似距离；“依赖 3 个变量”本身不足以满足 far promise。

## 8. 小结与习题

- Junta far promise 转化为任意 $k$ 变量外仍有 influence/Fourier 质量。
- Fourier sampling 能发现变量，但逐个收集对低 influence 变量低效。
- Gapped group testing 的 $\Theta(\sqrt{k/d})$ 原语批量检测某影响尺度的变量数。
- 对称群浅 QFT 让 adversary 构造同时具备近线性每查询时间。

1. 证明 $J$-junta 的 Fourier 支持只在 $2^J$ 上。
2. 对例子计算四个单变量 influence。
3. 比较 exact CGT 与 GGT 的输出信息量和复杂度。
4. 用 pigeonhole/分桶论证额外 influence 质量必落在某个尺度。

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