离散时间量子游走

Posted on 2026-11-02 Edited on 2026-11-04 Word count in article: 6.6k Reading time ≈ 24 mins.

Abstract. 本文收录于合集（量子计算文章选读）。这篇文章爬了 21 世纪初对离散时间量子游走的研究线，形成了一套对于这个算法框架的动机比较充分、直觉比较清楚的理解。

经典随机游走
- 基本性质
- 用随机游走解决搜索问题
量子随机游走
元素区分问题
参考文献

经典随机游走

基本性质

众所周知，一个支撑在 $N$ 个点图 $G = (V, E)$ 上的随机游走可以用一个随机矩阵 $P$ 刻画：$P_{ij}$ 表示每一步从 $j$ 到 $i$ 的转移概率，其中对于任意 $j$ 都有 $\sum_{k = 1}^N P_{kj} = 1$，且 $P_{ij}\ne 0$ 当且仅当 $(i, j)\in E$。给定任意一个支撑在该 $N$ 个点上的初始分布 $\pi$，经过一次转移之后分布将变成 $P\pi$。一个随机游走可以具有以下性质：

定义 1.1. 称一个由 $P$ 刻画的随机游走具有：

不可约性. 若 $G$ 强连通。
非周期性. 若 $G$ 中所有圈长度的最大公约数为 $1$。
遍历性. 若它同时具有不可约性和非周期性。

Perron-Frobenius 定理的概率版本告诉我们，任意一个遍历性的随机游走都有唯一的稳态分布 $\pi$。我们继续定义一个遍历性随机游走的可逆性：

定义 1.2. 称一个由 $P$ 刻画的随机游走是可逆的，若对于它是遍历性的，并且任意的 $i, j$ 都有

$$
\pi_{i}P_{ji} = \pi_j P_{ij},
$$

其中 $\pi$ 是以上随机游走的稳态分布，以上条件称为细致平衡条件。

直觉上，这个性质就是在稳态分布下，从 $i\rightarrow j$ 和从 $j\rightarrow i$ 的概率质量相等。分析随机游走时经常使用的一个工具，对称化转移矩阵，定义如下：

$$
D_{ij} = \sqrt{P_{ij}P_{ji}}
$$

对于可逆随机游走，它是一个保留了 $P$ 的谱信息的非负实对称矩阵：

定理 1.3. 对于任意可逆的随机游走，$P$ 和 $D$ 相似。具体地，定义 $\Pi = \operatorname{diag}(\pi)$。有

$$
D = \Pi^{-1/2}P\Pi^{1/2}.
$$

证明. 使用细致平衡条件验算即可。

$\blacksquare$

用随机游走解决搜索问题

在常见的搜索问题中，我们要在一个大小为 $N$ 的搜索空间中搜寻一个被标记的点。使用随机游走，我们容易设计以下算法：

设计一个随机游走的转移矩阵 $P$。
从均匀分布（或者随便一个分布）里面采样 $x$。
模拟 $t$ 随机游走，直到搜到一个目标解。

形式化地，我们考虑一个图 $G = (V, E)$，其中 $M \subset V$ 中的点被标记。任取一个随机矩阵 $P$，并且不妨设它是遍历且可逆的。将其改造成：

$$
P’_{jk} = \begin{cases}
[j = k], & k\in M, \\
P_{jk}, & \text{otherwise.}
\end{cases} \label{eq:marked-walk}
$$

最小的、使得 $t$ 步之后以常数概率走到一个被标记点的 $t$ 称为这个随机游走算法的命中时间（Hitting Time）。

作为热身，本节先证明以下定理：

定理 1.4. 设 $P$ 是遍历可逆的随机矩阵，其稳态分布为 $\pi$。若其谱间隙 $1 - \lambda_2(P)$ 为 $\delta$，且稳态分布在 $M$ 上的总质量为 $\epsilon = \sum_{i\in M} \pi_i$，则这个随机游走的命中时间
$$
t = O(1 / (\delta\epsilon))
$$

为了计算方便，我们不妨对点进行重编号，让 $M$ 中的点编号靠后。此时可以将 $P’$ 写作一个简明的分块下三角矩阵：

$$
P’ = \begin{pmatrix}
P_M & 0 \\
Q & I
\end{pmatrix}, \qquad (P’)^t = \begin{pmatrix}
P_M^t & 0 \\
Q\frac{P^t_M - I}{P_M - I} & I
\end{pmatrix}.
$$

我们从 $V\setminus M$ 上的初始分布开始游走（如果随机出 $x\in M$，那么直接就做完了，因此我们在第一步没有随出带标记的元素的条件下计算）。将初始分布对应的向量记作 $v$。则 $t$ 步之后没有走到 $M$ 中的概率无非是：

$$
\Pr[x_t\notin M | x_0 \notin M] = \left\lVert P_M^t v\right\rVert_1 \leq \left\lVert P_M^t\right\rVert_1 \leq \left\lVert P_M^t\right\rVert_2 \leq \left\lVert P_M\right\rVert_2^t.
$$

要让这个概率是 $O(1)$ 的，我们只需要令 $t = \frac{1}{1 - \left\lVert P_M\right\rVert}$。接下来，我们使用定理 1.1 中的参数来限制 $\left\lVert P_M\right\rVert$。

引理 1.5. 设 $P$ 可逆。若 $P$ 的谱间隙至少是 $\delta$，$|M|\geq \epsilon N$，那么 $\left\lVert P_M\right\rVert \leq 1 - \delta\epsilon$。

证明. 定义 $D$ 左上角和 $P_M$ 形状相同的一块为 $D_M$，$D_M$ 是非负实对称矩阵，因此必然有一个主特征向量 $v$。将 $v$ 后面 $m$ 维补 $0$ 得到 $w$。根据定理 1.3，$D_M$ 保留了 $P_M$ 的谱信息。于是

$$
\begin{aligned}
\left\lVert P_M\right\rVert = \left\lVert D_M\right\rVert = v^\top D_M v = w^\top D w
\end{aligned}
$$

现在将 $D$ 谱分解。有 $D$ 的主特征向量为 $\sqrt \pi$，

$$
\begin{aligned}
w^\top D w &= |w^\top \sqrt \pi|^2 + \sum_{\lambda \ne 1} \lambda |v_\lambda^\top w|^2 \\
&\leq |w^\top \pi|^2 + (1 - \delta)\sum_{\lambda \ne 1} |v_\lambda^\top w|^2 \\
&= 1 - \delta\left(1 - |w^\top \sqrt \pi|^2\right) \\
&\leq 1 - \delta\left(1 - \lVert w\rVert_2^2 \left(\sum_{i\in V\setminus M} (\sqrt \pi)^2\right)\right) \\
&= 1 - \delta\left(1 - (1 - \epsilon)\right) = 1 - \delta\epsilon
\end{aligned}
$$

$\blacksquare$

引理 1.5 和前面的论证自然可以推出定理 1.4。

Remark. 这个 $1 / (\epsilon \delta)$ 符合直觉，而且一般地，它是紧的。

这个 bound 符合用 markov chain 独立随机采样的直觉：我们用 $1 / \delta$ 步就可以让 markov chain 基本上收敛于稳态分布，此时抽出的样本的分布接近稳态分布。而从稳态分布中抽样抽到一个被标记的样本的概率正是 $\epsilon$。独立重复这个过程 $1 / \epsilon$ 次，就可以高概率抽到一个样本。

这个界基本上是紧的。考虑以下的随机游走：任取想要的稳态分布 $\pi$，每次以 $1 / \delta$ 概率留在原地，以 $\delta$ 概率用稳态分布抽样转移。那么任意时刻，下一次抽到一个被标记样本的概率都是 $\epsilon \delta$。

量子随机游走

现在我们考虑“量子化”一个随机游走 $P$。一个最初步的想法是使用算符

$$
|j\rangle \mapsto |\partial_j\rangle := \sum_k \sqrt{P_{kj}}|k\rangle
$$

然而这个算符不是酉的。可以想象的是，量子的演化总是可逆的，但对于马尔可夫这种扩散状的过程则不是这样。所以，你几乎没有办法在原地构造一个量子的演化，使得每个点都对应一个 computational basis vector、将概率分布编码在振幅上、不做任何中途测量、最终模拟一个马尔科夫链的 dynamics。此处所谓量子随机游走之框架，其实和原来的随机游走 $P$ 关系不大。更合适的理解方法是如 Ambainis [1] 所言，将其视为某种 Grover 反射的利用了图 $G$ 结构信息的拓展。接下来的内容按照如下结构组织：

在 2.1 节，我们给出一个量子意义下的随机游走算符 $U$，然后分析其谱性质。
在 2.2 节，我们给出一个早期的随机游走框架，然后分析其查询复杂度。
在 2.3 节，我们介绍 MNRS 意义下的随机游走框架，一个上述算法的优化。

Remark. 本文内容和北京大学量子计算课程中的随机游走框架有什么关系？

我们介绍的这个随机游走的框架和我校的量子计算课程讲授的框架 [5] 有一定的相通之处。该框架直接从 $O_U$ 出发，构造了矩阵 $D$ 的 block encoding

$$
O_D = O_U^\dagger S O_U
$$

然后发现了 $D$ 的特征向量在 block encoding 中被 qubitization，此后便将其视作 $\operatorname{SU}(2)$ 中的旋转，分析区分两个态所需的旋转次数。而我们的框架下的 $U$ 为

$$
SO_U^\dagger R_0 O_U
$$

做一个坐标变换 $O_U (\cdot) O_U^\dagger$ 就发现在选定的基底下，我们和上述 block encoding 只差了一次关于 $|0\rangle$ 的反射 $R_0$。所以说本文将要使用的随机游走算符本质上是一个反射，和旋转之间还欠着另一个反射，我们最后得到的算法也不是某种旋转状物，而是使用相位估计。

我个人觉得上来就提出要构造 $D$ 矩阵的 block encoding 这个 leap 太大，缺乏动机，此外讲义有些东西写的不清楚，所以我不考虑这条路径。

量子随机游走算符

这里我们给出 Andrew Childs 的讲义意义下 [2] 的随机游走的框架，它是 Szegedy 意义下的随机游走模型 [3] 的一个特例。本章所述的随机游走算符的源头还需要再往上面爬一点，我觉得不太必要，因此我们直接从这个形式的算符出发。

考虑一个随机矩阵 $P$。定义

$$
|\psi_j\rangle = |j\rangle\otimes \sum_{k}\sqrt{P_{kj}}|k\rangle
$$

注意因为 $P$ 是随机矩阵，所以这个态确实是归一化的。此外，因为张量积第一项的存在性，这是一组标准正交基。考虑朝 $\{|\psi_i\rangle\}$ 的投影和交换算符：

$$
\Pi := \sum_{j = 1}^N |\psi_J\rangle\langle\psi_j|, \qquad S = \sum_{j, k = 1}^N |j, k\rangle\langle k, j|
$$

我们定义 $P$ 对应的量子随机游走的算符为 $U := S(2\Pi - I)$，其中 $S$ 是 SWAP 门。粗浅地看，这个算符是首先用第一个 register 进行控制，让第二个 register 做关于 $|\partial_j\rangle$ 的反射以产生干涉。这个操作叫做 Grover Coin Flip，用于产生“随机性”。然后交换两个寄存器使得刚才扩散的结果被换到第一位，类似于你现在走到了下一个点。

为了理解这个随机游走算符的行为，我们首先分析 $U$ 的几何结构。我们尝试的角度是寻找 $U$ 的一个比较细的不变子空间分解，来得到 $U$ 的谱结构。既然 $U$ 是一个反射复合上交换算符，我们不妨从这个反射的不变子空间开始。我们将 $2\Pi - I$ 的不变子空间的标准正交基 $\{|\psi_j\rangle\}$ 纵向排列成以下矩阵：

$$
T := \sum_j |\psi_j\rangle\langle j|
$$

自然有 $TT^\dagger = \Pi$ 和 $T^\dagger T = I$。接下来，有一个深刻的洞察是 $U$ 的谱结构和 $T^\dagger ST$ 这个矩阵的谱结构密切相关。

Remark. 怎么看出来的？

我们考虑直接计算 $U$ 的特征向量。假设 $|\mu\rangle$ 是 $U$ 的特征值为 $\mu$ 的特征向量。有

$$
S(TT^\dagger - I)|\mu\rangle = \mu|\mu\rangle
$$

我们整理一下这个式子。首先有

$$
STT^\dagger |\mu\rangle = (S + \mu I)|\mu\rangle
$$

注意 $S^2 = I$。因此有当 $\mu \ne \pm 1$ 时，$(S + \mu I)^{-1} = (S - \mu I) / (1 - \mu^2)$。两边乘上这个逆，得到

$$
\frac{T - \mu ST}{1 - \mu^2}\cdot T^\dagger|\mu\rangle = |\mu\rangle \label{eq:mu-combination}
$$

至此已经很明显。两边再乘上 $T^\dagger$，并且令 $|\lambda\rangle = T^\dagger |\mu\rangle$ 得到

$$
-\frac{\mu}{1 - \mu^2}\cdot T^\dagger ST |\lambda\rangle = \left(1 - \frac{1}{1 - \mu^2}\right)|\lambda\rangle \label{eq:value-relation}
$$

此处的 $|\lambda\rangle$ 就是 $T^\dagger ST$ 的特征向量。反过来注意 \ref{eq:mu-combination}。这表明 $|\mu\rangle$ 是 $T|\lambda\rangle, ST|\lambda\rangle$ 的线性组合。也就是说，只要我们分析出了 $T^\dagger ST$ 的谱结构，拿着一个特征向量，根据 \ref{eq:value-relation} 可知，$\mu$ 是带参数 $\lambda$ 的二次方程的根。据此可以解出两个 $U$ 的特征值 $\mu_1, \mu_2$，并用 \ref{eq:mu-combination} 线性组合出 $U$ 的两个特征向量；$U$ 的其余特征值的特征向量必然是 $\pm 1$，至此 $U$ 的谱结构已然明了，接下来我们的分析基本上沿着这条线进行。

先考虑计算 $T^\dagger ST$ 是什么。

$$
\begin{align}
T^\dagger ST &= \sum_{i, j, k, l} \sqrt{P_{ji}P_{lk}}|i\rangle\langle i, j|l, k\rangle\langle k| \\
&= \sum_{i, k} \sqrt{P_{ki}P_{ik}}|i\rangle\langle k| = D
\end{align}
$$

于是，顺着 Remark 中的路线，我们便可以证明以下定理：

定理 2.1. 设 $P$ 是一个随机矩阵，$D$ 是其对称化转移矩阵。令 $D$ 的特征值是 ${\lambda}$，对应实特征向量 ${|\lambda\rangle}$。那么 $U$ 的特征值为 $\pm 1$ 和 $\lambda \pm i\sqrt{1 - \lambda^2} = e^{\pm i\arccos \lambda}$。

证明. 从 $|\lambda\rangle$ 出发。定义 $|\tilde \lambda\rangle = T|\lambda\rangle$，简单计算可知

于是，任意的 $\operatorname{span}\{|\tilde \lambda\rangle, S|\tilde \lambda\rangle\}$ 都是 $U$ 的不变子空间。限制在这个子空间上，$U$ 在这组基下的矩阵表示是

$$
\begin{pmatrix}
0 & \lambda \\
-1 & 2\lambda
\end{pmatrix}
$$

考虑全空间在这些不变子空间下的正交补

$$
\bot := \{|x\rangle : \forall \lambda, \langle x|\tilde \lambda\rangle = \langle x|S|\tilde \lambda\rangle = 0\}
$$

同样可以验证这个空间也是 $U$ 的不变子空间，更具体地，$U$ 限制在 $\bot$ 上就是 $-S$。至此我们知道了 $U$ 将整个空间划分成它不变子空间的直和：

$$
\mathcal{H} = \bot \oplus \bigoplus_{\lambda} \mathrm{span}\{|\tilde\lambda\rangle, S|\tilde\lambda\rangle\}
$$

要求 $U$ 的特征值，只需要在每个不变子空间中求解。对于 $\bot$，因为 $U$ 限制在其上是对合变换 $-S$，所以特征值只有 $\pm 1$。对于某个 $\mathrm{span}\{|\tilde\lambda\rangle, S|\tilde\lambda\rangle\}$，我们解特征方程

$$
\mu^2 - 2\lambda\mu + \lambda = 0, \qquad \Rightarrow \qquad \mu = \lambda\pm i\sqrt{1 - \lambda^2} = \exp(\pm i\arccos \lambda).
$$

$\blacksquare$

Remark. 注意如果矩阵 $D$ 的谱间隙为 $\delta$，那么在量子随机游走中，$U$ 有谱相位间隙

$$
\arccos(1 - \delta) \geq \sqrt{2\delta}
$$

这给随机游走搜索中的一个关键变量——某种意义上的谱间隙带来了平方级别的放大，这个规律称为 spectral gap amplification。在下一节我们将看到基于量子游走的搜索如何利用这个现象。

算法框架

和经典类比，我们也可以用随机矩阵 $P$ 对应的量子游走算符来解决 quantum query model 下的问题 $\Psi$。这里假设读者熟悉 quantum query model，如果不熟悉可以看第 3 章（元素区分问题）。要求是：

你需要用实例的 oracle $O_x$ 构造受控 $U$ 门。当该 oracle 对应一个 $\Phi(x) = 0$（$M = \varnothing$）的实例时，$U$ 是 $P$ 对应的随机游走；当该 oracle 对应一个 $\Phi(x) = 1$（$M\ne \varnothing$）的实例时，$U$ 是 $P’$（参见式 \ref{eq:marked-walk}）对应的随机游走。
如果问题有解，那么算法以常数 $1 - \varepsilon > 0$ 概率输出 $1$。否则，算法一定输出 $0$。

此处我们给出量子随机游走的算法框架。假设 $P$ 是一个遍历性可逆随机游走，且我们有以下原素的电路：

$P$ 的稳态分布的制备线路 $O_S : |0\rangle \mapsto |\pi\rangle$。
随机游走 oracle $O_U : |0, i\rangle \mapsto \sum_j \sqrt{P_{ji}}|j, i\rangle$。
检查一个点是否为被标记点的线路 $O_C: |x, 0\rangle \mapsto |x, [x\in M]\rangle$。

子过程. 用常数次 $O_U, O_C$ 制备 $U$。

这里我们演示如何用以上两个算符来实现受控 $U$ 门。使用 $n$ 比特以及 $2$ 比特的 Toffoli 门和 phase-kickback，我们可以制备关于任意一个 computational basis $|x\rangle$ 的反射算符及其受控版本

$$
R_x = 2|x\rangle\langle x| - I
$$

于是显然

$$
O_U^\dagger (R_0 \otimes I) O_U = 2\Pi - I, \qquad O_U^\dagger O_U = I
$$

因此受 $c$ 控制的 $U$ 的制备方法如下：

先用 $O_C$ 将标记信息存到一个辅助比特 $|b\rangle$ 中；
作用 $O_U^\dagger$；
条件于 $\neg b \wedge c$ 作用 $R_0$；
作用 $O_U$；
条件于 $b\wedge c$ 作用 $R_x$，其中 $x$ 是边态的第一个 register。

步骤 1. 制备 $P$ 的稳态分布 $|\pi\rangle$。对 $|\pi, 0\rangle$ 作用 $O_C$ 之后测量第二个寄存器。如果结果为 $1$，输出 $1$ 并停止。如果没有停止，假设测量后态坍缩到了 $|\psi\rangle$。

这一步做完之后，如果 $M = \varnothing$，那么测量后第一个寄存器还是 $|\psi\rangle = |\pi\rangle$。着重考虑 $M$ 非空的情况。此时如果我们测出了 $1$，那么我们可以断言答案为 $1$。否则 $|\pi\rangle$ 将坍缩至 $\{|x\rangle : x\in M\}$ 正交的子空间中。注意若 $M$ 非空，有
$$
D’ = \begin{pmatrix}
D_M & 0 \\
0 & I
\end{pmatrix}
$$

坍缩之后得到的态 $|\psi\rangle$ 是 $|D_M\rangle$ 的特征向量后面补 $0$。

步骤 2. 令 $|\tilde\psi\rangle = O_U|0, \psi\rangle$。在 $|\tilde\psi\rangle$ 上用受控 $U$ 门做精度为 $\sqrt{\delta\epsilon}$ 的相位估计。测出相位 $\varphi$ 之后，输出 $[\varphi = 0]$。

如果 $M = \varnothing$，那么

$$
|\psi\rangle = \sum_i\sqrt{\pi_i}|i\rangle\sum_j\sqrt{P_{ji}}|j\rangle
$$

从这个形式可见 $(2\Pi - I)O_U|\pi\rangle = O_U|\pi\rangle$。而由于 $P$ 是可逆随机游走，有

$$
S|\psi\rangle = \sum_i\sum_j \sqrt{\pi_i P_{ji}}|j, i\rangle = \sum_i\sum_j \sqrt{\pi_i P_{ji}}|i, j\rangle
$$

因此对 $|\psi\rangle$ 做相位估计，总是得到 $0$。

另一方面，若 $M\ne \varnothing$，则 $|\psi\rangle$ 可以被分解为 $D_M$ 的特征向量的线性组合。相干的相位估计对于每个分量分别测出相位。注意 $O_U|0, \psi\rangle = T|\psi\rangle$。因此，$|\tilde \psi\rangle$ 落在 $D_M$ 的特征值 $\{\lambda\}$ 对应的这些不变子空间 $\operatorname{span}\{|\tilde\lambda\rangle, S|\tilde\lambda\rangle\}$ 中。

上一节的论证表明，对 $|\tilde\psi\rangle$ 做相位估计，可能的结果只有 $\pm \arccos(\lambda)$。引理 1.5 告诉我们，$D_M$ 的最大特征值不超过 $1 - \delta\epsilon$。因此，根据此前推导的谱相位间隙，有这些相位中与 $0$ 最接近者也至少有 $\sqrt{\delta\epsilon}$。做精度为 $O(\sqrt{\epsilon\delta})$ 的相位估计，即可以常数（具体来说是 $8/\pi^2$ 的概率）输出一个非 $0$ 的相位估计。

最后我们来分析这个算法的查询复杂度。实践中，我们采用的图 $G = (V, E)$ 的顶点 $V$ 一般是由搜索状态 $x$ 和它携带的数据结构 $\operatorname{DS}(x)$ 共同决定。一般来说，单纯制备图上的稳态和转移不需要任何查询，查询只在维护数据结构时产生，详见元素区分问题。无论如何，我们考虑用我们使用的三个原素 $O_S, O_U, O_C$ 的查询次数来表示整个随机游走算法的查询复杂度。记

$O_S$ 对搜索问题 oracle 的查询次数为 $S$。
$O_U$ 对搜索问题 oracle 的查询次数为 $U$。
$O_C$ 对搜索问题 oracle 的查询次数为 $C$。

实际上，$U$ 就是各类广泛流传的讲义和定理 2.2 中所谓的维护数据结构所需的查询次数。考虑 $O_U$ 的构造：我们有了 $|u, \operatorname{DS}(u), 0, 0\rangle$，我们可以不用任意查询地算出 $P$ 的转移边 $|u, 0\rangle\mapsto \sum_v \sqrt{P_{vu}}|u, v\rangle$。将这个没有开销的算符作用在上述态的第 $1, 3$ 寄存器，得到若干形如 $|u, \operatorname{DS}(u), v, 0\rangle$ 的分量的叠加。现在，将 $\operatorname{DS}(u)$ 复制到第四个寄存器只需要用 CNOT 门，因此唯一产生查询的位置就是将 $\operatorname{DS}(u)$ 修改成 $\operatorname{DS}(v)$ 所需的开销。简单分析以上算法，得到本节的主定理：

定理 2.2. 在 quantum query model 下计算一个函数 $\Psi : S\rightarrow \{0, 1\}$。其中，问题的 instance $x\in S$ 仅能通过 quantum oracle $O_x: |i, z\rangle \mapsto |i, z\oplus x_i\rangle$ 访问。如果存在一个图 $G = (V, E)$、标记函数 $M_x : V\rightarrow \{0, 1\}$ 和支撑在 $G$ 上的一个遍历性可逆随机游走 $P$，使得：

$\Psi(x) = 1$ 当且仅当存在 $v\in V, M_x(v) = 1$；
$P$ 的 spectral gap 至少为 $\delta$；
对于任意的 $x$ 使得 $\Phi(x) = 1$，有 $\Pr_{v\sim \pi}[M_v = 1] \geq \epsilon$。

并且，

可以用 $S$ 次 query 制备稳态分布 $|\pi\rangle$；
可以用 $U$ 次 query 完成转移 $u\rightarrow v$；
可以用 $C$ 次 query 检查一个点 $v$ 是否带标记。

那么本问题的查询复杂度

$$
Q_\epsilon(\Phi) = O\left(S + \frac{1}{\sqrt{\delta\epsilon}}(U + C)\right)
$$

证明. 观察到本节所述算法调用 oracle 的位置分别是：

制备稳态分布时调用了一次 $O_S$，产生 $S$ 次查询；然后调用了一次 $O_C$，产生了 $C$ 次查询。
调用一次 $O_U$，产生 $U$ 次查询，然后做了精度为 $\sqrt{\delta\epsilon}$ 的相位估计。

做精度为 $\epsilon$ 相位估计需要依次调用受控 $U, U^2, U^4, U^{2^{\lceil\log(1 / \epsilon)\rceil}}$。总共调用了 $O(1 / \epsilon)$ 次受控 $U$ 门，每次调用 $O(1)$ 次 $O_U$ 和 $1$ 次 $O_C$，产生 $O((U + C) / \sqrt{\delta\epsilon})$ 次 oracle 访问。综上所述，上述算法的查询复杂度为

$$
O\left(S + \frac{1}{\sqrt{\delta\epsilon}}(U + C)\right)
$$

$\blacksquare$

优化：MNRS 随机游走框架

上述随机游走算法的直觉类似于我们在 1 章开头中讲的经典随机游走算法：一直随机游走，直到找到一个目标解。另一方面，我们还可以从第 1 章末尾的 Remark 中的直觉出发，构造如下算法：

从均匀分布出发；
独立重复 $1 / \epsilon$ 次：
$\qquad$ 模拟 $1 / \delta$ 次随机游走；
$\qquad$ 检查是否走到一个标记点。如果走到，退出。

这两个算法看起来没什么差别，但实际上仔细检查就可以发现，新的算法将检查标记的次数从 $1 / (\epsilon\delta)$ 变成了 $1 / \epsilon$。量子这边也是类似。我们可以在内层做精度为 $1 / \sqrt{\delta}$ 的相位估计，制备标记位以后，对标记为 $1$ 的态做振幅放大。可以预见，你会得到一个

$$
O\left(S + \frac{1}{\sqrt{\epsilon}}\left(\frac{1}{\sqrt{\delta}}U + C\right)\right)
$$

的算法。这就是 Magniez-Nayak-Roland-Santha [4] 提出的框架，细节我暂时不研究。

元素区分问题

我们给出量子随机游走的一个具体应用。考虑如下的元素区分问题：

Element Distinctness Problem. 给定一个函数 $f : [n]\rightarrow [n]$，判断是否存在 $1 \leq i < j \leq n$ 使得 $f(i) = f(j)$。

或者在 quantum query model 下，表述为：计算一个函数 $\text{EDP} : ([n]\rightarrow [n])\rightarrow \{0, 1\}$，其中

$$
\text{EDP} : f\mapsto \left[\exists 1 \leq i < j \leq n, f(i) = f(j)\right]
$$

输入 $f$ 被隐藏，只能通过 oracle $O_f : |i, z\rangle \mapsto |i, z\oplus f(i)\rangle$ 访问。熟知经典这个问题只有查询复杂度 $O(n)$（时间复杂度 $O(n\log n)$）的做法。而在量子这边，这个问题是一个量子随机游走的经典应用。在随机游走时，我们使用 quantum walk 中最为常见的 Hamming Graph，其中参数 $M$ 待定：

定义 3.1. 一个参数为 $N, M$ 的 Hamming 图 $H(N, M)$ 包含以下资料：

点集 $V = [N]^M$。
对于两个点 $(x_1, …, x_m), (y_1, …, y_m) \in V$，它们之间有一条边当且仅当这两个向量的 Hamming 距离为 $1$，即存在唯一的 $i$ 使得 $x_i\ne y_i$。

对于图上的每一个点 $(x_1, …, x_m)\in V$，我们给它配备数据结构

$$
\operatorname{DS}(x_1, …, x_m) = (f(x_1), …, f(x_m))
$$

以及标记函数

$$
M(x_1, …, x_m) = \left[\exists 1\leq i < j \leq m, f(x_i) = f(x_j)\right]
$$

注意在正确维护了数据结构之后，判断一个点有没有标记不需要任何查询。

现在，我们考虑在附带数据结构的 $H(N, M)$ 上进行均匀的随机游走 $P$：每次从一个点 $v$ 出发，以 $1 / (M(N - 1))$ 的概率走到它的任意一个邻居。显然对于非平凡的正则图，其中存在大小为 $2, 3$ 的圈，因此这是一个遍历性随机游走。另一方面，$P$ 甚至是对称的。于是 $P$ 可逆，且其唯一的稳态分布是均匀分布。于是在稳态分布中，对于一个有碰撞的实例，一个节点具有标记的概率至少是（此处我们考虑把碰撞的两个位置随意安进去，然后令其他位置都不是这两个东西）

$$
\epsilon \geq \frac{M(M - 1)(N - 2)^{M - 2}}{N^M} = \Theta(M^2 / N^2)
$$

然后我们需要分析 $P$ 的谱。事实上，$P$ 的封闭形式如下：

$$
P = \frac{1}{M(N - 1)}\sum_{i = 1}^M I^{\otimes (i - 1)}\otimes (J - I)\otimes I^{\otimes (M - i)}
$$

显而易见，$P$ 的特征向量形如 $|\psi_1, …, \psi_M\rangle$，对应特征值 $\frac{1}{M(N - 1)}\sum_{i = 1}^M \lambda_i$。其中 $|\psi_i\rangle$ 都是 $J - I$ 的特征向量，对应特征值 $\lambda_i$。而 $J - I$ 是我们熟悉的：它有一个 $1$ 重特征值 $N - 1$，和一个 $N - 1$ 重特征值 $-1$。因此，

$$
\delta = \frac{1}{M}
$$

最后我们来计算随机游走过程中的三个参数。

在初态制备时，我们只需要制备均匀叠加态，然后初始化数据结构即可。初始化数据结构时，需要做 $M$ 次查询。因此 $S = O(M)$。
在转移 $u\rightarrow v$ 时维护数据结构，假设 $u$ 是把第 $i$ 位从 $x_i$ 改成了 $x_i’$，那么我们只需要 uncompute $f(x_i)$，然后 compute $f(x_{i}’)$ 即可算出 $\mathrm{DS}(v)$。因此 $U = O(1)$。
按前文所说，$C = 0$。

使用 2.2 节的随机游走算法，其时间复杂度为

$$
O\left(M + \sqrt{\frac{N^2}{M}}\right)
$$

调参知道令 $M = N^{2/3}$ 时算法复杂度为 $O(N^{2/3})$。这和本问题的 $\Omega(N^{2/3})$ 量子查询下界匹配。

参考文献

Andris Ambainis. Quantum walk algorithm for element distinctness. 2003, https://arxiv.org/pdf/quant-ph/0311001v1.
Andrew M. Childs. Lecture Notes on Quantum Algorithms. 2025.
Mario Szedy. Quantum speed-up for Markov chain based algorithms. 45th FOCS. 2004.
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha. Search via Quantum Walk. 2011, https://arxiv.org/abs/quant-ph/0608026
Tongyang Li. Introduction to Quantum Computing. 2026. https://pku-quantum.tech/