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

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

本课知识点

  1. 经典随机行走的扩散极限——能写出经典随机行走的转移概率与 \(n\) 步后的标准差 \(\sigma = O(\sqrt{n})\)，并解释覆盖 \(O(n)\) 距离需要 \(O(n^2)\) 步这一扩散规律。

  2. DTQW 的硬币-移位构造——能写出硬币-位置联合空间、硬币算符与移位算符的定义并组合出单步演化 \(U = S \cdot (I_P \otimes F_d)\)，逐项验证 Grover 硬币 \(G_d\) 的"关于均值翻转"作用。

  3. 一维行走的振幅递推与双峰分布——能推导一维线上振幅的递推关系并手工计算前两步的分布，解释支撑约束 \(|x| \le n\)、\(x \equiv n \pmod 2\) 与初始硬币对分布对称性的影响。

  4. 色散关系与群速度——能用傅里叶变换把一维行走解耦为 \(2\times 2\) 块迭代，推导色散关系 \(\sin\omega(k) = \sin k/\sqrt{2}\)、群速度 \(v_\pm(k) = \pm\frac{\cos k}{\sqrt{1+\cos^2 k}}\) 及其上界 \(\frac{1}{\sqrt{2}}\)，并据此解释双峰位置 \(\pm\frac{n}{\sqrt{2}}\)。

  5. 图上的 DTQW 与混合时间——能解释 DTQW 瞬时分布为何一般不收敛，写出时间平均分布 \(\bar{P}_T(x)\) 的定义，并比较环图上 DTQW 的 \(O(n\log n)\) 与经典行走的 \(\Theta(n^2)\)。

  6. CTQW 的定义与哈密顿量——能写出 CTQW 的演化方程与 \(H = A\)、\(H = L = D - A\) 两种哈密顿量取法，并证明 \(d\) 正则图上两者只差时间反演与整体相位、位置分布相同。

  7. 一维 CTQW 的贝塞尔函数解——能用平面波本征态与 Jacobi–Anger 展开推导 \(|\psi(t)\rangle = \sum_x (-i)^x J_x(2t)\,|x\rangle\) 与 \(P(x,t) = J_x(2t)^2\)，并说明光锥边界 \(|x| \approx 2t\) 的线性传播。

  8. 完全图上的 CTQW 搜索——能把完全图搜索哈密顿量约化到二维不变子空间，推导能隙 \(\Delta = \frac{2}{\sqrt{N}}\) 与成功概率 \(P(w,t) = \sin^2\frac{t}{\sqrt{N}}\)，并计算成功概率为 1 的时刻 \(t^* = \frac{\pi}{2}\sqrt{N}\)。

经典随机行走回顾

在经典随机行走（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 硬币

\[\begin{split}H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix},\end{split}\]

以及 \(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{split}\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},\end{split}\]

且 \(\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\)，随后在顶点基上测量即可。

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【经典随机行走的扩散极限】（→ 经典随机行走回顾）

  1. 基础：一维经典随机行走每步以 \(\frac{1}{2}\) 概率向左或向右移动一格。把 \(n\) 步后的位置写成独立随机变量之和 \(X_n = \sum_{i=1}^{n}\xi_i\)（\(\xi_i = \pm 1\)），计算 \(\mathrm{Var}(X_n)\) 并写出标准差。

  2. 进阶：要让涨落的标准差达到 \(L\)，经典行走大约需要多少步？结合正文"覆盖 \(O(n)\) 距离需要 \(O(n^2)\) 步"与量子行走的弹道式传播（\(n\) 步内即可走远 \(O(n)\)），比较两者所需步数的量级关系。

提示：\(\mathrm{Var}(\xi_i) = 1\)；弹道式传播对应正文方差定理中 \(\mathrm{Var}(X_n) = \Theta(n^2)\)，即标准差 \(\Theta(n)\)。

练习 2【DTQW 的硬币-移位构造】（→ 定义与构造）

  1. 基础：写出 \(d\) 维 Grover 硬币 \(G_d = \frac{2}{d}J_d - I_d\) 分别作用于均匀硬币态 \(|s_d\rangle\) 与任意满足 \(\langle s_d|v\rangle = 0\) 的态 \(|v\rangle\) 的结果，并说明移位算符 \(S\) 为酉算符的条件。

  2. 进阶：利用 \(J_d^2 = d\,J_d\) 证明 \(G_d\) 是酉矩阵。

提示：\(G_d\) 是实对称矩阵，直接展开 \(G_d^2 = \frac{4}{d^2}J_d^2 - \frac{4}{d}J_d + I_d\)。

练习 3【一维行走的振幅递推与双峰分布】（→ 一维线上的量子行走）

  1. 基础：从初态 \(|0\rangle_P \otimes |0\rangle_C\) 出发，用正文递推式依次算出 1 步与 2 步后的全部振幅，写出 \(P(x,1)\) 与 \(P(x,2)\) 并验证各自总和为 1。

  2. 进阶：对 \(n\) 作归纳证明：\(n\) 步后振幅只在满足 \(|x| \le n\) 且 \(x \equiv n \pmod 2\) 的位置上非零。

  3. 基础：写出经典随机行走 2 步后的位置分布，说明它与第 1 题的 \(P(x,2)\) 相同——量子与经典的差异要到第 3 步起才通过干涉体现在概率上。

提示：归纳时注意递推式右端只取时刻 \(n\) 的 \((x-1,\cdot)\) 与 \((x+1,\cdot)\)，而 \(x \mp 1\) 的奇偶性每步翻转一次。

练习 4【色散关系与群速度】（→ 数学分析）

  1. 基础：验证 \(M(k)\) 的本征值 \(\lambda_\pm(k) = \frac{i\sin k \pm \sqrt{1+\cos^2 k}}{\sqrt{2}}\) 模长为 1。

  2. 进阶：由色散关系 \(\sin\omega(k) = \frac{\sin k}{\sqrt{2}}\) 求 \(\omega'(k)\)，推导群速度 \(v_\pm(k) = \pm\frac{\cos k}{\sqrt{1+\cos^2 k}}\)，并求 \(|v_\pm|\) 的最大值及对应的 \(k\)。

提示：两边对 \(k\) 求导得 \(\omega' = \frac{\cos k}{\sqrt{2}\cos\omega}\)，再代入 \(\cos\omega = \sqrt{\frac{1+\cos^2 k}{2}}\)；\(|v_\pm|\) 在 \(k = 0\) 与 \(k = \pi\) 处取最大值。

练习 5【图上的 DTQW 与混合时间】（→ 图上的离散量子行走）

  1. 基础：写出时间平均分布 \(\bar{P}_T(x) = \frac{1}{T}\sum_{n<T} P(x,n)\) 的定义，说明 DTQW 瞬时分布为何一般不收敛，并比较 \(n\) 顶点环图上经典行走的混合时间 \(\Theta(n^2)\) 与 DTQW 时间平均分布接近均匀所需步数。

  2. 进阶：在单个量子比特上反复作用 Hadamard 门、初态取 \(|0\rangle\)：写出偶数步与奇数步的态，证明瞬时分布不收敛，并求时间平均分布 \(\bar{P}(0)\) 与 \(\bar{P}(1)\)。

提示：\(H^2 = I\)，态在 \(|0\rangle\) 与 \(|+\rangle\) 之间交替；时间平均分布等于这两个态的分布的平均。

练习 6【CTQW 的定义与哈密顿量】（→ 定义）

  1. 基础：写出 CTQW 的演化方程 \(i\frac{d}{dt}|\psi(t)\rangle = H|\psi(t)\rangle\)、\(U(t) = e^{-iHt}\) 与两种哈密顿量 \(H = A\)、\(H = L = D - A\) 的定义；对 \(N\) 顶点完全图，用 \(J_N\) 与 \(I_N\) 写出 \(A\) 与 \(L\)。

  2. 进阶：证明在 \(d\) 正则图上 \(L = dI - A\)，两种哈密顿量的本征矢相同、本征值满足 \(\mu_j = d - \eta_j\)，且 \(e^{-iLt} = e^{-idt}e^{+iAt}\)，因此两种行走的位置分布完全相同。

提示：\(D = dI\) 时 \(L\) 与 \(A\) 只差单位矩阵的倍数；模长为 1 的整体相位 \(e^{-idt}\) 不影响任何测量概率。

练习 7【一维 CTQW 的贝塞尔函数解】（→ 一维线上的 CTQW）

  1. 基础：验证平面波 \(|k\rangle = \sum_x e^{ikx}|x\rangle\) 是无限线邻接矩阵的本征态并求本征值；写出 \(t\) 时刻位置 \(x\) 处的概率 \(P(x,t)\)。

  2. 进阶：证明谱分解恒等式 \(\frac{1}{2\pi}\int_{-\pi}^{\pi} e^{ikx}\,dk = \delta_{x,0}\)（\(x\) 为整数），从而 \(|0\rangle = \frac{1}{2\pi}\int_{-\pi}^{\pi}|k\rangle\,dk\)；并说明相位因子 \((-i)^x\) 为何不影响 \(P(x,t) = J_x(2t)^2\)。

提示：\(x \ne 0\) 时取原函数 \(\frac{e^{ikx}}{ix}\)，其端点值依赖 \(e^{\pm i\pi x} = (-1)^x\)；\(|(-i)^x| = 1\)。

练习 8【完全图上的 CTQW 搜索】（→ 完全图上的 CTQW）

  1. 基础：写出 \(\gamma = \frac{1}{N}\) 时的有效哈密顿量 \(H_{\text{eff}}\)，求其本征值与能隙；取 \(N = 100\)，计算成功概率达到 1 的时刻 \(t^*\)。

  2. 进阶：验证 \(H_{\text{eff}}^2 = \frac{1}{N}I\) 与 \(H_{\text{eff}}|s\rangle = \frac{1}{\sqrt{N}}|w\rangle\)，把 \(e^{-iH_{\text{eff}}t}\) 按指数的奇偶幂分组求和，推导 \(|\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}}\)。

提示：偶数次幂为 \((\frac{1}{N})^k I\)、奇数次幂为 \((\frac{1}{N})^k H_{\text{eff}}\)，分别配成 \(\cos\frac{t}{\sqrt{N}}\) 与 \(\sqrt{N}\sin\frac{t}{\sqrt{N}}\) 的级数。

参考文献：

  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.