# 一般子集寻找：Johnson 图量子行走的 $N^{k/(k+1)}$ 模板 在[碰撞与元素唯一性](collision-element-distinctness.md)一课中，我们解决了一个具体的搜索问题：给定 oracle $f:[N]\to[M]$，找两个索引 $i\neq j$ 使 $f(i)=f(j)$。Element distinctness 只是在找一对满足"函数值相同"的索引。本课把这一问题推广到它的一般形态。 **Subset finding 问题**：给定 oracle $f:D\to R$ 和一个**固定的 $k$ 元性质** $P$（$k$ 是与 $N$ 无关的常数），要求找出一个 $k$ 元子集 $$ \{x_1,\ldots,x_k\}\subset D $$ 使得 $$ \big((x_1,f(x_1)),\ldots,(x_k,f(x_k))\big)\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$ 元子集共有 $\binom{N}{k}=\Theta(N^k)$ 个（$k$ 为常数），Grover 需要 $$ \Theta\!\left(\sqrt{\tbinom{N}{k}}\right)=\Theta\!\left(N^{k/2}\right) $$ 次查询。$k=2$ 时这是 $\Theta(N)$，与经典完全一样，**毫无优势**。$k$ 越大，这个朴素指数 $k/2$ 越糟。 问题的根源在于：Grover 的每一步都要从头构造一个候选 $k$ 元子集，查询它的全部 $k$ 个函数值，然后丢弃。相邻两次迭代之间没有任何信息被保留。量子行走的核心思想是**把已查询的数据留在状态里**：让候选集合每次只变化一个元素，这样每步只需 $O(1)$ 次新查询，省下的查询预算换成"走得更慢但更便宜"的搜索。本课的目的就是把这句口号变成精确的复杂度账目。 :::{admonition} 本课知识点 :class: tip 1. **[问题模型与记账纪律](#problem-model)**——能写出 subset finding 的 oracle 模型与"性质 $P$ 只读缓存、不许额外查询"的约定，并判断 $k$-sum、$k$-distinctness、clique 这类性质是否需要为检查 $P$ 追加 oracle 查询。 2. **[从朴素 Grover 到图上行走](#walk-intuition)**——能算出对所有 $k$ 元子集直接 Grover 的 $\Theta(N^{k/2})$，解释"把已查询数据留在状态里、每步只换一个元素"为何把每步新查询降到 $O(1)$，并说出标记稀疏与行走变慢两股力量的对抗。 3. **[行走状态与三项成本](#walk-state-costs)**——能写出行走状态 $|S\rangle\otimes|D(S)\rangle$ 与标记条件，并逐项核算 setup 为 $r$ 次、update 为 $O(1)$ 次、check 为 $0$ 次查询。 4. **[量子行走搜索框架](#walk-search-framework-subset-finding)**——能写出 Szegedy 型搜索的步数 $O(1/\sqrt{\delta\epsilon})$ 与总查询形状 $Q=S+\frac{1}{\sqrt{\delta\epsilon}}\cdot(U+C)$，并说明 $\epsilon$ 与 $\delta$ 两个因子各自的来源。 5. **[标记比例 ε 的推导](#marking-ratio)**——能由组合计数导出 $\epsilon=\binom{N-k}{r-k}/\binom{N}{r}=\Theta\!\left((r/N)^k\right)$，并计算多 witness 情形下 $\epsilon$ 与行走步数的变化。 6. **[Johnson 图的谱隙](#johnson-spectral-gap-subset-finding)**——能用"重叠每步约衰减 $1-1/r$"的启发式论证推出 $\delta=\Theta(1/r)$，并解释 $r$ 增大时 $\epsilon$ 变好、$\delta$ 变坏的对抗关系。 7. **[参数平衡与最优工作集](#parameter-balancing)**——能把 $\epsilon$、$\delta$ 代入框架得到 $Q(r)=O\!\left(r+N^{k/2}/r^{(k-1)/2}\right)$，用两项同阶与求导两种方式解出 $r=N^{k/(k+1)}$，并核对 $k=1,2$ 的退化情形。 8. **[k-sum 下界与模板边界](#ksum-lower-bound)**——能陈述 negative-weight adversary 给出的 $\Omega(N^{k/(k+1)})$ 下界及其两个假设，区分固定 $k$ 与任意大小两种参数化，并说明 clique 类问题必须重算 setup/update/check。 ::: (problem-model)= ## 1. 问题模型与 property oracle 先固定记号。令 $N=|D|$，$k$ 为常数。算法通过标准 XOR oracle 访问 $f$： $$ O_f|x,z\rangle=|x,\;z\oplus f(x)\rangle. $$ 我们按**查询复杂度 (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 零查询"的前提下成立。 (walk-intuition)= ## 2. 核心直觉：把搜索变成图上的行走 在形式化之前，先用平实语言说清楚算法为什么是对的。 搜索的困难在于"候选太多、每个候选的验证太贵"。Grover 每次从头掷一个全新的 $k$ 元子集，验证它要花 $k$ 次查询，验证完就扔掉。量子行走换一种玩法：维护一个大小为 $r$ 的**工作集** $S$（$r\ge k$ 是一个待选参数），把它连同其中所有元素的函数值一起缓存。如果 $S$ 里已经藏着某个满足 $P$ 的 $k$ 元子集，我们就成功了——这样的 $S$ 称为**被标记的 (marked)**。 接下来不再是"掷新候选"，而是"**走动**"：每一步从 $S$ 中删掉一个元素、加入一个新元素。因为旧数据都在缓存里，这一步只需要查询**一个新元素**的函数值——$O(1)$ 次查询，而不是 $k$ 次。所有可能的工作集连同"删一添一"的相邻关系构成一张图，这就是 **Johnson 图 $J(N,r)$**；算法就是在这张图上做量子版本的随机行走搜索，希望尽快走到一个被标记的顶点上。 这个图景里有两股相互竞争的力量，理解它们就理解了整个复杂度分析： - **标记顶点太稀少**。随机一个 $r$ 元子集恰好包含目标 $k$ 元子集的概率 $\epsilon$ 大约是 $(r/N)^k$。$r$ 取得越大，标记比例越高，搜索越容易。 - **图越来越难走**。工作集越大，每一步只能换一个元素，要让状态"忘记"起点、混合到全图上，需要的步数就越多；反映在谱隙上，$\delta=\Theta(1/r)$，$r$ 越大谱隙越小，行走越慢。 量子行走搜索的步数由乘积 $\delta\epsilon$ 控制（第 4 节给出框架），于是我们面对一个经典的参数平衡问题：$r$ 太小则标记太稀，$r$ 太大则行走太慢且初始缓存太贵。第 5 节会展示最优的 $r$ 恰好让"初始建缓存的成本"与"行走搜索的成本"同阶，而平衡点是 $r=N^{k/(k+1)}$。 (walk-state-costs)= ## 3. 行走状态与标记条件 现在把上一节的图景形式化。选择参数 $r\ge k$，在 Johnson 图 $J(N,r)$ 上行走。图的每个顶点是一个 $r$ 元子集 $S\subset D$；两个顶点相邻当且仅当它们恰好在**一个元素**上不同，即存在 $x\in S$、$x'\notin S$ 使 $S'=S\setminus\{x\}\cup\{x'\}$。 算法为每个顶点维护缓存 $$ D(S)=\{(x,f(x)):x\in S\}, $$ 即 $S$ 中每个元素及其函数值的列表，存放在合适的数据结构中（排序数组、哈希表等）。行走状态因此是形如 $|S\rangle\otimes|D(S)\rangle$ 的叠加。 **标记条件**：若 $S$ 内存在某个 $k$ 元子集 $\{x_1,\ldots,x_k\}\subset S$ 使 $\big((x_1,f(x_1)),\ldots,(x_k,f(x_k))\big)\in P$，就标记 $S$。注意这个判定只读取 $D(S)$ 中已存的数据，符合第 1 节对 property oracle 的约定。 三项成本分别核算： - **Setup（初始建立）**：制备所有 $r$ 元子集的均匀叠加，并为每个 $S$ 查询其中全部 $r$ 个函数值以建立 $D(S)$。这需要 $r$ 次查询，一次付清。 - **Update（走一步）**：从 $S$ 走到相邻的 $S'$ 时，只有一个元素被替换。新元素的函数值需要 $1$ 次新查询（实际上还要把被删元素的旧值可逆地擦除，这是常数次额外操作和一次"反查询"，不改变量级），故 update 是常数次查询。 - **Check（判定标记）**：只读取 $D(S)$。在有合适的哈希/索引结构时，例如判 $k$-distinctness 只需在按值哈希的表中查找，判 $k$-sum 可以在排序缓存上查找补数，都不需要新的 oracle 调用，故 check 为 $0$ 次查询。 查询模型把数据结构操作视为免费；真实电路中要在叠加的 $S$ 上可逆地维护 $D(S)$，需要可逆哈希、radix tree 等技术把 update/check 压到 polylog 时间开销。本课的 $O(\cdot)$ 结论都是**查询复杂度**结论，这一点与上一课对 element distinctness 的说明一致。 (walk-search-framework-subset-finding)= ## 4. 量子行走搜索框架：步数由 $\delta\epsilon$ 控制 我们不重新推导量子行走搜索定理（其细节属于 Szegedy 型行走与振幅放大，读者已在 Grover 与振幅放大一课见过"$O(1/p)$ 次重复可被 $O(1/\sqrt{p})$ 次相干迭代替代"的机制），而是把它作为黑箱陈述，并把每个因子的含义讲清楚。 设一张规则图上有随机行走，满足： - 均匀分布是行走的平稳分布（即"随机走很久之后"落在每个顶点的概率相同）； - 行走的**谱隙 (spectral gap)** 为 $\delta$——粗略地说，$1/\delta$ 是行走"忘记起点、接近平稳分布"所需的步数尺度； - 被标记的顶点在平稳分布下占比例 $\epsilon$。 那么 Szegedy 型量子行走搜索用 $$ O\!\left(\frac{1}{\sqrt{\delta\,\epsilon}}\right) $$ 步（每步一次 update 加一次 check）就能以 $\Omega(1)$ 概率落在一个标记顶点上；外加一次 setup 建立初始叠加。 **为什么是 $\sqrt{\delta\epsilon}$ 这个组合**。直觉来自与 Grover 的类比：在 Grover 中，目标比例 $p=1/N$，需要 $O(1/\sqrt{p})$ 次迭代——这里 $\epsilon$ 扮演的正是"目标在平稳分布中的比例"，开根号是振幅放大带来的二次加速。但量子行走不能像 Grover 那样每一步都"瞬移"到一个全新的均匀随机候选：它只能在图上走，而"模拟一次独立抽样"本质上要求行走先混合，代价由谱隙 $\delta$ 控制。两个因子相乘再开根号，就是量子行走为"局部移动"付出的相对代价。严谨的表述是把随机行走的转移矩阵量子化，在"标记/非标记"二维子空间内做振幅放大；我们只需要知道结论与每个因子的来源。 于是总查询数的通用形状是 $$ Q=\underbrace{S}_{\text{setup}}+\underbrace{\frac{1}{\sqrt{\delta\epsilon}}}_{\text{行走步数}}\cdot\underbrace{(U+C)}_{\text{每步 update}+\text{check}}, $$ 其中 $S,U,C$ 分别是 setup、update、check 的单次查询成本。对我们的问题，$S=r$、$U=O(1)$、$C=0$，所以剩下的工作只有两件：算出 $\epsilon$，算出 $\delta$。 (marking-ratio)= ## 5. 标记比例 $\epsilon$ 的精确推导 先分析最坏情形：整个输入中**只有一个**目标 $k$ 元集合 $$ T=\{x_1^*,\ldots,x_k^*\}. $$ 唯一 witness 是最难的情形，也是最坏分析的标准假设（多 witness 的情形在本节末尾讨论）。 随机一个 $r$ 元子集 $S$ 被标记，当且仅当 $T\subset S$。计数：包含 $T$ 的 $r$ 元子集，相当于从剩下 $N-k$ 个元素中任选 $r-k$ 个补齐，共 $\binom{N-k}{r-k}$ 个；$r$ 元子集总数为 $\binom{N}{r}$。因此 $$ \epsilon=\frac{\binom{N-k}{r-k}}{\binom{N}{r}}. $$ 把这个比值的阶算出来需要两步代数。第一步，把组合数展开成阶乘并约简： $$ \epsilon =\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$ 个因子的乘积，逐项配对得 $$ \epsilon=\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\epsilon\le\left(\frac{r}{N}\right)^k \quad\Longrightarrow\quad \epsilon=\Theta\!\left(\left(\frac{r}{N}\right)^k\right). $$ 常数 $2^{-k}$ 被吸收进 $\Theta$，这正是"$k$ 为常数"这一假设在分析中的第一个用场。 **直觉复述**：要把某个特定的目标元素 $x_1^*$ 装进随机 $r$ 元子集，概率约为 $r/N$；$k$ 个目标元素大致独立地都要被装进去，所以概率约为 $(r/N)^k$。"大致独立"在大 $N$ 下是对的，上面的乘积推导是它的严格版本。 **多 witness 的情形**。如果有 $M$ 个近似不重叠（两两交集很小）的目标集合，每个都独立地贡献约 $(r/N)^k$ 的被标记概率，于是 $\epsilon$ 约增大 $M$ 倍，行走步数相应缩小约 $\sqrt{M}$ 倍，搜索更快。上面的 $\epsilon=\Theta((r/N)^k)$ 是唯一 witness 的保守最坏界，模板的安全参数都按它取。 (johnson-spectral-gap-subset-finding)= ## 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-\frac1r\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$ 太大则行走太慢"的定量来源。 注意 $\epsilon$ 随 $r$ 增大而**变好**（标记变多），$\delta$ 随 $r$ 增大而**变坏**（混合变慢）——两股力量的对抗将在下一节决出最优的 $r$。 (parameter-balancing)= ## 7. 行走步数与参数平衡：$N^{k/(k+1)}$ 的诞生 把第 5、6 节的结果代入第 4 节的框架。行走步数为 $$ \frac{1}{\sqrt{\delta\epsilon}} =\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\epsilon}}\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}$ 来自 $\epsilon$ 中 $(r/N)^k$ 的 $N^k$ 开根号，分母 $r^{(k-1)/2}$ 是 $\epsilon$ 中的 $r^k$ 与 $\delta$ 中的 $1/r$ 相乘后净剩的 $r^{k-1}$ 再开根号。 **平衡求解**。第一项随 $r$ 增、第二项随 $r$ 减，最优解在两项同阶处。令 $$ r=\frac{N^{k/2}}{r^{(k-1)/2}} \quad\Longleftrightarrow\quad r\cdot r^{(k-1)/2}=N^{k/2} \quad\Longleftrightarrow\quad 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'(r)=1-\frac{k-1}{2}\cdot\frac{N^{k/2}}{r^{(k+1)/2}}. $$ 令 $Q'(r)=0$ 得 $r^{(k+1)/2}=\frac{k-1}{2}N^{k/2}$，即 $r=\big(\frac{k-1}{2}\big)^{2/(k+1)}N^{k/(k+1)}$——与平衡解只相差一个依赖 $k$ 的常数因子，而 $k$ 是常数，所以 $r=\Theta(N^{k/(k+1)})$ 确实是最优点。且 $r\to 0$ 时第二项发散、$r\to N$ 时第一项发散，$Q'(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}$ 的行走"。 (ksum-lower-bound)= ## 8. $k$-sum 的匹配下界 模板给出了上界，自然的问题是：这个指数还能改进吗？对 $k$-sum 这一具体实例，答案是否定的（在查询模型意义下）。 $k$-sum 问题：给定 $a_1,\ldots,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 的区别 名字相近的另一个问题必须区分开。[量子子集和](../ch09-algebra-number-theory/quantum-subset-sum.md)允许选取**任意大小**的子集，证书长度不固定，搜索空间是全部 $2^N$ 个子集；该问题是 NP 完全的，目前已知的最佳算法（无论经典还是量子）仍然是指数时间的，量子加速体现为指数底数的改善（如 representation technique 等技术）。 本课的 subset finding 走的是另一条参数化路线：把 $k$ 当常数，证书大小固定，搜索空间只有 $\binom{N}{k}=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，需要知道 $\binom{k}{2}$ 条边的存在性，而**顶点 oracle 查询一个顶点不会返回它与其他顶点的边信息**——边信息来自另一个 edge oracle（"查询顶点对 $(u,v)$ 是否有边"）。 于是数据结构必须升级：$D(S)$ 除了缓存顶点，还必须缓存 $S$ 的**诱导子图**，即 $S$ 内部所有顶点对的边信息。三项成本全部重估： - **Setup**：为 $r$ 个顶点查询全部 $\binom{r}{2}=\Theta(r^2)$ 条内部边，setup 从 $r$ 变为 $\Theta(r^2)$； - **Update**：换入一个新顶点后，要查询它与现有 $r-1$ 个顶点之间的全部边，update 从 $O(1)$ 变为 $\Theta(r)$； - **Check**：诱导子图已在缓存中，检查任意 $k$ 元子集是否成团仍然零查询。 代入第 4 节的通用形状，行走步数不变（$\epsilon$ 与 $\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),\qquad t=24. $$ **第一步：找出全部 witness**。$N=5$，三元子集共 $\binom{5}{3}=10$ 个，逐个求和： $$ \begin{aligned} &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=\mathbf{24}, &&a_0+a_3+a_4=2+11+14=27,\\ &a_1+a_2+a_3=5+8+11=24\ \text{?}\quad 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{aligned} $$ 仔细核对：$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 使 $\epsilon$ 增大"的论断。） **第二步：装配 Johnson 行走**。取 $r=k=3$（这个小 $N$ 下渐近最优 $r=N^{3/4}$ 无意义，但 $r=3$ 让机制最透明）。$J(5,3)$ 有 $\binom{5}{3}=10$ 个顶点，每个顶点是一个三元索引集。被标记的顶点是那些包含某个 witness 的顶点；由于 $r=k=3$，"包含 witness"就是"等于 witness"，故标记顶点恰为 $\{0,2,4\}$ 与 $\{1,2,3\}$ 两个。 **第三步：核对 $\epsilon$**。按第 5 节的公式，唯一 witness 时 $$ \epsilon_{\text{单}}=\frac{\binom{5-3}{3-3}}{\binom{5}{3}}=\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\epsilon}}=\sqrt{\frac{3}{1/5}}=\sqrt{15}\approx 4 $$ （取真实 $\epsilon$），这在 $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 的标记比例 $\epsilon=\binom{N-k}{r-k}/\binom{N}{r}=\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【问题模型与记账纪律】**（→ [1 节](#problem-model)） 1. 基础：写出 subset finding 的输入（oracle $f$ 与固定 $k$ 元性质 $P$）与证书的形式，并分别给出 $k$-sum 与 $k$-distinctness 的性质 $P$ 的显式条件。 2. 进阶：对 $k$-sum、$k$-distinctness 与"$k$ 个顶点两两相邻"三类性质，逐一判断能否只靠已缓存的 $(x,f(x))$ 数据零额外查询地判定；对不能的，指出缺的信息来自哪个 oracle、按第 1 节的记账纪律应如何处理。 > 提示：顶点 oracle 不返回边信息，边的存在性要靠另一个 edge oracle。 **练习 2【从朴素 Grover 到图上行走】**（→ [2 节](#walk-intuition)） 1. 基础：计算对所有 $\binom{N}{k}$ 个 $k$ 元子集直接 Grover 的查询数，代入 $k=2$ 与 $k=3$，说明它分别与经典算法同阶、劣于本课模板。 2. 进阶（概念）：解释为什么朴素 Grover over 所有 $k$ 元子集给出 $\Theta(N^{k/2})$，并指出量子行走省下的查询究竟来自哪一处机制上的差别。 **练习 3【行走状态与三项成本】**（→ [3 节](#walk-state-costs)） 1. 基础：写出 Johnson 图 $J(N,r)$ 的顶点与相邻定义、行走状态 $|S\rangle\otimes|D(S)\rangle$ 中缓存 $D(S)$ 的内容，以及顶点"被标记"的精确条件。 2. 进阶：解释 update 一步为何只需常数次查询——包括被删元素的旧函数值为何也要被可逆地擦除；并核算 setup、update、check 的查询次数分别为 $r$、$O(1)$、$0$。 > 提示：擦除旧值相当于一次"反查询"，仍是常数次操作。 **练习 4【量子行走搜索框架】**（→ [4 节](#walk-search-framework-subset-finding)） 1. 基础：写出 Szegedy 型搜索的步数 $O\!\left(1/\sqrt{\delta\epsilon}\right)$ 与总查询 $Q=S+\frac{1}{\sqrt{\delta\epsilon}}\cdot(U+C)$，并说明 $S$、$U$、$C$ 各对应哪一项操作。 2. 进阶：与 Grover 的 $O(1/\sqrt{p})$ 类比，解释 $\epsilon$ 为何被开方、行走为何还要额外付出一个由谱隙 $\delta$ 控制的混合代价。 **练习 5【标记比例 ε 的推导】**（→ [5 节](#marking-ratio)） 1. 基础：取 $N=10$、$r=4$、$k=2$，分别用比值 $\binom{N-k}{r-k}/\binom{N}{r}$ 与乘积 $\prod_{j=0}^{k-1}\frac{r-j}{N-j}$ 计算 $\epsilon$，并与近似 $(r/N)^k$ 比较大小。 2. 进阶（推导）：不引用第 5 节，从组合数定义出发，精确推导"随机 $r$ 元子集包含固定 $k$ 元集合 $T$"的概率，把它写成 $\prod_{j=0}^{k-1}\frac{r-j}{N-j}$，并给出 $\Theta((r/N)^k)$ 成立的全部假设。 3. 进阶（多 witness）：设存在 $M$ 个两两不相交的目标 $k$ 元集合。写出新的 $\epsilon$，代入行走步数公式，说明总查询如何依赖 $M$；并讨论 witness 之间存在重叠时这个估计会发生什么变化。 > 提示：不重叠时各 witness 的标记事件近乎互斥，概率近似相加；有重叠时需要容斥。 **练习 6【Johnson 图的谱隙】**（→ [6 节](#johnson-spectral-gap-subset-finding)） 1. 基础：复述启发式论证的两个概率依据——$S_0$ 中每个元素每步以约 $1/r$ 的概率被删去、新加入元素落入 $S_0$ 的概率约 $r/N$ 可忽略——并由 $\mathbb{E}[X_{t+1}]\approx(1-1/r)\mathbb{E}[X_t]$ 推出混合时间 $\Theta(r)$ 与 $\delta=\Theta(1/r)$。 2. 进阶：设 $r$ 从 $N^{1/2}$ 增大到 $N^{2/3}$（即 $k=1$ 与 $k=2$ 的最优值），计算 $\delta$ 与混合时间各变化多少；并解释为什么 $\epsilon$ 随 $r$ 变好、$\delta$ 随 $r$ 变坏必然导致一个折中的最优 $r$。 **练习 7【参数平衡与最优工作集】**（→ [7 节](#parameter-balancing)） 1. 基础：把 $\delta=\Theta(1/r)$ 与 $\epsilon=\Theta((r/N)^k)$ 代入第 4 节的框架，逐步化简出行走步数 $\Theta\!\left(N^{k/2}/r^{(k-1)/2}\right)$ 与总查询 $Q(r)=O\!\left(r+N^{k/2}/r^{(k-1)/2}\right)$。 2. 基础：取 $N=16$，对 $k=1$ 与 $k=3$ 分别算出最优的 $r=N^{k/(k+1)}$ 与总查询量级，并验证 setup 项与行走项同阶。 3. 进阶（平衡）：对 $k=3$，写出总成本 $Q(r)=r+N^{3/2}/r$，分别用"两项同阶"与"求导"两种方法求最优 $r$，验证 $Q=O(N^{3/4})$；再用同一模板核对 $k=1$ 与 $k=2$ 退化为已知结果。 > 提示：求导得 $Q'(r)=1-\frac{k-1}{2}\cdot\frac{N^{k/2}}{r^{(k+1)/2}}$，极小点与平衡解只差依赖 $k$ 的常数因子。 **练习 8【k-sum 下界与模板边界】**（→ [8 节](#ksum-lower-bound)） 1. 基础：写出 $k$-sum 的量子查询复杂度，注明上界与下界分别来自哪一节的方法，并列出下界依赖的两个假设；再用一两句话区分固定 $k$ 与任意大小两种参数化的结论差异。 2. 进阶（记账）：为 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)}$ 模板。 3. 进阶（综合）：某问题要求从 $N$ 个数中找 $k=4$ 个不同索引使其乘积等于给定值 $t$（值域足够大）。判断它是否属于本课模板；若是，给出最优 $r$ 与总查询复杂度；并说明若把"乘积"改为"乘积模一个小素数 $p$"，哪些结论仍然成立、哪些需要重新审查。 > 提示：$k=3$ 的 clique 账单中行走项与 $r$ 无关；乘积模小素数时"值域足够大"的假设被破坏。 ## 参考文献 - 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).