量子行走（Quantum Walk）是经典随机行走的量子对应物，也是量子计算的基本原语之一。与经典随机行走的扩散性传播不同，量子行走利用量子叠加与干涉实现弹道式传播，速度平方级优于经典。它不仅为 Grover 搜索、图同构等算法提供了统一框架，也是哈密顿量模拟、量子搜索引擎和量子行走算法设计的基础。

经典随机行走回顾

在经典随机行走中，粒子位于图的某个顶点，每步以均匀概率跳转到相邻顶点：

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

$n$ 步后，粒子的位置分布服从扩散规律：$\sigma = O(\sqrt{n})$。

量子行走将概率替换为振幅，扩散替换为相干干涉，传播速度从 $O(\sqrt{n})$ 提升至 $O(n)$。

离散时间量子行走（DTQW）

定义与构造

离散时间量子行走定义在硬币-位置空间 $\mathcal{H}_C \otimes \mathcal{H}_P$：

• 位置空间 $\mathcal{H}_P$：图的顶点，基态 $\{|x\rangle : x \in V\}$
• 硬币空间 $\mathcal{H}_C$：决定行走方向，基态 $\{|c\rangle : c = 0, 1, \ldots, d-1\}$（$d$ 为最大度）

单步演化由两个酉操作组成：

1. 硬币翻转 $C$：在硬币空间上施加酉变换 $$C = I_P \otimes F_d$$ 其中 $F_d$ 是 $d$-维硬币算符，常用 Hadamard 硬币（$d = 2$）：$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

2. 条件转移 $S$：根据硬币状态移动到相邻顶点 $$S|x, c\rangle = |x_c, c\rangle$$ 其中 $x_c$ 是 $x$ 的第 $c$ 个邻居

总演化算符：$U = S \cdot (I_P \otimes F_d)$

初始态：通常为 $|\psi_0\rangle = |0\rangle_P \otimes |\phi\rangle_C$（硬币态 $|\phi\rangle$ 可选）

一维线上的量子行走

最简单的非平凡案例：粒子在整数格点 $\mathbb{Z}$ 上行走，硬币为二维（左/右）。

硬币算符：$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

条件转移： $$S|x, 0\rangle = |x+1, 0\rangle \quad (\text{向右})$$ $$S|x, 1\rangle = |x-1, 1\rangle \quad (\text{向左})$$

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

$n$ 步后粒子的位置分布 $P(x, n) = |\langle x| \psi(n)\rangle|^2$（对硬币求和），呈现双峰结构：概率集中在 $\pm n/\sqrt{2}$ 附近，而非经典随机行走的 $O(\sqrt{n})$ 扩散。

数学分析

令 $|\psi(n)\rangle = \sum_{x, c} \alpha_{x,c}(n) |x, c\rangle$。递推关系：

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

傅里叶分析：定义 $\tilde{\alpha}_c(k) = \sum_x \alpha_{x,c} e^{ikx}$，递推变为 $2 \times 2$ 矩阵乘法：

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

该矩阵的特征值为 $\lambda_\pm = \pm e^{i\arcsin(\sin k)}$。传播速度由群速度 $v_g = d\omega/dk = \cos k$ 决定，最大速度为 $1$（即每步移动 1 格），因此 $n$ 步后概率分布在 $\pm n$ 附近——线性传播。

图上的离散量子行走

对一般图 $G = (V, E)$，DTQW 的构造需要对每条边指定方向标记。

以 $d$-正则图为例（每个顶点的度为 $d$）：

• 硬币空间维度 $d$
• 硬币算符：$d$-维 Grover 扩散算符 $G_d = \frac{2}{d}J_d - I_d$（$J_d$ 为全 1 矩阵）
• 条件转移：$S|v, c\rangle = |v_c, c\rangle$（$v_c$ 为 $v$ 的第 $c$ 个邻居）

混合时间（Mixing Time）：量子行走达到均匀分布所需步数。对 $d$-正则图，量子行走的混合时间 $O(n \log n / d)$，而经典随机行走需要 $O(n^2 d)$。

连续时间量子行走（CTQW）

定义

连续时间量子行走直接由图的邻接矩阵（或拉普拉斯矩阵）驱动，无需硬币空间：

$$i\frac{d}{dt}|\psi(t)\rangle = H |\psi(t)\rangle$$

其中哈密顿量 $H$ 为：

• 邻接矩阵哈密顿量：$H = A$（$A_{xy} = 1$ 当且仅当 $(x,y) \in E$）
• 拉普拉斯矩阵哈密顿量：$H = L = D - A$（$D$ 为度矩阵）

演化算符：$U(t) = e^{-iHt}$

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

一维线上的 CTQW

$H = A$（无限线的邻接矩阵），特征态为平面波 $|k\rangle$，特征值 $E(k) = 2\cos k$。

从 $|0\rangle$ 出发：

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

其中 $J_x$ 是第一类贝塞尔函数。$|J_x(2t)|^2$ 在 $|x| \le 2t$ 范围内近似均匀，$|x| > 2t$ 时指数衰减——传播速度为 $O(t)$（线性）。

CTQW 的搜索算法

定理（Farhi et al., 1998）：在 $N$ 个顶点的图上，若存在唯一标记顶点 $|w\rangle$，CTQW 可在 $O(\sqrt{N})$ 时间内找到它——复现 Grover 搜索的复杂度。

实现：令 $H = -\gamma L + |w\rangle\langle w|$（拉普拉斯矩阵 + 标记态的投影），选择 $\gamma$ 使 $H$ 的两个最低能级之间有 $O(1/\sqrt{N})$ 的能隙，然后用 QPE 测量能隙。

完全图上的 CTQW

完全图 $K_N$（所有顶点两两相连），$A = J_N - I_N$。从 $|s\rangle$ 出发，由对称性，系统始终在 $\{|s\rangle, |s^\perp\rangle\}$（标记态和正交子空间）中演化。

有效哈密顿量限制为 $2 \times 2$：

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

演化时间 $t = \pi/(2\sqrt{N-1})$，测量得到 $|w\rangle$ 的概率 $\approx 1$——精确的 Grover 搜索。

DTQW 与 CTQW 的关系

定理（Childs, 2010）：任意 CTQW 可以精确模拟为某个 DTQW。

构造：给定图 $G$ 的邻接矩阵 $A$，构造边图 $G'$，DTQW 在 $G'$ 上的演化精确复现 CTQW 在 $G$ 上的演化。

意义：CTQW 和 DTQW 在计算能力上等价。实际选择取决于实现便利性：

量子行走算法的应用

元素区分问题（Element Distinctness）

给定 $N$ 个元素，判断是否存在重复。

• 经典：$\Omega(N)$（需要读取所有元素）
• DTQW（Ambainis, 2004）：$O(N^{2/3})$
• 最优量子算法：$O(N^{2/3})$（匹配下界）

方法：构造”碰撞图”，量子行走在图上搜索碰撞顶点。

图同构问题（部分情形）

量子行走对某些图类可区分经典算法无法区分的非同构图：

• 射影测量量子行走（PMQW）：测量 $n$ 步后的位置分布
• 对强正则图（如 Shrikhande 图 vs. $4 \times 4$ 方格图），量子行走可以区分，而经典 Weisfeiler-Leman 算法无法区分

三角形发现（Triangle Finding）

在 $n$ 个顶点的图中判断是否存在三角形。

• 经典：$\Omega(n^2)$
• DTQW（Magniez et al., 2007）：$O(n^{13/10})$（优于经典）

空间搜索

在 $N$ 个点的网格上搜索标记元素：

• 经典：$O(N)$
• Grover（完全图）：$O(\sqrt{N})$
• DTQW（二维网格）：$O(\sqrt{N}\log N)$

理论推导

DTQW 传播速度的证明

定理：一维线上 Hadamard DTQW 从 $|0, 0\rangle$ 出发，$n$ 步后位置方差 $\text{Var}(X) = O(n^2)$。

证明概要：

傅里叶空间中，每步演化乘以矩阵 $M(k) = \frac{1}{\sqrt{2}}\begin{pmatrix} e^{ik} & e^{ik} \\ e^{-ik} & -e^{-ik} \end{pmatrix}$。

$n$ 步后振幅为 $\tilde{\psi}(k, n) = M(k)^n \tilde{\psi}(k, 0)$。

$M(k)$ 的特征值 $\lambda_\pm = \pm e^{i\omega_\pm(k)}$，其中 $\omega_\pm(k) = \pm\arcsin(\sin k)$。

位置算符的期望值：

$$\langle X \rangle_n = \frac{1}{2\pi} \int_{-\pi}^{\pi} \sum_j |\tilde{\alpha}_j(k,n)|^2 \cdot v_j(k) \, dk$$

其中群速度 $v_j = d\omega_j/dk = \pm\cos k / \sqrt{1 - \sin^2 k} = \pm 1$（除 $k = \pm\pi/2$ 外）。

因此 $|\langle X \rangle_n| = O(n)$，方差 $O(n^2)$——线性传播。$\blacksquare$

CTQW 搜索的能隙分析

定理（Farhi et al.）：在 $N$ 顶点的完全图上，$H = -A + N|w\rangle\langle w|$，$H$ 的两个最低本征值之差（能隙）为 $\Delta = O(1/\sqrt{N})$。

证明：$H$ 在 $\{|w\rangle, |w^\perp\rangle\}$（标记态和其余态的均匀叠加）的子空间上限制为：

$$H_{\text{eff}} = \begin{pmatrix} N-1 & -(N-1) \\ -(N-1) & N-1 \end{pmatrix} + \text{修正}$$

对角化得本征值 $0$ 和 $2(N-1)$（近似）。更精确地，加入 $|w\rangle\langle w|$ 项后，最低能隙为 $O(1/\sqrt{N})$，对应振荡周期 $T = O(\sqrt{N})$。

量子行走的加速下界

定理（Szegedy, 2004）：对 $N$ 顶点的图，CTQW 的搜索时间下界为 $\Omega(\sqrt{N})$。

意义：量子行走不能比 Grover 搜索更快（对无结构搜索问题），任何加速都来自图的结构。

实验实现

光子量子行走

• 平台：波导阵列，光子在耦合波导中传播
• 实现：CTQW 自然实现（光子传播对应连续时间演化）
• 规模：$O(100)$ 个位置

离子阱量子行走

• 平台：囚禁离子的内部态 + 运动态
• 实现：DTQW，硬币为内部态，位置为运动模
• 规模：$O(10)$ 步，$O(50)$ 个位置

超导量子处理器

• 平台：transmon 量子比特
• 实现：DTQW 通过量子门电路
• 规模：$O(50)$ 量子比特，$O(20)$ 步

总结

量子行走是量子计算的基础原语，将经典随机行走推广到量子领域，实现从扩散到弹道传播的质变。离散时间量子行走（DTQW）通过硬币-位置空间的交替演化实现，连续时间量子行走（CTQW）直接由图的哈密顿量驱动，两者在计算能力上等价。量子行走不仅是设计量子算法的通用工具，也是理解 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. (1998). A quantum algorithm for the Hamiltonian NAND tree. arXiv:quant-ph/0702144.
4. Ambainis, A. (2004). Quantum walk algorithm for element distinctness. FOCS 2004.