# 量子行走详解：连续与离散量子行走

量子行走（Quantum Walk）是经典随机行走的量子对应物，也是量子计算的基本原语（primitive）之一。与经典随机行走的扩散式传播不同，量子行走利用量子叠加与干涉实现弹道式传播（ballistic propagation）：$n$ 步之后位置分布的宽度从 $O(\sqrt{n})$ 增长到 $O(n)$。量子行走不仅为 Grover 搜索、图同构检验等算法提供了统一框架，也是哈密顿量模拟、量子搜索引擎与量子算法设计的基础工具。

## 经典随机行走回顾

在经典随机行走（classical random walk）中，粒子位于图 $G=(V,E)$ 的某个顶点 $x$，每一步以均匀概率跳到某个相邻顶点：

$$P(x \to y) = \frac{1}{\deg(x)}, \quad y \in N(x),$$

其中 $N(x)$ 是 $x$ 的邻居集合，$\deg(x) = |N(x)|$ 是顶点的度。若粒子从原点出发，$n$ 步之后位置的涨落服从扩散规律：标准差为 $\sigma = O(\sqrt{n})$，因此覆盖距离 $O(n)$ 的范围需要 $O(n^2)$ 步。

量子行走将"概率"替换为"振幅"，将"扩散"替换为"相干干涉"，于是传播速度从 $O(\sqrt{n})$ 提升到 $O(n)$。这种由扩散到弹道的质变，正是量子行走算法加速的根源。

## 离散时间量子行走（DTQW）

### 定义与构造

离散时间量子行走（Discrete-Time Quantum Walk, DTQW）定义在硬币-位置联合空间 $\mathcal{H}_C \otimes \mathcal{H}_P$ 上：

- 位置空间（position space）$\mathcal{H}_P$：以图的顶点为基态 $\{|x\rangle : x \in V\}$；
- 硬币空间（coin space）$\mathcal{H}_C$：编码行走方向的内部自由度，基态为 $\{|c\rangle : c = 0, 1, \ldots, d-1\}$，其中 $d$ 是图的最大度。

单步演化由两个酉算符（unitary operator）交替组成。

第一是硬币算符（coin operator）$C$，它在硬币空间上作用一个酉变换：

$$C = I_P \otimes F_d,$$

其中 $F_d$ 是 $d$ 维硬币。最常用的是 $d=2$ 的 Hadamard 硬币

$$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix},$$

以及 $d$ 维的 Grover 扩散算符（Grover diffusion operator）

$$G_d = \frac{2}{d}J_d - I_d,$$

其中 $J_d$ 是全 1 矩阵。我们验证 $G_d$ 的作用方式：记均匀硬币态 $|s_d\rangle = \frac{1}{\sqrt d}\sum_{c=0}^{d-1}|c\rangle$，则 $J_d = \vec 1 \vec 1^{\mathsf T}$ 满足 $J_d|s_d\rangle = d\,|s_d\rangle$，而对满足 $\langle s_d|v\rangle = 0$ 的 $v$ 有 $J_d|v\rangle = 0$。代入上式得

$$G_d|s_d\rangle = |s_d\rangle, \qquad G_d|v\rangle = -|v\rangle \quad (v \perp |s_d\rangle),$$

即 $G_d$ 恰好执行 Grover 迭代中的"关于均值翻转"。这一结构是后文行走搜索与 Grover 算法相通的根源。

第二是移位算符（shift operator）$S$，它根据硬币取值把振幅搬运到相邻顶点：

$$S|x, c\rangle = |x_c, c\rangle,$$

其中 $x_c$ 是顶点 $x$ 的第 $c$ 个邻居。注意 $S$ 是基态集合上的一个置换，它酉当且仅当映射 $(x,c) \mapsto (x_c, c)$ 是双射。对 $d$ 正则图配上一致性边标号（每个顶点把它的 $d$ 条边分别标为 $0,\ldots,d-1$，且每个标号方向诱导的映射可逆，例如格点上按方向 $\{\pm e_i\}$ 统一标号）即可保证这一点。

总演化算符为

$$U = S \cdot (I_P \otimes F_d),$$

即"先掷硬币、再按硬币方向移动"。初始态通常取直积态

$$|\psi_0\rangle = |0\rangle_P \otimes |\phi\rangle_C,$$

其中硬币态 $|\phi\rangle_C$ 的选择会影响分布的左右对称性（见下节）。

### 一维线上的量子行走

最简单的非平凡例子是整数格点 $\mathbb{Z}$ 上的行走：硬币取二维（右/左），硬币算符为 $H$，移位规则为

$$S|x, 0\rangle = |x+1, 0\rangle \quad (\text{向右}), \qquad S|x, 1\rangle = |x-1, 1\rangle \quad (\text{向左}),$$

单步算符为 $U = S \cdot (I_P \otimes H)$。

我们推导振幅的递推关系。设 $|\psi(n)\rangle = \sum_{x,c}\alpha_{x,c}(n)\,|x,c\rangle$。先作用硬币 $I \otimes H$，得到中间振幅

$$\beta_{x,0} = \frac{1}{\sqrt{2}}\left(\alpha_{x,0} + \alpha_{x,1}\right), \qquad \beta_{x,1} = \frac{1}{\sqrt{2}}\left(\alpha_{x,0} - \alpha_{x,1}\right).$$

再作用移位 $S$。由于处在 $(x,0)$ 的振幅只能来自上一时刻的 $(x-1,0)$（它向右移动一格到达 $x$），处在 $(x,1)$ 的振幅只能来自 $(x+1,1)$，我们得到

$$\alpha_{x,0}(n+1) = \frac{1}{\sqrt{2}}\left[\alpha_{x-1,0}(n) + \alpha_{x-1,1}(n)\right],$$
$$\alpha_{x,1}(n+1) = \frac{1}{\sqrt{2}}\left[\alpha_{x+1,0}(n) - \alpha_{x+1,1}(n)\right].$$

$n$ 步后的位置分布需要对硬币求和：

$$P(x, n) = \sum_{c \in \{0,1\}} \left|\alpha_{x,c}(n)\right|^2,$$

其支撑满足 $|x| \le n$ 且 $x \equiv n \pmod 2$（每步恰好移动一格）。数值模拟显示 $P(x,n)$ 呈双峰结构：概率集中在 $\pm \frac{n}{\sqrt{2}}$ 附近；若初始硬币为对称态 $\frac{1}{\sqrt{2}}(|0\rangle + i|1\rangle)$，双峰等高，而初始硬币 $|0\rangle$ 则给出左峰较高的不对称分布。这与经典随机行走始终停留在原点附近的单峰形成鲜明对比。下一节我们用傅里叶分析严格解释双峰位置 $\pm n/\sqrt{2}$ 的来源。

### 数学分析

定义傅里叶变换 $\tilde{\alpha}_c(k) = \sum_x \alpha_{x,c}\, e^{ikx}$。对上面两条递推式两边乘 $e^{ikx}$ 并对 $x$ 求和：第一式令 $y = x - 1$（即 $x = y+1$，求和号平移不影响），第二式令 $y = x + 1$，得

$$\tilde{\alpha}_0(k, n+1) = \frac{e^{ik}}{\sqrt{2}}\left[\tilde{\alpha}_0(k,n) + \tilde{\alpha}_1(k,n)\right],$$
$$\tilde{\alpha}_1(k, n+1) = \frac{e^{-ik}}{\sqrt{2}}\left[\tilde{\alpha}_0(k,n) - \tilde{\alpha}_1(k,n)\right].$$

于是每个动量 $k$ 解耦为一个 $2 \times 2$ 块的迭代：

$$\begin{pmatrix} \tilde{\alpha}_0(k, n+1) \\ \tilde{\alpha}_1(k, n+1) \end{pmatrix} = M(k) \begin{pmatrix} \tilde{\alpha}_0(k, n) \\ \tilde{\alpha}_1(k, n) \end{pmatrix}, \qquad M(k) = \frac{1}{\sqrt{2}} \begin{pmatrix} e^{ik} & e^{ik} \\ e^{-ik} & -e^{-ik} \end{pmatrix},$$

且 $\tilde{\psi}(k, n) = M(k)^n\, \tilde{\psi}(k, 0)$。因此长时间行为完全由 $M(k)$ 的谱决定。

我们先把 $M(k)$ 分解为 Pauli 矩阵以便严格对角化。由 $M(k) = \mathrm{diag}(e^{ik}, e^{-ik})\,H$，写 $\mathrm{diag}(e^{ik}, e^{-ik}) = \cos k \, I + i \sin k \, \sigma_z$，并利用 $H = \frac{\sigma_x + \sigma_z}{\sqrt 2}$ 与 $\sigma_z \sigma_x = i \sigma_y$，展开得到

$$M(k) = \frac{1}{\sqrt{2}}\left[ i\sin k \, I + \cos k \,\sigma_x - \sin k\, \sigma_y + \cos k\, \sigma_z \right].$$

记 $\vec b(k) = (\cos k, -\sin k, \cos k)$，则 Pauli 部分 $(\vec b \cdot \vec\sigma)^2 = \|\vec b\|^2 I = (1 + \cos^2 k)\, I$，从而

$$M(k)^\dagger M(k) = \frac{1}{2}\left[\sin^2 k + (1 + \cos^2 k)\right] I = I,$$

即 $M(k)$ 自动酉——这与每一步演化都是酉算符的事实一致，也验证了分解无误。

由于 $\vec b \cdot \vec\sigma$ 的本征值为 $\pm\|\vec b\| = \pm\sqrt{1+\cos^2 k}$，$M(k)$ 的本征值为

$$\lambda_\pm(k) = \frac{i \sin k \pm \sqrt{1 + \cos^2 k}}{\sqrt{2}}.$$

两者模长为 1，直接验算：$|\lambda_\pm|^2 = \frac{\sin^2 k + 1 + \cos^2 k}{2} = 1$。把本征值写成纯相位形式

$$\lambda_+(k) = e^{+i\omega(k)}, \qquad \lambda_-(k) = -e^{-i\omega(k)},$$

并对照实部与虚部，即得色散关系（dispersion relation）

$$\sin \omega(k) = \frac{\sin k}{\sqrt{2}}, \qquad \cos \omega(k) = \sqrt{\frac{1 + \cos^2 k}{2}}, \qquad \omega(k) = \arcsin \frac{\sin k}{\sqrt 2},$$

其中第三个等式由第一个等式直接给出（验证自洽：$\sin^2\omega + \cos^2\omega = \frac{\sin^2 k}{2} + \frac{1+\cos^2 k}{2} = 1$）。两个本征值相差一个与 $k$ 无关的因子 $-1 = e^{i\pi}$，因此相位的 $k$ 导数、亦即群速度（group velocity），只取 $\pm\omega'(k)$ 两个值。由复合函数求导，

$$v_\pm(k) = \frac{d(\pm\omega)}{dk} = \pm \frac{\cos k / \sqrt 2}{\sqrt{1 - \sin^2 k / 2}} = \pm \frac{\cos k}{\sqrt{2 - \sin^2 k}} = \pm \frac{\cos k}{\sqrt{1 + \cos^2 k}}.$$

其绝对值在 $k = 0, \pi$ 处取最大值 $\frac{1}{\sqrt 2}$。因此概率峰以每步 $\frac{1}{\sqrt 2}$ 格的速度传播，这严格解释了双峰位置 $\pm\frac{n}{\sqrt 2}$；支撑的光锥边缘速度为每步 1 格（$|x| \le n$），但光锥边缘处的概率质量很小。传播是线性的（弹道式），速度平方级优于经典的扩散速度。

### 图上的离散量子行走

对一般图 $G = (V, E)$，DTQW 的构造需要对每条边指定一致性方向标号（见上文移位算符的讨论）。以 $d$ 正则图为例（每个顶点的度均为 $d$）：

- 硬币空间维度为 $d$；
- 硬币算符取 $d$ 维 Grover 扩散算符 $G_d = \frac{2}{d}J_d - I_d$，其作用已在上文逐项推导；
- 移位规则为 $S|v, c\rangle = |v_c, c\rangle$，其中 $v_c$ 是 $v$ 的第 $c$ 个邻居。

混合时间（mixing time）方面需要注意：由于演化是酉的，DTQW 的瞬时分布一般不收敛。我们转而考虑时间平均分布 $\bar{P}_T(x) = \frac{1}{T}\sum_{n<T} P(x,n)$。在 $n$ 个顶点的环图上，经典随机行走的混合时间为 $\Theta(n^2)$，而 DTQW 的时间平均分布只需 $O(n \log n)$ 步即可接近均匀 [1]——这是量子行走相对经典行走的又一平方级优势。

## 连续时间量子行走（CTQW）

### 定义

连续时间量子行走（Continuous-Time Quantum Walk, CTQW）直接由图的矩阵驱动，无需硬币空间：

$$i\frac{d}{dt}|\psi(t)\rangle = H |\psi(t)\rangle, \qquad U(t) = e^{-iHt},$$

其中哈密顿量 $H$ 有两种常见取法：

- 邻接矩阵哈密顿量：$H = A$，其中 $A_{xy} = 1$ 当且仅当 $(x,y) \in E$；
- 拉普拉斯矩阵哈密顿量：$H = L = D - A$，其中 $D$ 是度矩阵。

两者的本征值关系可逐项写出。对 $d$ 正则图，$D = dI$，于是 $L = dI - A$：二者本征矢完全相同，本征值满足线性关系 $\mu_j = d - \eta_j$（$\eta_j$ 为 $A$ 的本征值）。相应地，$e^{-iLt} = e^{-idt} e^{+iAt}$，即两种行走的演化只相差时间反演与一个整体相位，位置分布相同。一般图上二者谱结构不同（$L$ 半正定而 $A$ 不定），选择哪种取决于具体问题。

初始态通常取某个顶点态 $|\psi(0)\rangle = |s\rangle$。

### 一维线上的 CTQW

取 $H = A$（无限线的邻接矩阵）。记平面波态 $|k\rangle = \sum_x e^{ikx}|x\rangle$，则 $A|k\rangle = (e^{ik} + e^{-ik})|k\rangle = 2\cos k\,|k\rangle$，故特征值为 $E(k) = 2\cos k$。初始态的谱分解为 $|0\rangle = \frac{1}{2\pi}\int_{-\pi}^{\pi} |k\rangle\, dk$（直接验证：右边 $= \sum_x \left[\frac{1}{2\pi}\int e^{ikx}dk\right]|x\rangle = \sum_x \delta_{x,0}|x\rangle$）。于是

$$|\psi(t)\rangle = \frac{1}{2\pi}\int_{-\pi}^{\pi} e^{-i\,2t\cos k}\,|k\rangle\,dk.$$

把它展开到位置基上，需要计算 $\frac{1}{2\pi}\int_{-\pi}^{\pi} e^{-i\,2t\cos k} e^{ikx} dk$。代入 Jacobi–Anger 展开 $e^{-iz\cos\theta} = \sum_n (-i)^n J_n(z)\, e^{in\theta}$（$J_n$ 为第一类贝塞尔函数，Bessel function of the first kind），逐项积分后仅 $n = -x$ 项存活：

$$|\psi(t)\rangle = \sum_x (-i)^x J_x(2t)\,|x\rangle,$$

其中用了 $J_{-x} = (-1)^x J_x$。位置概率为

$$P(x, t) = J_x(2t)^2$$

（相位 $(-i)^x$ 不影响概率），且满足归一化 $\sum_x J_x(2t)^2 = 1$。$J_x(2t)$ 在 $|x| > 2t$ 时指数衰减，概率质量集中在光锥边界 $|x| \approx 2t$ 附近宽度 $O(t^{1/3})$ 的区域内振荡——传播速度为 $O(t)$（线性），远快于经典行走的 $O(\sqrt t)$。

### CTQW 的搜索算法

定理（Farhi 与 Gutmann，1998）：在 $N$ 个顶点的完全图上，若存在唯一标记顶点 $|w\rangle$，CTQW 可以在 $O(\sqrt N)$ 时间内以接近 1 的概率找到它——复现 Grover 搜索的复杂度。

实现方式如下。取哈密顿量

$$H = |w\rangle\langle w| - \gamma L,$$

即"拉普拉斯矩阵加标记态投影"，并选 $\gamma = \frac 1N$。我们将在下节证明：此时与初态耦合的两个本征能级之差（能隙）为 $\frac{2}{\sqrt N}$，初态 $|s\rangle = \frac{1}{\sqrt N}\sum_x |x\rangle$ 在这个二维不变子空间内旋转，在时刻 $t \approx \frac{\pi}{2}\sqrt N$ 处几乎完全转移到 $|w\rangle$，随后在顶点基上测量即可。

### 完全图上的 CTQW

完全图 $K_N$ 的邻接矩阵为 $A = J_N - I_N$，拉普拉斯矩阵为 $L = (N-1)I - A$。我们逐步把搜索问题约化为二维问题。

第一步：识别不变子空间。记 $|r\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq w}|x\rangle$（非标记态的均匀叠加）。设 $\phi = \sum_x c_x |x\rangle$ 满足 $c_w = 0$ 且 $\sum_x c_x = 0$，即 $\phi \in \{w\}^\perp \cap \{s\}^\perp$。则 $(A\phi)_w = \sum_{x \neq w} c_x = 0$，而对 $y \neq w$ 有 $(A\phi)_y = \sum_{x \neq y, w} c_x = -c_y$，故 $A\phi = -\phi$，进而 $L\phi = (N-1)\phi - A\phi = N\phi$。于是子空间 $\{w\}^\perp \cap \{s\}^\perp$（维度 $N-2$）在 $H$ 下不变，本征值为 $-\gamma N$，且与初态 $|s\rangle$ 正交——演化永远不会泄漏到这个子空间。整个问题约化为二维空间 $\mathrm{span}\{|w\rangle, |r\rangle\}$。

第二步：写出有效哈密顿量。利用 $A|w\rangle = \sqrt{N-1}\,|r\rangle$ 以及 $A|r\rangle = \sqrt{N-1}\,|w\rangle + (N-2)|r\rangle$（$w$ 分量来自 $N-1$ 个邻居各贡献 $\frac{1}{\sqrt{N-1}}$，其余分量共 $N-2$ 个），我们得到

$$L|w\rangle = (N-1)|w\rangle - \sqrt{N-1}\,|r\rangle, \qquad L|r\rangle = |r\rangle - \sqrt{N-1}\,|w\rangle.$$

代入 $H = |w\rangle\langle w| - \gamma L$，得 $2\times 2$ 有效哈密顿量

$$H_{\text{eff}} = \begin{pmatrix} 1 - \gamma(N-1) & \gamma\sqrt{N-1} \\ \gamma\sqrt{N-1} & -\gamma \end{pmatrix}.$$

第三步：代入 $\gamma = \frac 1N$：

$$H_{\text{eff}} = \frac{1}{N}\begin{pmatrix} 1 & \sqrt{N-1} \\ \sqrt{N-1} & -1 \end{pmatrix}.$$

其迹为 0、行列式为 $-\frac{1}{N^2}(1 + N - 1) = -\frac 1N$，故本征值 $\lambda_\pm = \pm\frac{1}{\sqrt N}$，能隙为

$$\Delta = \frac{2}{\sqrt N} = O(1/\sqrt N).$$

第四步：精确求解演化。直接平方可以验证两个关键恒等式：

$$H_{\text{eff}}^2 = \frac{1}{N^2}\begin{pmatrix} 1 + N - 1 & \sqrt{N-1} - \sqrt{N-1} \\ \sqrt{N-1} - \sqrt{N-1} & N - 1 + 1 \end{pmatrix} = \frac{1}{N} I,$$

以及（利用 $|s\rangle = \frac{1}{\sqrt N}(|w\rangle + \sqrt{N-1}|r\rangle)$，故 $|w\rangle + \sqrt{N-1}|r\rangle = \sqrt N |s\rangle$）

$$H_{\text{eff}}|s\rangle = \frac{1}{N\sqrt N}\left[(1 + N - 1)|w\rangle + (\sqrt{N-1} - \sqrt{N-1})|r\rangle\right] = \frac{1}{\sqrt N}|w\rangle.$$

由 $H_{\text{eff}}^2 = \frac 1N I$，指数的偶数次幂为 $(\frac 1N)^k I$、奇数次幂为 $(\frac1N)^k H_{\text{eff}}$，于是指数可严格求和：

$$e^{-iH_{\text{eff}} t} = \cos\frac{t}{\sqrt N}\, I - i\sqrt N \sin\frac{t}{\sqrt N}\, H_{\text{eff}}.$$

作用到初态上并用上面的恒等式，交叉项恰好配成 Grover 型旋转：

$$|\psi(t)\rangle = \cos\frac{t}{\sqrt N}\,|s\rangle - i\sin\frac{t}{\sqrt N}\,|w\rangle,$$

$$P(w, t) = \sin^2\frac{t}{\sqrt N}.$$

取 $t^* = \frac{\pi}{2}\sqrt N$ 即得 $P(w, t^*) = 1$——精确的 Grover 搜索。这与 Grover 算法中 $\sin^2((2m+1)\theta)$、$\sin\theta = \frac{1}{\sqrt N}$ 的振荡完全同构：二维不变子空间内的旋转角速度由能隙 $\frac{2}{\sqrt N}$ 决定。

## DTQW 与 CTQW 的关系

定理（Childs, 2010）[2]：稀疏图上时间 $t$ 的连续时间行走可以用离散时间行走高效模拟。构造方法为：把图 $G$ 的每条边替换为长度 $\ell$ 的路径，得到细分图（subdivision graph）$G'$；在 $G'$ 上使用 Grover 硬币的 DTQW，其演化随细分长度 $\ell$ 的增大而任意精确地逼近 CTQW 在 $G$ 上的演化，所需顶点数只多项式增长。

这个结果（连同相对容易的反方向模拟）表明 CTQW 与 DTQW 在计算能力上等价，实际选择取决于实现便利性：

| 特性 | DTQW | CTQW |
|------|------|------|
| 硬币空间 | 需要 | 不需要 |
| 时间离散性 | 离散步 | 连续时间 |
| 量子门结构 | 自然适配 | 需要 Trotter 分解或 QSP |
| 实验实现 | 光子、离子阱 | 波导、超导 |
| 算法设计 | 丰富（图搜索、元素区分） | 简洁（哈密顿量驱动） |

## 量子行走算法的应用

### 元素区分问题（Element Distinctness）

给定 $N$ 个元素及两两比较的 Oracle，要求判断是否存在相等的元素对。经典随机算法需要 $\Omega(N)$ 次查询；Ambainis [4] 在"Johnson 图 + 碰撞对顶点"构成的碰撞图上构造 DTQW 搜索，复杂度为 $O(N^{2/3})$；Aaronson 与 Shi 证明了匹配的量子查询下界 $\Omega(N^{2/3})$，因此该算法是最优的。

### 图同构问题（部分情形）

CTQW 的跃迁概率由谱决定，因此同谱图（如某些参数相同的强正则图）无法用单点 CTQW 区分。带硬币的 DTQW 携带更多信息：对具有相同参数组 $(16, 6, 2, 2)$ 的 Shrikhande 图与 $4 \times 4$ 车图（Rook's graph）这类 1-WL（Weisfeiler–Leman）算法无法区分的同谱强正则图对，已有研究表明 DTQW 的相关统计量（例如行走矩阵的正支撑模式）能够区分二者。这一方向说明量子行走可作为经典图同构启发式的补充工具。

### 三角形发现（Triangle Finding）

在 $n$ 个顶点的图中判断是否存在三角形，经典算法在悲观意义下需要 $\Omega(n^2)$ 次边查询。Magniez、Santha 与 Szegedy（2007）用 DTQW 给出 $O(n^{13/10})$ 的量子算法，严格优于经典下界。

### 空间搜索

在 $N$ 个点的网格上搜索标记元素：经典随机行走需要 $O(N)$；完全图上的 Grover 搜索需要 $O(\sqrt N)$；在二维网格上，DTQW 搜索（Childs 与 Goldstone，2004）达到 $O(\sqrt N \log N)$——空间结构使量子行走几乎追平无结构搜索的效率。

## 理论推导

### DTQW 传播速度的证明

定理：一维线上 Hadamard DTQW 从 $|0\rangle \otimes |\phi\rangle$ 出发，$n$ 步后位置 $X_n$ 的方差满足

$$\mathrm{Var}(X_n) = n^2\left(\overline{v^2} - \bar v^2\right) + O(n),$$

其中权重平均定义为 $\overline{v^m} := \frac{1}{2\pi}\int_{-\pi}^{\pi}\sum_{\pm} |a_\pm(k)|^2\, v_\pm(k)^m\, dk$，$a_\pm(k) = \chi_\pm^\dagger(k)\,\tilde\psi(k, 0)$ 是初始条件在 $M(k)$ 的归一化本征矢 $\chi_\pm(k)$ 上的分量。特别地，由 $|v_\pm(k)| \le \frac{1}{\sqrt 2}$ 得 $\mathrm{Var}(X_n) \le \frac{n^2}{2} + O(n)$，且对一般初始硬币为 $\Theta(n^2)$；对称初态 $\frac{1}{\sqrt 2}(|0\rangle + i|1\rangle)$ 的精确常数为 $\mathrm{Var}(X_n) = \left(1 - \frac{1}{\sqrt 2}\right)n^2 + O(n) \approx 0.293\, n^2$。

证明分四步。

第一步（本征分解）。记本征相位 $\theta_+(k) = \omega(k)$、$\theta_-(k) = \pi - \omega(k)$，使 $\lambda_\pm = e^{i\theta_\pm}$。两本征值不会重合：若 $e^{i\omega} = -e^{-i\omega}$，则 $e^{2i\omega} = -1$，即 $\sin\omega = \pm 1$；但 $|\sin\omega| = |\sin k|/\sqrt 2 < 1$，矛盾。又因为 $M(k)$ 关于 $k$ 光滑且 $2\pi$ 周期，本征矢 $\chi_\pm(k)$ 可取为光滑周期函数。于是

$$\tilde\psi(k, n) = \sum_\pm a_\pm(k)\, e^{i n \theta_\pm(k)}\, \chi_\pm(k).$$

第二步（矩恒等式）。由定义 $\tilde\alpha_c(k) = \sum_x \alpha_{x,c} e^{ikx}$ 得 $-i\partial_k \tilde\alpha_c = \sum_x x\,\alpha_{x,c} e^{ikx}$，即位置算符在动量表象中是 $-i\partial_k$；它对 $2\pi$ 周期函数是厄米的。结合 Parseval 等式 $\sum_c \sum_x |\alpha_{x,c}|^2 = \frac{1}{2\pi}\int \tilde\psi^\dagger \tilde\psi\, dk$，我们有一、二阶矩

$$\langle X \rangle_n = \frac{1}{2\pi}\int_{-\pi}^{\pi} \tilde\psi^\dagger(k,n)\left(-i\partial_k\right)\tilde\psi(k,n)\, dk, \qquad \langle X^2 \rangle_n = \frac{1}{2\pi}\int_{-\pi}^{\pi} \left\|\partial_k \tilde\psi(k,n)\right\|^2 dk.$$

（第二式用 $\langle\psi|X^2|\psi\rangle = \|X|\psi\rangle\|^2$。）

第三步（求导与振荡项衰减）。对第一步的展开求导：

$$\partial_k \tilde\psi = \sum_\pm e^{in\theta_\pm}\left[\left(\partial_k a_\pm\right)\chi_\pm + a_\pm \left(\partial_k \chi_\pm\right) + i n\, \theta_\pm'\, a_\pm \chi_\pm\right].$$

两支之间的交叉项携带相位 $e^{in(\theta_+ - \theta_-)} = e^{in(2\omega - \pi)}$。其相位导数 $2\omega'(k)$ 仅在 $k = \pm\pi/2$ 处为零（孤立驻点），由驻相分析，这类振荡积分随 $n \to \infty$ 以 $O(n^{-1/2})$ 衰减；而 $\chi_\pm^\dagger \partial_k \chi_\pm$ 型的贝里联络项与 $n$ 无关。因此交叉项与联络项对 $\langle X \rangle_n$、$\langle X^2\rangle_n$ 分别只贡献 $O(1)$、$O(n)$ 的修正。

第四步（主阶）。保留首项：

$$\langle X \rangle_n = n \sum_\pm \overline{v_\pm} + O(1) = n\, \bar v + O(1), \qquad \langle X^2 \rangle_n = n^2\, \overline{v^2} + O(n),$$

相减即得定理。由 $|v_\pm(k)| \le \frac{1}{\sqrt 2}$ 有 $\overline{v^2} \le \frac 12$；只要两本征支上的权重 $|a_\pm(k)|^2$ 在正测度集上非零且速度非常数，就有 $\overline{v^2} - \bar v^2 > 0$，方差为 $\Theta(n^2)$。$\blacksquare$

### CTQW 搜索的能隙分析

定理：在 $N$ 顶点完全图上取 $H = |w\rangle\langle w| - \gamma L$，则 $\gamma = \frac 1N$ 时与初态 $|s\rangle$ 耦合的两个本征值为 $\pm\frac{1}{\sqrt N}$，能隙 $\Delta = \frac{2}{\sqrt N} = O(1/\sqrt N)$，对应的振荡周期为 $\pi\sqrt N$。

证明：上文"完全图上的 CTQW"已逐步给出推导，这里汇总核对。不变子空间约化依赖恒等式 $L\phi = N\phi$（$\phi \in \{w\}^\perp \cap \{s\}^\perp$），故正交补能级为 $-\gamma N = -1$，且与 $|s\rangle$ 解耦。二维块的有效哈密顿量在 $\gamma = \frac1N$ 时为 $\frac1N\begin{pmatrix} 1 & \sqrt{N-1} \\ \sqrt{N-1} & -1\end{pmatrix}$，其迹为 0、行列式为 $-\frac 1N$，特征多项式 $\lambda^2 - \frac 1N = 0$ 给出 $\lambda_\pm = \pm\frac{1}{\sqrt N}$，能隙 $\frac{2}{\sqrt N}$。能隙以 $N^{-1/2}$ 关闭，正是能级间振荡周期 $T_{\text{osc}} = \frac{2\pi}{\Delta} = \pi\sqrt N = O(\sqrt N)$ 的来源，与"演化到 $t^* = \frac{\pi}{2}\sqrt N$ 时成功概率为 1"一致。$\blacksquare$

### 量子行走的加速下界

无结构搜索的量子查询下界为 $\Omega(\sqrt N)$（Bennett–Bernstein–Brassard–Vazirani 类型的论证）。因此对无结构搜索问题，量子行走不能超越 Grover 的平方加速；任何更快的行走算法必然利用了图的结构。Szegedy（2004）的量子马尔可夫链搜索框架精确刻画了结构带来的加速：若马尔可夫链的经典击中时间（hitting time）为 $HT$，则相应量子行走的击中时间为 $O(\sqrt{HT})$，且这个平方加速在该黑箱模型下是最优的。元素区分问题的 $O(N^{2/3})$ 算法正是该框架的典型应用。

## 实验实现

### 光子量子行走

波导阵列是光子行走的典型平台：光子在耦合波导之间的隧穿自然实现连续时间行走，耦合强度与间距决定哈密顿量的边权。目前可实现的规模约为 $O(100)$ 个位置。

### 离子阱量子行走

囚禁离子把行走的两类自由度分开：内部态充当硬币，离散的运动模充当位置。该平台可实现 $O(10)$ 步、$O(50)$ 个位置的 DTQW，并可对退相干进行精确研究。

### 超导量子处理器

transmon 量子比特通过门电路实现 DTQW，硬币与移位分别对应单比特旋转与受控传输门。目前演示规模约为 $O(50)$ 个量子比特、$O(20)$ 步。

## 总结

量子行走是量子计算的基础原语，它把经典随机行走推广到量子领域，实现了从扩散到弹道传播的质变。离散时间量子行走（DTQW）通过硬币-位置空间的交替酉演化实现，其谱由色散关系 $\sin\omega(k) = \sin k/\sqrt 2$ 决定，群速度上界 $1/\sqrt 2$ 给出双峰位置 $\pm n/\sqrt 2$；连续时间量子行走（CTQW）直接由图的邻接或拉普拉斯矩阵驱动，完全图上的搜索通过二维不变子空间中的 Grover 型旋转达到 $O(\sqrt N)$。两者在计算能力上等价。量子行走不仅是设计量子算法的通用工具，也是理解 Qubitization、哈密顿量模拟等高级技术的直觉来源。

---

**参考文献：**

1. Kempe, J. (2003). *Quantum random walks: An introductory overview.* Contemporary Physics, 44(4), 307-327.
2. Childs, A. M. (2010). *On the relationship between continuous- and discrete-time quantum walk.* Communications in Mathematical Physics, 294(2), 581-603.
3. Farhi, E., Goldstone, J., & Gutmann, S. (2007). *A quantum algorithm for the Hamiltonian NAND tree.* arXiv:quant-ph/0702144.
4. Ambainis, A. (2004). *Quantum walk algorithm for element distinctness.* FOCS 2004.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)