量子游走查询算法

经典随机游走先花约 $1/\delta$ 步忘掉起点，再以约 $1/\epsilon$ 次机会碰到标记。量子版本对谱隙和标记质量都取平方根，但只在 update 与 check 可以相干、可逆地执行时成立。

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

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

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

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

若没有标记，$\epsilon$ 下界不成立，搜索过程不会凭空给无解证书；决策版本要规定超时并验证候选。若 $P$ 不可逆、stationary state 难制备或 update 丢弃旧 data，就不能直接套 MNRS。把链 lazy 化也会改变一步实现，公式中的 $\delta$ 必须按 lazy 后的链重算，不能沿用原链的 absolute gap。

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

量子 walk 适合状态之间高度重叠、单步只改少量数据的问题。Element distinctness公理库元素互异性的量子查询算法Element distinctness quantum query algorithm · Quantum element distinctness在 Johnson graph 上维护子集输入值，以 O(n^(2/3)) 次查询判定是否存在碰撞，并由下界证明最优。在 Johnson graph 上令一个 vertex 保存 $r$ 个输入值，从而以昂贵 setup 换取常数 update 和免费 query-check。

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