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

量子行走（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 硬币

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

完全图上的 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\) 有效哈密顿量

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

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

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

其迹为 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).\]

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

\[\begin{split}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,\end{split}\]

以及（利用 \(|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.