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 覆盖