# 一般子集寻找：Johnson 图量子行走的 $N^{k/(k+1)}$ 模板

Element distinctness 只是在找一对满足“函数值相同”的索引。更一般地，给定 oracle $f:D\to R$ 和一个可由已查询数据判定的 $k$ 元性质 $P$，我们要找

$$
\{x_1,\ldots,x_k\}\subset D
$$

使 $((x_1,f(x_1)),\ldots,(x_k,f(x_k)))\in P$。Childs--Eisenberg 指出 Ambainis 的 Johnson 图算法无需使用“相等”这一特殊结构，直接给出 $O(N^{k/(k+1)})$ 通用查询模板。

## 1. 问题模型与 property oracle

令 $N=|D|$，$k$ 为常数。算法可查询

$$
O_f|x,z\rangle=|x,z\oplus f(x)\rangle.
$$

性质 $P$ 只允许读取已经存储的 $(x,f(x))$；例如：

- $k$-sum：$f(i)=a_i$，要求 $\sum_{j=1}^k a_{i_j}=t$；
- $k$-distinctness：要求 $f(i_1)=\cdots=f(i_k)$；
- 给定显式兼容表，要求所选 $k$ 对构成某种局部结构。

若检查 $P$ 本身还要新查询，必须把成本放进 check term，不能宣称免费。

## 2. 行走状态与标记条件

选择参数 $r\ge k$，在 Johnson 图 $J(N,r)$ 上行走。每个顶点是 $r$ 元子集 $S\subset D$，并维护

$$
D(S)=\{(x,f(x)):x\in S\}.
$$

若 $S$ 内含某个满足 $P$ 的 $k$ 元子集，就标记 $S$。设置数据需 $r$ 次查询；相邻顶点替换一个元素，update 需常数次查询；有合适哈希/索引时，check 只用已存数据。

## 3. 标记比例与谱隙

先分析最坏只有一个目标集合

$$
T=\{x_1^*,\ldots,x_k^*\}.
$$

随机 $r$ 元子集包含 $T$ 的概率

$$
\epsilon=
\frac{\binom{N-k}{r-k}}{\binom Nr}
=\prod_{j=0}^{k-1}
\frac{r-j}{N-j}
=\Theta((r/N)^k).
$$

Johnson 随机替换链谱隙

$$
\delta=\Theta(1/r).
$$

Szegedy 搜索的 walk steps 为

$$
O\!\left(
\frac1{\sqrt{\delta\epsilon}}
\right)
=O\!\left(
\frac{N^{k/2}}{r^{(k-1)/2}}
\right).
$$

## 4. 平衡得到通用指数

总查询数

$$
Q(r)=O\!\left(
r+\frac{N^{k/2}}{r^{(k-1)/2}}
\right).
$$

平衡两项：

$$
r^{(k+1)/2}=N^{k/2}
\quad\Longrightarrow\quad
r=N^{k/(k+1)}.
$$

因此

$$
Q=O(N^{k/(k+1)}).
$$

$k=1$ 给 $N^{1/2}$（Grover），$k=2$ 给 $N^{2/3}$（element distinctness），清楚展示同一模板。

如果有 $M$ 个近似不重叠的目标集合，$\epsilon$ 约增大 $M$ 倍，搜索更快；上式是唯一 witness 的保守最坏界。

## 5. $k$-sum 的匹配下界

给定 $a_1,\ldots,a_N$，寻找 $k$ 个不同索引满足

$$
a_{i_1}+\cdots+a_{i_k}=t
$$

是该框架的直接实例。对足够大的值域，negative-weight adversary 方法构造输入对矩阵，证明

$$
Q(k\text{-sum})
=\Omega(N^{k/(k+1)}),
$$

与 Johnson 上界匹配。下界依赖值域/群足够大及固定 $k$；不能直接外推到任意小模数或 $k$ 随 $N$ 增长。

## 6. 与任意大小 subset-sum 的区别

[量子子集和](../ch09-algebra-number-theory/quantum-subset-sum.md)允许选任意大小子集，搜索空间是 $2^N$，问题 NP 完全，最佳算法仍为指数时间。这里的 subset finding 把 $k$ 当常数，搜索证书大小固定，复杂度是 $N$ 的多项式。

同名的 $k$-subset-sum 因此有两种参数化：

- 固定 $k$、列表长度 $N$ 增长：本课 $N^{k/(k+1)}$；
- $k=\Theta(N)$ 或任意子集：指数算法与 representation technique。

## 7. 图 clique 为何需要额外一层

若 $D$ 是图顶点、$P$ 是“所选 $k$ 点形成 clique”，检查需要知道 $\binom k2$ 条边。若 edge oracle 的值不随单个顶点查询返回，$D(S)$ 必须缓存诱导子图，setup/update 成本分别约为 $r^2$、$r$，平衡指数改变。Childs--Eisenberg 给出多种 clique 算法，说明通用公式只有在 property 真能由 $f(S)$ 免费判定时才直接适用。

## 8. 小例子：3-sum

列表

$$
(2,5,8,11,14),\qquad t=24
$$

有目标索引集合 $\{0,2,4\}$，因为 $2+8+14=24$。行走维护 $r$ 个索引和其值；一个状态被标记当缓存中任意三值之和为 24。对大 $N$ 取 $r=N^{3/4}$，setup 与 $N^{3/2}/r$ walk cost 同阶。

## 9. 小结与习题

- Johnson 状态缓存 $r$ 个 oracle 值，标记条件可为任意固定大小性质。
- 唯一 $k$ 元 witness 的标记比例为 $\Theta((r/N)^k)$。
- 谱隙 $1/r$ 与 setup $r$ 平衡，得到 $N^{k/(k+1)}$。
- Property 检查若需额外 oracle，必须重算 setup/update/check。

1. 精确推导包含固定 $T$ 的组合概率。
2. 对 $k=3$ 最小化总成本并得到 $N^{3/4}$。
3. 解释多个 witness 如何改变 $\epsilon$。
4. 为 clique edge oracle 写出新的 setup 与 update 成本。

## 参考文献

- Zoo 编号 162：Andrew Childs 与 Jason Eisenberg, [Quantum Algorithms for Subset Finding](https://arxiv.org/abs/quant-ph/0311038).
- Zoo 编号 7：Andris Ambainis, [Quantum Walk Algorithm for Element Distinctness](https://arxiv.org/abs/quant-ph/0311001).
- Zoo 编号 163：Aleksandrs Belovs 与 Robert Špalek, [Adversary Lower Bound for the $k$-Sum Problem](https://arxiv.org/abs/1206.6528).