量子行走

量子行走（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}{\mathrm{deg}(x)},y\in N(x),$

其中 $N(x)$ 是 $x$ 的邻居集合，$\mathrm{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⟩:x\in V\}$；
• 硬币空间（coin space）${\mathcal{H}}_C$：编码行走方向的内部自由度，基态为 $\{|c⟩:c=0,1,\dots ,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}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),$

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

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

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

$G_d|s_d⟩=|s_d⟩,G_d|v⟩=-|v⟩(v\perp |s_d⟩),$

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

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

$S|x,c⟩=|x_c,c⟩,$

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

总演化算符为

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

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

$|{\psi }_0⟩=|0{⟩}_P\otimes |\varphi {⟩}_C,$

其中硬币态 $|\varphi {⟩}_C$ 的选择会影响分布的左右对称性（见下节）。

一维线上的量子行走

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

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

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

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

${\beta }_{x,0}=\frac{1}{\sqrt{2}}\left({\alpha }_{x,0}+{\alpha }_{x,1}\right),{\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(\mathrm{mod}2)$（每步恰好移动一格）。数值模拟显示 $P(x,n)$ 呈双峰结构：概率集中在 $\pm \frac{n}{\sqrt{2}}$ 附近；若初始硬币为对称态 $\frac{1}{\sqrt{2}}(|0⟩+i|1⟩)$，双峰等高，而初始硬币 $|0⟩$ 则给出左峰较高的不对称分布。这与经典随机行走始终停留在原点附近的单峰形成鲜明对比。下一节我们用傅里叶分析严格解释双峰位置 $\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$ 块的迭代：

$\left(\begin{array}{c}{\tilde{\alpha }}_0(k,n+1)\\ {\tilde{\alpha }}_1(k,n+1)\end{array}\right)=M(k)\left(\begin{array}{c}{\tilde{\alpha }}_0(k,n)\\ {\tilde{\alpha }}_1(k,n)\end{array}\right),M(k)=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{e}^{ik}& e^{ik}\\ e^{-ik}& -e^{-ik}\end{array}\right),$

且 $\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 kI+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 kI+\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=\Vert \vec{b}{\Vert }^{2}I=(1+{\cos }^{2}k)I$，从而

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

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

由于 $\vec{b}\cdot \vec{\sigma }$ 的本征值为 $\pm \Vert \vec{b}\Vert =\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)},{\lambda }_{-}(k)=-e^{-i\omega (k)},$

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

$\sin \omega (k)=\frac{\sin k}{\sqrt{2}},\cos \omega (k)=\sqrt{\frac{1+{\cos }^{2}k}{2}},\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 }^{\prime }(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⟩=|v_c,c⟩$，其中 $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)⟩=H|\psi (t)⟩,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)⟩=|s⟩$。

一维线上的 CTQW

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

$|\psi (t)⟩=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }{e}^{-i2t\cos k}|k⟩dk.$

把它展开到位置基上，需要计算 $\frac{1}{2\pi }{\int }_{-\pi }^{\pi }{e}^{-i2t\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)⟩={\sum }_x(-i{)}^x{J}_x(2t)|x⟩,$

其中用了 $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⟩$，CTQW 可以在 $O(\sqrt{N})$ 时间内以接近 1 的概率找到它——复现 Grover 搜索的复杂度。

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

$H=|w⟩⟨w|-\gamma L,$

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

完全图上的 CTQW

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

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

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

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

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

$H_{\text{eff}}=\left(\begin{array}{cc}1-\gamma (N-1)& \gamma \sqrt{N-1}\\ \gamma \sqrt{N-1}& -\gamma \end{array}\right).$

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

$H_{\text{eff}}=\frac{1}{N}\left(\begin{array}{cc}1& \sqrt{N-1}\\ \sqrt{N-1}& -1\end{array}\right).$

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

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

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

$H_{\text{eff}}^2=\frac{1}{N^2}\left(\begin{array}{cc}1+N-1& \sqrt{N-1}-\sqrt{N-1}\\ \sqrt{N-1}-\sqrt{N-1}& N-1+1\end{array}\right)=\frac{1}{N}I,$

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

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

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

$e^{-i{H}_{\text{eff}}t}=\cos \frac{t}{\sqrt{N}}I-i\sqrt{N}\sin \frac{t}{\sqrt{N}}{H}_{\text{eff}}.$

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

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

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

取 $t^{\ast }=\frac{\pi }{2}\sqrt{N}$ 即得 $P(w,t^{\ast })=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^{\prime }$；在 $G^{\prime }$ 上使用 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⟩\otimes |\varphi ⟩$ 出发，$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 }^{†}(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⟩+i|1⟩)$ 的精确常数为 $\mathrm{Var}(X_n)=\left(1-\frac{1}{\sqrt{2}}\right)n^2+O(n)\approx 0.293n^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^{in{\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 }}^{†}\tilde{\psi }dk$，我们有一、二阶矩

$⟨X{⟩}_n=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }{\tilde{\psi }}^{†}(k,n)\left(-i{\partial }_k\right)\tilde{\psi }(k,n)dk,⟨X^2{⟩}_n=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }{\Vert {\partial }_k\tilde{\psi }(k,n)\Vert }^{2}dk.$

（第二式用 $⟨\psi |X^2|\psi ⟩=\Vert X|\psi ⟩{\Vert }^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)+in{\theta }_{\pm }^{\prime }{a}_{\pm }{\chi }_{\pm }\right].$

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

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

$⟨X{⟩}_n=n{\sum }_{\pm }\overline{v_{\pm }}+O(1)=n\bar{v}+O(1),⟨X^2{⟩}_n=n^2\overline{v^2}+O(n),$

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

CTQW 搜索的能隙分析

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

证明：上文”完全图上的 CTQW”已逐步给出推导，这里汇总核对。不变子空间约化依赖恒等式 $L\varphi =N\varphi$（$\varphi \in \{w{\}}^{\perp }\cap \{s{\}}^{\perp }$），故正交补能级为 $-\gamma N=-1$，且与 $|s⟩$ 解耦。二维块的有效哈密顿量在 $\gamma =\frac{1}{N}$ 时为 $\frac{1}{N}\left(\begin{array}{cc}1& \sqrt{N-1}\\ \sqrt{N-1}& -1\end{array}\right)$，其迹为 0、行列式为 $-\frac{1}{N}$，特征多项式 ${\lambda }^2-\frac{1}{N}=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^{\ast }=\frac{\pi }{2}\sqrt{N}$ 时成功概率为 1”一致。$■$

量子行走的加速下界

无结构搜索的量子查询下界为 $\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.

---

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch06-scientific-computing/quantum-walk-tutorial
• 内容遵循 CC BY-NC-SA 4.0 许可协议