元素互异性的量子查询算法

形式陈述

输入 $x=(x_1,\ldots,x_n)\in\Sigma^n$ 由 value oracle 给出；element distinctness 判定所有 $x_i$ 是否两两不同。渐近分析中选 $2\le r\le n/2$ ，使用 Johnson graph $J(n,r)$ ：vertex 是 $r$ 元子集 $R\subseteq[n]$ ，相邻 vertex 删除一个索引并加入一个新索引。状态 data 保存

\{(i,x_i):i\in R\}.

均匀 Johnson walk 可逆且平稳分布均匀，spectral gap 为

\delta=\Theta(1/r).

若输入至少含一对碰撞 $x_i=x_j$ ，把包含 $\{i,j\}$ 的子集标为 marked。一个随机 $r$ -子集包含该固定 pair 的概率恰为

\varepsilon =\frac{\binom{n-2}{r-2}}{\binom nr} =\frac{r(r-1)}{n(n-1)} =\Theta\!\left(\frac{r^2}{n^2}\right).

准备 data 要查询 $r$ 个值，所以 $S=r$ 。一步交换只需清理旧值并查询新值，oracle 次数为常数，故 $U=O(1)$ ；碰撞已在存储表中，可用免费本地计算检查，故查询成本 $C=0$ 。代入MNRS quantum walk bound：

S+\frac1{\sqrt\varepsilon} \left(\frac U{\sqrt\delta}+C\right) =O\!\left(r+\frac nr\sqrt r\right) =O\!\left(r+\frac n{\sqrt r}\right).

取 $r=\Theta(n^{2/3})$ ，两项同阶，得到

Q_2(\operatorname{ED}_n)=O(n^{2/3}).

Aaronson–Shi 的 polynomial lower bound 给 $\Omega(n^{2/3})$ ，因此在足够大值域的标准 oracle 模型中复杂度为 $\Theta(n^{2/3})$ 。

直觉

直接 Grover 搜索所有 $\binom n2$ 对，每次检查一对需两次值查询，只给 $O(n)$ 。Johnson walk 让相邻候选共享 $r-1$ 个已查询值：先为一个子集支付 $r$ ，此后每步只换一个值；谱隙与命中 collision pair 的概率共同决定最优平衡点。

这也是 data structure 进入 query algorithm 的典型方式。Check 为零不是比较免费到不存在，而是输入查询已经在 setup/update 中支付；对已存值的排序或哈希不计 query。

例子与边界

取 $n=27,r=9$ ，并假设只有坐标 $i,j$ 构成碰撞。随机 vertex 含这对的概率为

\varepsilon=\frac{9\cdot8}{27\cdot26} =\frac{4}{39}.

Johnson gap 为 $\Theta(1/9)$ ，所以 $1/\sqrt\delta=\Theta(3)$ ， $1/\sqrt\varepsilon=\sqrt{39}/2$ 。除常数外，walk 部分约为 $(\sqrt{39}/2)\cdot3$ 次 update，加 setup 的 $9$ 次查询；它与公式 $r+n/\sqrt r=9+9=18$ 同一常数量级。更多碰撞只会增大 marked mass，不会使这个最坏上界变差。

值域是实质边界。若 $|\Sigma|<n$ ，鸽巢原理保证不存在 all-distinct 输入，判定函数退化为常数， $\Omega(n^{2/3})$ 下界当然不成立；通常假设 $|\Sigma|\ge n$ 或给出同时包含 yes/no 实例的 promise。

若 oracle 一次返回整批值，或 update 不能相干清理旧值， $S,U$ 都会改变。查询上界也不声明 $O(n^{2/3})$ 的 classical memory；标准实现存 $r$ 个值，本地时间与空间需另行核算。

推论与应用

Johnson graph 模板还用于 $k$ -distinctness、子图碰撞和若干 subset finding 问题，但 marked mass、gap 与 check 成本会改变，不能只把 $r=n^{2/3}$ 原样复制。最优 $r$ 必须从新的三项成本重新平衡。

Element distinctness 同时校准了方法强度：正权 adversary 的 certificate barrier 只能到平方根，而 polynomial 或 tight general adversary 达到 $n^{2/3}$ ；上界的 Johnson walk 与下界证据在同一 oracle/promise 下才构成 tight result。

参考资料

Andris Ambainis, “Quantum Walk Algorithm for Element Distinctness,” SIAM Journal on Computing 37(1), 2007, pp. 210–239.
Scott Aaronson and Yaoyun Shi, “Quantum Lower Bounds for the Collision and the Element Distinctness Problems,” Journal of the ACM 51(4), 2004, pp. 595–605.
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha, “Search via Quantum Walk,” SIAM Journal on Computing 40(1), 2011, pp. 142–164.

形式陈述 ​

反向链接

形式陈述