一般子集寻找：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 的区别

量子子集和允许选任意大小子集，搜索空间是 \(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 成本。

参考文献