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

在碰撞与元素唯一性一课中，我们解决了一个具体的搜索问题：给定 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)\) 次新查询，省下的查询预算换成"走得更慢但更便宜"的搜索。本课的目的就是把这句口号变成精确的复杂度账目。

本课知识点

  1. 问题模型与记账纪律——能写出 subset finding 的 oracle 模型与"性质 \(P\) 只读缓存、不许额外查询"的约定，并判断 \(k\)-sum、\(k\)-distinctness、clique 这类性质是否需要为检查 \(P\) 追加 oracle 查询。

  2. 从朴素 Grover 到图上行走——能算出对所有 \(k\) 元子集直接 Grover 的 \(\Theta(N^{k/2})\)，解释"把已查询数据留在状态里、每步只换一个元素"为何把每步新查询降到 \(O(1)\)，并说出标记稀疏与行走变慢两股力量的对抗。

  3. 行走状态与三项成本——能写出行走状态 \(|S\rangle\otimes|D(S)\rangle\) 与标记条件，并逐项核算 setup 为 \(r\) 次、update 为 \(O(1)\) 次、check 为 \(0\) 次查询。

  4. 量子行走搜索框架——能写出 Szegedy 型搜索的步数 \(O(1/\sqrt{\delta\epsilon})\) 与总查询形状 \(Q=S+\frac{1}{\sqrt{\delta\epsilon}}\cdot(U+C)\)，并说明 \(\epsilon\) 与 \(\delta\) 两个因子各自的来源。

  5. 标记比例 ε 的推导——能由组合计数导出 \(\epsilon=\binom{N-k}{r-k}/\binom{N}{r}=\Theta\!\left((r/N)^k\right)\)，并计算多 witness 情形下 \(\epsilon\) 与行走步数的变化。

  6. Johnson 图的谱隙——能用"重叠每步约衰减 \(1-1/r\)"的启发式论证推出 \(\delta=\Theta(1/r)\)，并解释 \(r\) 增大时 \(\epsilon\) 变好、\(\delta\) 变坏的对抗关系。

  7. 参数平衡与最优工作集——能把 \(\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 下界与模板边界——能陈述 negative-weight adversary 给出的 \(\Omega(N^{k/(k+1)})\) 下界及其两个假设，区分固定 \(k\) 与任意大小两种参数化，并说明 clique 类问题必须重算 setup/update/check。

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 零查询"的前提下成立。

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)}\)。

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 的说明一致。

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\)。

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 的保守最坏界，模板的安全参数都按它取。

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\)。

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}\) 的行走"。

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 的区别

名字相近的另一个问题必须区分开。量子子集和允许选取任意大小的子集，证书长度不固定，搜索空间是全部 \(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{split} \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} \end{split}\]

仔细核对：\(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 节）

  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 节）

  1. 基础：计算对所有 \(\binom{N}{k}\) 个 \(k\) 元子集直接 Grover 的查询数，代入 \(k=2\) 与 \(k=3\)，说明它分别与经典算法同阶、劣于本课模板。

  2. 进阶（概念）：解释为什么朴素 Grover over 所有 \(k\) 元子集给出 \(\Theta(N^{k/2})\)，并指出量子行走省下的查询究竟来自哪一处机制上的差别。

练习 3【行走状态与三项成本】（→ 3 节）

  1. 基础：写出 Johnson 图 \(J(N,r)\) 的顶点与相邻定义、行走状态 \(|S\rangle\otimes|D(S)\rangle\) 中缓存 \(D(S)\) 的内容，以及顶点"被标记"的精确条件。

  2. 进阶：解释 update 一步为何只需常数次查询——包括被删元素的旧函数值为何也要被可逆地擦除；并核算 setup、update、check 的查询次数分别为 \(r\)、\(O(1)\)、\(0\)。

提示：擦除旧值相当于一次"反查询"，仍是常数次操作。

练习 4【量子行走搜索框架】（→ 4 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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\) 无关；乘积模小素数时"值域足够大"的假设被破坏。

参考文献