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

形式陈述

取整数 $n\ge2$ 与有限非空字母表 $\Sigma$ 。输入 $x=(x_1,\ldots,x_n)\in\Sigma^n$ 由一次读取完整符号的 value oracle 给出；element distinctness 判定所有 $x_i$ 是否两两不同。对 $n\ge9$ 选整数 $2\le r<n/2$ ；更小规模可直接全读，不影响渐近界。使用 Johnson graph $J(n,r)$ ：vertex 是 $r$ 元子集 $R\subseteq[n]$ ，相邻 vertex 删除一个索引并加入一个新索引。状态 data 保存

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

每步以一半概率原地停留，否则均匀选择删除和加入的索引；这一 lazy Johnson walk 可逆、非周期且平稳分布均匀，其绝对谱隙为

\delta=\Theta(1/r).

可执行的 marked 判定是“存储的子集中存在任意一对相同值”，它不需要预先知道哪一对碰撞。分析非全异输入时，任选一对确实满足 $x_i=x_j$ 的不同位置；所有包含 $\{i,j\}$ 的子集都必然 marked。用子集计数可得这部分子集的平稳概率，因此取已知下界

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

于是整个 marked 集合的平稳质量至少为 $\varepsilon$ ，存在更多碰撞时未必取等。准备一个子集的 data 要查询 $r$ 个值，所以 $S=r$ 。相干更新保留旧顶点及其数据，将共享的 $r-1$ 个计算基值复制到新数据寄存器，只查询新加入的位置；逆操作清理新数据也只需常数次 oracle。复制的是已编码的基标签，操作在叠加上按线性性延拓。因此 MNRS 两个方向的更新都满足 $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=\lfloor n^{2/3}\rfloor$ （ $n\ge9$ 时落在上述范围），两项同阶，得到

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

Aaronson–Shi 的多项式下界先在大小为 $\Omega(n^2)$ 的值域给出 $\Omega(n^{2/3})$ ；Ambainis 的小值域转移定理将它扩展到每个 $|\Sigma|\ge n$ 。[1, Theorems 2.3、3.1] 因此在完整符号输入域与 $|\Sigma|\ge n$ 下，复杂度为 $\Theta(n^{2/3})$ ；这里只引用下界定理，不把上面的 walk 构造当作其证明。

直觉

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

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

元素互异性的量子查询算法：Johnson 图局部结构加成本平衡图 — 元素互异性的量子查询算法示意图

例子与边界

取 $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$ 。任意另加的 promise 即使同时有 yes/no 输入，也须重新核验难度。例如只许一个已知同值串和一个已知全异串时，检查一个两者值不同的位置便可区分，不能保留原来的 $n^{2/3}$ 下界。

若 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，§1.3 的 Johnson 链谱隙尺度与 Theorem 3 的完整搜索保证。
[1] Andris Ambainis, “Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range,” Theory of Computing 1, 2005, pp. 37–46，Theorem 2.3 的既有大值域下界与 Theorem 3.1 的对称性质转移。

形式陈述 ​

反向链接

形式陈述