量子游走查询算法 | Codeboy's Blog

形式陈述

设 $P$ 是至少含两个状态的有限集合 $\Omega$ 上不可约、非周期且可逆的Markov 链，平稳分布为 $\pi$ 。若原链尚未满足非周期条件，可换成 $(I+P)/2$ ；它保持平稳分布与可逆性，并把谱移入 $[0,1]$ 。以下的 $P$ 和谱隙始终指实际使用的链；已经满足条件的链不必再次 lazy 化。定义 absolute spectral gap

\delta=1-\max_{j\ge2}|\lambda_j(P)|>0.

标记集合为 $M\subseteq\Omega$ 。给定已知 $0<\varepsilon\le1$ ，承诺 $M$ 为空，或其平稳质量满足

\pi(M)=\sum_{u\in M}\pi(u)\ge\varepsilon.

记 $|u\rangle_d=|u,\operatorname{data}(u)\rangle$ ，并用 $|\bot\rangle_d$ 表示指定的空白状态。MNRS 在两个带数据的顶点寄存器上工作，将成本分成：

$S$ ：从空白制备 $\sum_u\sqrt{\pi(u)}|u\rangle_d|\bot\rangle_d$ 。
$U$ ：下述两个相干更新及各自逆操作的成本上界： $|u\rangle_d|\bot\rangle_d\longmapsto |u\rangle_d\sum_v\sqrt{P(u,v)}|v\rangle_d, \qquad |\bot\rangle_d|v\rangle_d\longmapsto \sum_u\sqrt{P^*(v,u)}|u\rangle_d|v\rangle_d.$ 这里 $P^*$ 为时间反向链；可逆时 $P^*=P$ 。操作须延拓为整个寄存器空间上的酉电路，不能用一次经典随机转移代替。
$C$ ：由带数据顶点相干判定是否标记并执行条件相位翻转的成本；测量后的候选验证也须在同一量级内完成。

相应双反射 walk 及其受控版本由这些已给出的更新电路、逆电路和空白态受控反射构成，成本为 $O(U)$ ，没有假设任意未知酉黑盒都可免费加控制。[1, §1.3、Proposition 2]

在硬查询计费下，MNRS Theorem 3 给出一个有限预算算法： $M$ 为空时返回无标记，非空时以正常数概率找到并验证一个 marked vertex。用常数次独立重复可将成功率提高到至少 $2/3$ ，总成本仍为

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

这个不带额外对数的界使用 MNRS 的递归稳健放大，而非直接重复一个固定误差的反射。相关不变空间中的量子 walk phase gap 为 $\Omega(\sqrt\delta)$ ；基于相位估计的检测可用 $O(\delta^{-1/2}\log(1/\eta))$ 次受控 walk／逆 walk，将 stationary-state 反射的误差控制在 $0<\eta<1/2$ 。

若把这个近似反射直接用于 $O(\varepsilon^{-1/2})$ 轮普通振幅放大，逐轮累积误差要求 $\eta=O(\sqrt\varepsilon)$ ，得到的是多一个 $\log(1/\varepsilon)$ 因子的简单版本（同文 Theorem 7）。上述 sharp bound 则引用 §4 的递归放大与分层误差安排；这里只说明其假设和成本，不把简单版本的论证当作消去对数的证明。

直觉

经典对应过程的谱隙控制去相关尺度，标记质量控制搜索机会。把任意起点混合到指定总变差精度通常还含平稳分布与误差的对数因子，不能直接把 $1/\delta$ 当作完整最坏混合时间。量子版本对谱隙和标记质量都取平方根，但只在 update 与 check 可以相干、可逆地执行时成立。

三个成本分开至关重要。某些问题准备一个带数据的 vertex 很贵，却每次换一个坐标很便宜；另一些问题检查标记本身需要多次 oracle。只报“走了多少步”会漏掉真正的输入访问。

例子与边界

用 complete mixing chain 校准公式。取 $N\ge2$ ，令 $\Omega=[N]$ ，从任意状态下一步均匀跳到所有顶点，故 $\pi$ 均匀，特征值为 $1,0,\ldots,0$ ， $\delta=1$ 。若恰有一个标记点，则 $\varepsilon=1/N$ 。

均匀 stationary state 与 walk update 都与输入无关，可按查询口径取 $S=U=0$ ；检查当前顶点是否标记需一次 phase query，故 $C=1$ 。代入得到

O\!\left(\sqrt N\right),

恰退化为 Grover 搜索尺度。若 $N=4$ ，公式中的放大量级为 $1/\sqrt{1/4}=2$ 次 check；具体反射角可进一步把常数优化，但参数账已经逐项对上。

无标记输入也在“空集或质量至少 $\varepsilon$ ”的承诺内：算法按有限日程结束，且不会验证出不存在的标记。但非空时仍可能漏检，所以一次“无标记”输出不是确定的不存在证明。单状态链无需谱隙公式，直接检查唯一状态即可。若 $P$ 不可逆、stationary state 难制备或 update 丢弃旧 data，就不能直接套 MNRS。把链 lazy 化也会改变一步实现，公式中的 $\delta$ 必须按 lazy 后的链重算，不能沿用原链的 absolute gap。

查询界不等于时间或空间界。Check 在查询模型中可能是 $C=0$ ，因为所有值已存于 data；维护、排序或比较这些值仍可能耗费大量本地门和 memory。

推论与应用

量子 walk 适合状态之间高度重叠、单步只改少量数据的问题。Element distinctness在 Johnson graph 上令一个 vertex 保存 $r$ 个输入值，从而以昂贵 setup 换取常数 update 和免费 query-check。

设计时先选 classical chain 并计算 $\pi(M)$ 与 $\delta$ ，再给 coherent data structure 的 $S,U,C$ 。少任一项都不足以得到查询上界；尤其不能用 classical mixing time 的经验值替代可证明 spectral gap。

参考资料

Mario Szegedy, “Quantum Speed-Up of Markov Chain Based Algorithms,” Proceedings of FOCS 2004, pp. 32–41.
[1] 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 的两寄存器数据更新、Theorem 3 的最终成本、Theorem 7 的简单对数版本及 §4 的递归稳健放大。
Andris Ambainis, “Quantum Walk Algorithm for Element Distinctness,” SIAM Journal on Computing 37(1), 2007, pp. 210–239.

形式陈述 ​

反向链接

形式陈述