一般子集寻找

在碰撞与元素唯一性词条中，我们解决了一个具体的搜索问题：给定 oracle $f:[N]\to [M]$，找两个索引 $i\ne j$ 使 $f(i)=f(j)$。Element distinctness 只是在找一对满足”函数值相同”的索引。本词条把这一问题推广到它的一般形态。

Subset finding 问题：给定 oracle $f:D\to R$ 和一个固定的 $k$ 元性质 $P$（$k$ 是与 $N$ 无关的常数），要求找出一个 $k$ 元子集

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

使得

$$((x_1,f(x_1)),\dots ,(x_k,f(x_k)))\in P.$$

也就是说，证书由 $k$ 个索引以及它们的函数值组成，而性质 $P$ 只允许读取这 $k$ 对 $(x,f(x))$ 来判定。这里 $k$ 固定、$N=|D|$ 增长的参数化方式是本词条一切结论的前提，请务必记住。

历史脉络。$k=1$ 时这就是无结构搜索，Grover 算法给出 $O(\sqrt{N})$；$k=2$、$P$ 取”两个函数值相等”时就是 element distinctness，Ambainis 在 2003 年用 Johnson 图上的量子行走给出 $O(N^{2/3})$（Zoo 7），这是量子行走超越 Grover 框架的第一个里程碑。Childs 与 Eisenberg 随即指出：Ambainis 的算法其实从未用到”相等”这一特殊结构——它只是要求”缓存的子集中存在一个可由已查询数据判定的 $k$ 元证书”。把这一点抽象出来，就得到对所有固定 $k$ 元性质都适用的 $O(N^{k/(k+1)})$ 通用查询模板（Zoo 162）。随后 Belovs 与 Špalek 用 negative-weight adversary 方法证明，对 $k$-sum 这一具体实例，$\Omega (N^{k/(k+1)})$ 也是下界（Zoo 163），说明这个指数不是分析上的巧合。

为什么经典算法和朴素量子算法都不够好。在进入量子行走之前，先看清两条”捷径”为什么走不通。

• 经典算法：最坏情况下必须查询几乎所有输入。以 element distinctness 为例，若对手把前 $N-1$ 次查询都回答成互不相同的值，我们仍然无法判断最后一个值是否造成碰撞；一般地，判定一个”最坏情形只有唯一 witness”的 $k$ 元性质需要 $\Theta (N)$ 次查询。
• 朴素量子算法：把搜索空间取为所有 $k$ 元子集，直接 Grover。$k$ 元子集共有 $\left(\genfrac{}{}{0ex}{}{N}{k}\right)=\Theta (N^k)$ 个（$k$ 为常数），Grover 需要

$$\Theta \left(\sqrt{\left(\genfrac{}{}{0ex}{}{N}{k}\right)}\right)=\Theta \left(N^{k/2}\right)$$

次查询。$k=2$ 时这是 $\Theta (N)$，与经典完全一样，毫无优势。$k$ 越大，这个朴素指数 $k/2$ 越糟。

问题的根源在于：Grover 的每一步都要从头构造一个候选 $k$ 元子集，查询它的全部 $k$ 个函数值，然后丢弃。相邻两次迭代之间没有任何信息被保留。量子行走的核心思想是把已查询的数据留在状态里：让候选集合每次只变化一个元素，这样每步只需 $O(1)$ 次新查询，省下的查询预算换成”走得更慢但更便宜”的搜索。本词条的目的就是把这句口号变成精确的复杂度账目。

1. 问题模型与 property oracle

先固定记号。令 $N=|D|$，$k$ 为常数。算法通过标准 XOR oracle 访问 $f$：

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

我们按**查询复杂度 (query complexity)** 计量成本：每调用一次 $O_f$ 记一次，其余酉操作不计（但数据结构的可逆性要求会在讨论中说明）。

性质 $P$ 的访问方式是本词条的关键约定：$P$ 只允许读取已经存储在状态里的 $(x,f(x))$ 对，不允许额外调用 $O_f$。典型的合法例子：

• $k$-sum：$f(i)=a_i\in G$（$G$ 是某个 Abel 群或足够大的值域），要求所选索引满足

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

• $k$-distinctness：要求

$$f(i_1)=f(i_2)=\cdots =f(i_k);$$

• 一般兼容性条件：给定一张显式的兼容表（例如预先给出的”允许的 $k$ 元组取值”列表），要求所选 $k$ 对 $(x_j,f(x_j))$ 构成表中允许的某种局部结构。

一条必须遵守的记账纪律：若检查 $P$ 本身还需要新的 oracle 查询（最典型的情形是 $P$ 涉及输入之间的关系，例如”所选顶点两两有边”，而边的信息不随顶点查询返回），那么这些查询必须计入成本，不能宣称检查免费。后文第 7 节的 clique 例子会展示违反这条纪律会发生什么。通用模板的全部结论只在”check 零查询”的前提下成立。

2. 核心直觉：把搜索变成图上的行走

在形式化之前，先用平实语言说清楚算法为什么是对的。

搜索的困难在于”候选太多、每个候选的验证太贵”。Grover 每次从头掷一个全新的 $k$ 元子集，验证它要花 $k$ 次查询，验证完就扔掉。量子行走换一种玩法：维护一个大小为 $r$ 的工作集 $S$（$r\ge k$ 是一个待选参数），把它连同其中所有元素的函数值一起缓存。如果 $S$ 里已经藏着某个满足 $P$ 的 $k$ 元子集，我们就成功了——这样的 $S$ 称为被标记的 (marked)。

接下来不再是”掷新候选”，而是”走动”：每一步从 $S$ 中删掉一个元素、加入一个新元素。因为旧数据都在缓存里，这一步只需要查询一个新元素的函数值——$O(1)$ 次查询，而不是 $k$ 次。所有可能的工作集连同”删一添一”的相邻关系构成一张图，这就是 Johnson 图 $J(N,r)$；算法就是在这张图上做量子版本的随机行走搜索，希望尽快走到一个被标记的顶点上。

这个图景里有两股相互竞争的力量，理解它们就理解了整个复杂度分析：

• 标记顶点太稀少。随机一个 $r$ 元子集恰好包含目标 $k$ 元子集的概率 $ϵ$ 大约是 $(r/N{)}^k$。$r$ 取得越大，标记比例越高，搜索越容易。
• 图越来越难走。工作集越大，每一步只能换一个元素，要让状态”忘记”起点、混合到全图上，需要的步数就越多；反映在谱隙上，$\delta =\Theta (1/r)$，$r$ 越大谱隙越小，行走越慢。

量子行走搜索的步数由乘积 $\delta ϵ$ 控制（第 4 节给出框架），于是我们面对一个经典的参数平衡问题：$r$ 太小则标记太稀，$r$ 太大则行走太慢且初始缓存太贵。第 5 节会展示最优的 $r$ 恰好让”初始建缓存的成本”与”行走搜索的成本”同阶，而平衡点是 $r=N^{k/(k+1)}$。

3. 行走状态与标记条件

现在把上一节的图景形式化。选择参数 $r\ge k$，在 Johnson 图 $J(N,r)$ 上行走。图的每个顶点是一个 $r$ 元子集 $S\subset D$；两个顶点相邻当且仅当它们恰好在一个元素上不同，即存在 $x\in S$、$x^{\prime }\notin S$ 使 $S^{\prime }=S\setminus \{x\}\cup \{x^{\prime }\}$。

算法为每个顶点维护缓存

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

即 $S$ 中每个元素及其函数值的列表，存放在合适的数据结构中（排序数组、哈希表等）。行走状态因此是形如 $|S⟩\otimes |D(S)⟩$ 的叠加。

标记条件：若 $S$ 内存在某个 $k$ 元子集 $\{x_1,\dots ,x_k\}\subset S$ 使 $((x_1,f(x_1)),\dots ,(x_k,f(x_k)))\in P$，就标记 $S$。注意这个判定只读取 $D(S)$ 中已存的数据，符合第 1 节对 property oracle 的约定。

三项成本分别核算：

• Setup（初始建立）：制备所有 $r$ 元子集的均匀叠加，并为每个 $S$ 查询其中全部 $r$ 个函数值以建立 $D(S)$。这需要 $r$ 次查询，一次付清。
• Update（走一步）：从 $S$ 走到相邻的 $S^{\prime }$ 时，只有一个元素被替换。新元素的函数值需要 $1$ 次新查询（实际上还要把被删元素的旧值可逆地擦除，这是常数次额外操作和一次”反查询”，不改变量级），故 update 是常数次查询。
• Check（判定标记）：只读取 $D(S)$。在有合适的哈希/索引结构时，例如判 $k$-distinctness 只需在按值哈希的表中查找，判 $k$-sum 可以在排序缓存上查找补数，都不需要新的 oracle 调用，故 check 为 $0$ 次查询。

查询模型把数据结构操作视为免费；真实电路中要在叠加的 $S$ 上可逆地维护 $D(S)$，需要可逆哈希、radix tree 等技术把 update/check 压到 polylog 时间开销。本词条的 $O(\cdot )$ 结论都是查询复杂度结论，这一点与前一词条对 element distinctness 的说明一致。

4. 量子行走搜索框架：步数由 $\delta ϵ$ 控制

我们不重新推导量子行走搜索定理（其细节属于 Szegedy 型行走与振幅放大，读者已在 Grover 与振幅放大词条见过”$O(1/p)$ 次重复可被 $O(1/\sqrt{p})$ 次相干迭代替代”的机制），而是把它作为黑箱陈述，并把每个因子的含义讲清楚。

设一张规则图上有随机行走，满足：

• 均匀分布是行走的平稳分布（即”随机走很久之后”落在每个顶点的概率相同）；
• 行走的谱隙 (spectral gap) 为 $\delta$——粗略地说，$1/\delta$ 是行走”忘记起点、接近平稳分布”所需的步数尺度；
• 被标记的顶点在平稳分布下占比例 $ϵ$。

那么 Szegedy 型量子行走搜索用

$$O\left(\frac{1}{\sqrt{\delta ϵ}}\right)$$

步（每步一次 update 加一次 check）就能以 $\Omega (1)$ 概率落在一个标记顶点上；外加一次 setup 建立初始叠加。

为什么是 $\sqrt{\delta ϵ}$ 这个组合。直觉来自与 Grover 的类比：在 Grover 中，目标比例 $p=1/N$，需要 $O(1/\sqrt{p})$ 次迭代——这里 $ϵ$ 扮演的正是”目标在平稳分布中的比例”，开根号是振幅放大带来的二次加速。但量子行走不能像 Grover 那样每一步都”瞬移”到一个全新的均匀随机候选：它只能在图上走，而”模拟一次独立抽样”本质上要求行走先混合，代价由谱隙 $\delta$ 控制。两个因子相乘再开根号，就是量子行走为”局部移动”付出的相对代价。严谨的表述是把随机行走的转移矩阵量子化，在”标记/非标记”二维子空间内做振幅放大；我们只需要知道结论与每个因子的来源。

于是总查询数的通用形状是

$$Q=\underset{\text{setup}}{\underbrace{S}}+\underset{\text{行走步数}}{\underbrace{\frac{1}{\sqrt{\delta ϵ}}}}\cdot \underset{\text{每步 update}+\text{check}}{\underbrace{(U+C)}},$$

其中 $S,U,C$ 分别是 setup、update、check 的单次查询成本。对我们的问题，$S=r$、$U=O(1)$、$C=0$，所以剩下的工作只有两件：算出 $ϵ$，算出 $\delta$。

5. 标记比例 $ϵ$ 的精确推导

先分析最坏情形：整个输入中只有一个目标 $k$ 元集合

$$T=\{x_1^{\ast },\dots ,x_k^{\ast }\}.$$

唯一 witness 是最难的情形，也是最坏分析的标准假设（多 witness 的情形在本节末尾讨论）。

随机一个 $r$ 元子集 $S$ 被标记，当且仅当 $T\subset S$。计数：包含 $T$ 的 $r$ 元子集，相当于从剩下 $N-k$ 个元素中任选 $r-k$ 个补齐，共 $\left(\genfrac{}{}{0ex}{}{N-k}{r-k}\right)$ 个；$r$ 元子集总数为 $\left(\genfrac{}{}{0ex}{}{N}{r}\right)$。因此

$$ϵ=\frac{\left(\genfrac{}{}{0ex}{}{N-k}{r-k}\right)}{\left(\genfrac{}{}{0ex}{}{N}{r}\right)}.$$

把这个比值的阶算出来需要两步代数。第一步，把组合数展开成阶乘并约简：

$$ϵ=\frac{(N-k)!}{(r-k)!(N-r)!}\cdot \frac{r!(N-r)!}{N!}=\frac{r!}{(r-k)!}\cdot \frac{(N-k)!}{N!}.$$

第二步，把两个阶乘比分别写成下降阶乘的乘积。$r!/(r-k)!=r(r-1)\cdots (r-k+1)$ 是 $k$ 个因子的乘积，$N!/(N-k)!=N(N-1)\cdots (N-k+1)$ 同样是 $k$ 个因子的乘积，逐项配对得

$$ϵ=\prod _{j=0}^{k-1}\frac{r-j}{N-j}.$$

最后估计这个乘积的阶。因为 $k$ 是常数而 $r$ 将取为 $N$ 的幂（$r\ge 2k$ 且 $r\le N/2$），乘积中的每一项都满足

$$\frac{r}{2N}\le \frac{r-k}{N}\le \frac{r-j}{N-j}\le \frac{r}{N},$$

其中左端用了 $r-j\ge r-k\ge r/2$（因 $r\ge 2k$）与 $N-j\le N$，右端用了 $\frac{r-j}{N-j}\le \frac{r}{N}$（交叉相乘后等价于 $Nj\ge rj$，因 $r\le N$ 成立）。于是

$${\left(\frac{r}{2N}\right)}^k\le ϵ\le {\left(\frac{r}{N}\right)}^k⟹ϵ=\Theta \left({\left(\frac{r}{N}\right)}^k\right).$$

常数 $2^{-k}$ 被吸收进 $\Theta$，这正是”$k$ 为常数”这一假设在分析中的第一个用场。

直觉复述：要把某个特定的目标元素 $x_1^{\ast }$ 装进随机 $r$ 元子集，概率约为 $r/N$；$k$ 个目标元素大致独立地都要被装进去，所以概率约为 $(r/N{)}^k$。“大致独立”在大 $N$ 下是对的，上面的乘积推导是它的严格版本。

多 witness 的情形。如果有 $M$ 个近似不重叠（两两交集很小）的目标集合，每个都独立地贡献约 $(r/N{)}^k$ 的被标记概率，于是 $ϵ$ 约增大 $M$ 倍，行走步数相应缩小约 $\sqrt{M}$ 倍，搜索更快。上面的 $ϵ=\Theta ((r/N{)}^k)$ 是唯一 witness 的保守最坏界，模板的安全参数都按它取。

6. Johnson 图的谱隙 $\delta =\Theta (1/r)$

Johnson 图上的随机替换链这样走一步：从当前集合 $S$ 中均匀随机挑一个元素删去，再从补集中均匀随机挑一个元素加入。我们要它的谱隙。先给结论：Johnson 图的邻接结构（它是一个强正则图族）的谱可以精确算出来，随机替换链的谱隙为

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

完整的谱计算可以在 Ambainis 的论文（Zoo 7）中找到；这里给一个启发式推导，说明 $1/r$ 从何而来。

固定起始顶点 $S_0$，考察 $t$ 步之后当前集合与 $S_0$ 的重叠大小 $X_t=|S_t\cap S_0|$。初始 $X_0=r$；完全混合时，随机一个 $r$ 元子集与 $S_0$ 的期望重叠只有约 $r\cdot \frac{r}{N}=r^2/N$，当 $r\ll N$ 时几乎为 $0$。所以”重叠从 $r$ 衰减到接近 $0$“就是”忘记起点”的标志。每走一步，$S_0$ 中任何一个特定元素被删去的概率是 $1/r$（删谁均匀随机），而新加进来的元素恰好属于 $S_0$ 的概率约为 $r/N\ll 1$，近似可以忽略。于是每个”旧元素”每步以约 $1/r$ 的概率流失，重叠的期望值近似按

$$\mathbb{E}[X_{t+1}]\approx \left(1-\frac{1}{r}\right)\mathbb{E}[X_t]$$

衰减，$t$ 步后约为 $r(1-1/r{)}^t\approx r{e}^{-t/r}$。要让相关性衰减一个常数因子，需要 $t=\Theta (r)$ 步——混合时间的尺度是 $r$，谱隙是它的倒数尺度，即 $\delta =\Theta (1/r)$。

直觉复述：每步只能换掉一个位置，而工作集有 $r$ 个位置，所以”翻新整个集合”需要约 $r$ 步。$r$ 越大，行走越”粘”，这就是上一节所说”$r$ 太大则行走太慢”的定量来源。

注意 $ϵ$ 随 $r$ 增大而变好（标记变多），$\delta$ 随 $r$ 增大而变坏（混合变慢）——两股力量的对抗将在下一节决出最优的 $r$。

7. 行走步数与参数平衡：$N^{k/(k+1)}$ 的诞生

把第 5、6 节的结果代入第 4 节的框架。行走步数为

$$\frac{1}{\sqrt{\delta ϵ}}=\frac{1}{\sqrt{\Theta (1/r)\cdot \Theta ((r/N{)}^k)}}=\Theta \left(\sqrt{r\cdot \frac{N^k}{r^k}}\right)=\Theta \left(\frac{N^{k/2}}{r^{(k-1)/2}}\right).$$

逐项检查这个代数：根号内是 $r\cdot N^k/r^k=N^k/r^{k-1}$（$r$ 与 $r^k$ 约去一个 $r$），再开根号得 $N^{k/2}/r^{(k-1)/2}$。于是 Szegedy 搜索的 walk steps 为

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

加上每步 $O(1)$ 的 update 与零成本的 check，总查询数为

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

这个表达式里每个因子的来源都值得复述一遍：第一项 $r$ 是 setup——建立缓存必须付出的 $r$ 次查询，随 $r$ 线性增长；第二项是行走搜索，分子 $N^{k/2}$ 来自 $ϵ$ 中 $(r/N{)}^k$ 的 $N^k$ 开根号，分母 $r^{(k-1)/2}$ 是 $ϵ$ 中的 $r^k$ 与 $\delta$ 中的 $1/r$ 相乘后净剩的 $r^{k-1}$ 再开根号。

平衡求解。第一项随 $r$ 增、第二项随 $r$ 减，最优解在两项同阶处。令

$$r=\frac{N^{k/2}}{r^{(k-1)/2}}⟺r\cdot r^{(k-1)/2}=N^{k/2}⟺r^{(k+1)/2}=N^{k/2}.$$

两边同时取 $2/(k+1)$ 次幂：

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

代回任一项验证：setup 为 $r=N^{k/(k+1)}$；行走项为

$$\frac{N^{k/2}}{r^{(k-1)/2}}=\frac{N^{k/2}}{N^{\frac{k}{k+1}\cdot \frac{k-1}{2}}}=N^{\frac{k}{2}-\frac{k(k-1)}{2(k+1)}}=N^{\frac{k(k+1)-k(k-1)}{2(k+1)}}=N^{\frac{2k}{2(k+1)}}=N^{k/(k+1)},$$

两项确实同阶，因此

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

为什么平衡就是最优（而不仅是启发式）。把 $Q(r)$ 对 $r$ 求导（把 $r$ 当连续变量，这在大 $N$ 下无伤大雅）：

$$Q^{\prime }(r)=1-\frac{k-1}{2}\cdot \frac{N^{k/2}}{r^{(k+1)/2}}.$$

令 $Q^{\prime }(r)=0$ 得 $r^{(k+1)/2}=\frac{k-1}{2}{N}^{k/2}$，即 $r=(\frac{k-1}{2}{)}^{2/(k+1)}{N}^{k/(k+1)}$——与平衡解只相差一个依赖 $k$ 的常数因子，而 $k$ 是常数，所以 $r=\Theta (N^{k/(k+1)})$ 确实是最优点。且 $r\to 0$ 时第二项发散、$r\to N$ 时第一项发散，$Q^{\prime }(r)$ 由负变正，这是唯一的极小点。“两项同阶”在这里不只是口诀，而是被导数验证过的。

退化情形的自检。$k=1$ 给出 $r=N^{1/2}$、$Q=O(N^{1/2})$（Grover）；$k=2$ 给出 $r=N^{2/3}$、$Q=O(N^{2/3})$（element distinctness）。两个已知结果从同一个模板中掉出来，清楚地展示了这套机制的统一性：Grover 是”缓存大小为 $\sqrt{N}$ 的行走”，element distinctness 是”缓存大小为 $N^{2/3}$ 的行走”。

8. $k$-sum 的匹配下界

模板给出了上界，自然的问题是：这个指数还能改进吗？对 $k$-sum 这一具体实例，答案是否定的（在查询模型意义下）。

$k$-sum 问题：给定 $a_1,\dots ,a_N$（取自某个 Abel 群或值域），寻找 $k$ 个不同索引满足

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

它是 subset finding 框架的直接实例：$f(i)=a_i$，性质 $P$ 检查 $k$ 个已缓存的值之和，零额外查询，第 1 节的记账纪律自动满足。套用第 7 节，量子查询上界为 $O(N^{k/(k+1)})$。

Belovs 与 Špalek（Zoo 163）用 negative-weight adversary 方法给出了匹配的下界。adversary 方法的思想是把”任何量子查询算法都必须在输入对之间积累足够的区分度”转化为一个优化问题：为每一对输入 $(x,y)$ 设计一个权重矩阵，使得算法每做一次查询能推进的”进展”有上界，而总的必需进展有下界，两者相除就是查询数下界。经典（正权重）adversary 的进展度量受限于”一个位置的改变能影响多少”，常常给不出紧的界；负权重版本允许矩阵元取负值，进展度量更细，能精确捕捉 $k$-sum 中”必须同时凑齐 $k$ 个索引”的瓶颈。Belovs–Špalek 为 $k$-sum 显式构造了这样的负权重 adversary 矩阵，证明

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

与 Johnson 图行走的上界匹配。于是 $k$-sum 的量子查询复杂度被完全确定为 $\Theta (N^{k/(k+1)})$——通用模板至少在这个实例上是不可改进的。

保留条款（务必注意适用范围）：这个下界依赖两个假设。

• 值域/群足够大。下界构造需要值域大到能容纳 adversary 矩阵所需的输入结构；不能直接外推到任意小的模数。例如模一个小常数的 $k$-sum，输入结构完全不同，结论不再自动成立。
• $k$ 是固定常数。证明中的常数因子随 $k$ 变化；若 $k$ 随 $N$ 增长（例如 $k=\Theta (N)$），$\Theta$ 记号里被吃掉的因子可能变成主角，结论失效。

换言之，下界与上界一样，都是”固定 $k$、$N$ 增长”这一参数化下的结论。

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

名字相近的另一个问题必须区分开。量子子集和允许选取任意大小的子集，证书长度不固定，搜索空间是全部 $2^N$ 个子集；该问题是 NP 完全的，目前已知的最佳算法（无论经典还是量子）仍然是指数时间的，量子加速体现为指数底数的改善（如 representation technique 等技术）。

本词条的 subset finding 走的是另一条参数化路线：把 $k$ 当常数，证书大小固定，搜索空间只有 $\left(\genfrac{}{}{0ex}{}{N}{k}\right)=N^{O(1)}$，问题在 $P$ 中，复杂度是 $N$ 的多项式，量子加速体现为多项式指数的降低（从经典的 $\Theta (N)$ 降到 $N^{k/(k+1)}$）。

因此同名的 $k$-subset-sum 有两种参数化，结论完全不同：

• 固定 $k$、列表长度 $N$ 增长：本词条模板，$\Theta (N^{k/(k+1)})$ 量子查询；
• $k=\Theta (N)$ 或任意大小子集：NP 完全，指数时间算法与 representation technique。

读文献时务必先确认对方用的是哪一种参数化。

10. 图 clique 为何需要额外一层

最后用一个反例检验模板的边界，它也正好演示第 1 节那条记账纪律的作用。

设 $D$ 是某个图的顶点集，性质 $P$ 是”所选 $k$ 个点两两相邻，构成 $k$-clique”。粗看这是 subset finding 的直接实例：证书大小固定为 $k$。但问题出在检查环节：判定 $k$ 个顶点是否构成 clique，需要知道 $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ 条边的存在性，而顶点 oracle 查询一个顶点不会返回它与其他顶点的边信息——边信息来自另一个 edge oracle（“查询顶点对 $(u,v)$ 是否有边”）。

于是数据结构必须升级：$D(S)$ 除了缓存顶点，还必须缓存 $S$ 的诱导子图，即 $S$ 内部所有顶点对的边信息。三项成本全部重估：

• Setup：为 $r$ 个顶点查询全部 $\left(\genfrac{}{}{0ex}{}{r}{2}\right)=\Theta (r^2)$ 条内部边，setup 从 $r$ 变为 $\Theta (r^2)$；
• Update：换入一个新顶点后，要查询它与现有 $r-1$ 个顶点之间的全部边，update 从 $O(1)$ 变为 $\Theta (r)$；
• Check：诱导子图已在缓存中，检查任意 $k$ 元子集是否成团仍然零查询。

代入第 4 节的通用形状，行走步数不变（$ϵ$ 与 $\delta$ 只依赖图的组合结构），但每步贵了 $r$ 倍：

$$Q(r)=\Theta \left(r^2\right)+O\left(\frac{N^{k/2}}{r^{(k-1)/2}}\right)\cdot \Theta (r)=\Theta \left(r^2+\frac{N^{k/2}}{r^{(k-3)/2}}\right),$$

（$k\ge 3$；$k=3$ 时第二项中 $r$ 的幂次为 $0$，即行走成本与 $r$ 无关。）最优的 $r$ 和最终指数都随之改变，一般明显劣于”免费检查”模板的 $N^{k/(k+1)}$。Childs–Eisenberg 针对 clique 类问题给出了多种更精细的算法（包括嵌套行走等结构），其出发点正是绕开这份朴素的账单。

教训是通用的：只有当性质 $P$ 真能由已缓存的 $f(S)$ 数据免费判定时，$N^{k/(k+1)}$ 公式才直接适用。一旦检查环节暗藏新的 oracle 查询，setup/update/check 三项必须从头重算，结论也必须重算。

11. 小例子：3-sum 的完整演算

用一个可以全部手算的实例把模板过一遍。取 $k=3$，列表

$$(a_0,a_1,a_2,a_3,a_4)=(2,5,8,11,14),t=24.$$

第一步：找出全部 witness。$N=5$，三元子集共 $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 个，逐个求和：

$$\begin{array}{rlrl}& a_0+a_1+a_2=2+5+8=15,& & a_0+a_1+a_3=2+5+11=18,\\ & a_0+a_1+a_4=2+5+14=21,& & a_0+a_2+a_3=2+8+11=21,\\ & a_0+a_2+a_4=2+8+14=24,& & a_0+a_3+a_4=2+11+14=27,\\ & a_1+a_2+a_3=5+8+11=24\text{?}5+8+11=24,& & \\ & a_1+a_2+a_4=5+8+14=27,& & a_1+a_3+a_4=5+11+14=30,\\ & a_2+a_3+a_4=8+11+14=33.& & \end{array}$$

仔细核对：$a_0+a_2+a_4=2+8+14=24$ 命中；而 $a_1+a_2+a_3=5+8+11=24$ 也命中。所以这个实例其实有两个 witness：$\{0,2,4\}$ 与 $\{1,2,3\}$。（原例中最显眼的目标是 $\{0,2,4\}$，因为 $2+8+14=24$；把第二个也找出来，正好用来验证第 5 节”多 witness 使 $ϵ$ 增大”的论断。）

第二步：装配 Johnson 行走。取 $r=k=3$（这个小 $N$ 下渐近最优 $r=N^{3/4}$ 无意义，但 $r=3$ 让机制最透明）。$J(5,3)$ 有 $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 个顶点，每个顶点是一个三元索引集。被标记的顶点是那些包含某个 witness 的顶点；由于 $r=k=3$，“包含 witness”就是”等于 witness”，故标记顶点恰为 $\{0,2,4\}$ 与 $\{1,2,3\}$ 两个。

第三步：核对 $ϵ$。按第 5 节的公式，唯一 witness 时

$${ϵ}_{\text{单}}=\frac{\left(\genfrac{}{}{0ex}{}{5-3}{3-3}\right)}{\left(\genfrac{}{}{0ex}{}{5}{3}\right)}=\frac{1}{10},$$

与乘积形式 ${\prod }_{j=0}^2\frac{3-j}{5-j}=\frac{3}{5}\cdot \frac{2}{4}\cdot \frac{1}{3}=\frac{6}{60}=\frac{1}{10}$ 一致。实际有两个不重叠的 witness（$\{0,2,4\}\cap \{1,2,3\}=\{2\}$，近似不重叠），故真实标记比例为 $\frac{2}{10}=\frac{1}{5}$，恰为单 witness 的 $M=2$ 倍——第 5 节的论断在此精确成立。

第四步：走几步。谱隙 $\delta =\Theta (1/r)=\Theta (1/3)$。按 Szegedy 框架，步数尺度为

$$\frac{1}{\sqrt{\delta ϵ}}=\sqrt{\frac{3}{1/5}}=\sqrt{15}\approx 4$$

（取真实 $ϵ$），这在 $N=5$ 的尺度上没有渐近意义，但完整演示了”setup 一次、行走数步、每步只付一次新查询”的机制：setup 查询 $3$ 个值；一步移动（例如从 $\{0,2,4\}$ 到 $\{0,2,3\}$）删去索引 $4$、加入索引 $3$，只需新查询 $a_3=11$ 一次；检查缓存中是否存在三数之和为 $24$，零查询。

第五步：回到渐近。对大的 $N$ 与 $k=3$，模板给出 $r=N^{3/4}$，此时 setup 成本 $r=N^{3/4}$ 与行走成本

$$\frac{N^{3/2}}{r^{(3-1)/2}}=\frac{N^{3/2}}{r}=\frac{N^{3/2}}{N^{3/4}}=N^{3/4}$$

同阶，总查询 $O(N^{3/4})$。对照经典 $\Theta (N)$ 与朴素 Grover over 三元组的 $\Theta (N^{3/2})$，量子行走的优势一目了然。

12. 小结与习题

• 问题：固定 $k$ 元性质、可由已查询数据判定的 subset finding；经典 $\Theta (N)$，朴素 Grover over 子集 $\Theta (N^{k/2})$。
• 机制：Johnson 图 $J(N,r)$ 量子行走；状态缓存 $r$ 个 oracle 值；每步替换一个元素，update 为 $O(1)$ 次查询；标记条件可为任意固定大小性质。
• 两个关键量：唯一 $k$ 元 witness 的标记比例 $ϵ=\left(\genfrac{}{}{0ex}{}{N-k}{r-k}\right)/\left(\genfrac{}{}{0ex}{}{N}{r}\right)=\Theta ((r/N{)}^k)$；随机替换链谱隙 $\delta =\Theta (1/r)$。
• 平衡：setup $r$ 与行走 $N^{k/2}/r^{(k-1)/2}$ 在 $r=N^{k/(k+1)}$ 同阶，总查询 $O(N^{k/(k+1)})$；$k=1$ 退化为 Grover，$k=2$ 退化为 element distinctness。
• 匹配性：$k$-sum 的 negative-weight adversary 下界 $\Omega (N^{k/(k+1)})$ 与模板匹配（限于大值域、固定 $k$）。
• 纪律：property 检查若需额外 oracle，必须重算 setup/update/check，通用指数不再直接适用（clique 例）。

习题：

1.（推导）不引用第 5 节，从组合数定义出发，精确推导”随机 $r$ 元子集包含固定 $k$ 元集合 $T$“的概率，把它写成 ${\prod }_{j=0}^{k-1}\frac{r-j}{N-j}$，并给出 $\Theta ((r/N{)}^k)$ 成立的全部假设。 2.（平衡）对 $k=3$，写出总成本 $Q(r)=r+N^{3/2}/r$，分别用”两项同阶”与”求导”两种方法求最优 $r$，验证 $Q=O(N^{3/4})$；再用同一模板核对 $k=1$ 与 $k=2$ 退化为已知结果。 3.（多 witness）设存在 $M$ 个两两不相交的目标 $k$ 元集合。写出新的 $ϵ$，代入行走步数公式，说明总查询如何依赖 $M$；并讨论 witness 之间存在重叠时这个估计会发生什么变化。 4.（记账）为 clique 问题的 edge oracle 情形写出 setup 与 update 的查询成本，代入通用框架得到 $Q(r)=\Theta \left(r^2+N^{k/2}/r^{(k-3)/2}\right)$；对 $k=3$ 求出该朴素账单下的最优查询量，并解释它为何劣于 $N^{k/(k+1)}$ 模板。 5.（概念）解释为什么朴素 Grover over 所有 $k$ 元子集给出 $\Theta (N^{k/2})$，并指出量子行走省下的查询究竟来自哪一处机制上的差别。 6.（综合）某问题要求从 $N$ 个数中找 $k=4$ 个不同索引使其乘积等于给定值 $t$（值域足够大）。判断它是否属于本词条模板；若是，给出最优 $r$ 与总查询复杂度；并说明若把”乘积”改为”乘积模一个小素数 $p$“，哪些结论仍然成立、哪些需要重新审查。

参考文献

• Zoo 编号 162：Andrew Childs 与 Jason Eisenberg, Quantum Algorithms for Subset Finding.
• Zoo 编号 7：Andris Ambainis, Quantum Walk Algorithm for Element Distinctness.
• Zoo 编号 163：Aleksandrs Belovs 与 Robert Špalek, Adversary Lower Bound for the $k$-Sum Problem.

---

参考资料

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