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

量子行走（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$ 为最大度）

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

硬币翻转 $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}$
条件转移 $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 在计算能力上等价。实际选择取决于实现便利性：

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

代码示例（uniqc 实现）

类型：完整算法演示。下面在 $\mathbb{Z}_{16}$（16 顶点环）上构造一个 4 位置比特 + 1 硬币比特的 Hadamard 离散量子行走，并与经典对称随机行走对比标准差的增长率，验证”弹道（$\sigma \sim T$）vs 扩散（$\sigma \sim \sqrt{T}$）“的关键差异。

import numpy as np
from uniqc import Circuit

N_POS_QUBITS = 4
N_POS = 2 ** N_POS_QUBITS       # 16
COIN_QUBIT = N_POS_QUBITS       # q[4]

def increment(circ, pos_qubits, ctrl):
    """对 pos_qubits 表示的整数做 (+1) mod 2^n，额外受控于 ctrl 比特。"""
    n = len(pos_qubits)
    for k in range(n - 1, 0, -1):
        circ.set_control(pos_qubits[:k] + [ctrl])
        circ.x(pos_qubits[k])
        circ.unset_control()
    circ.set_control([ctrl]); circ.x(pos_qubits[0]); circ.unset_control()

def decrement(circ, pos_qubits, ctrl):
    """(-1) mod 2^n，increment 的逆。"""
    circ.set_control([ctrl]); circ.x(pos_qubits[0]); circ.unset_control()
    for k in range(1, len(pos_qubits)):
        circ.set_control(pos_qubits[:k] + [ctrl])
        circ.x(pos_qubits[k])
        circ.unset_control()

def build_walk_circuit(n_steps, start=8):
    circ = Circuit()
    circ.identity(N_POS_QUBITS)  # 占满 5 个量子比特
    for q in range(N_POS_QUBITS):
        if (start >> q) & 1:
            circ.x(q)
    pos_qubits = list(range(N_POS_QUBITS))
    for _ in range(n_steps):
        circ.h(COIN_QUBIT)
        # coin=0 → 右移：先翻硬币使受控生效
        circ.x(COIN_QUBIT)
        increment(circ, pos_qubits, ctrl=COIN_QUBIT)
        circ.x(COIN_QUBIT)
        # coin=1 → 左移
        decrement(circ, pos_qubits, ctrl=COIN_QUBIT)
    return circ

def quantum_distribution(T, start=8):
    U = build_walk_circuit(T, start).get_matrix()
    psi = U[:, 0]  # 第一列 = U|0...0⟩
    probs = np.abs(psi) ** 2
    pos_probs = np.zeros(N_POS)
    for idx in range(len(probs)):
        pos_probs[idx & (N_POS - 1)] += probs[idx]
    return pos_probs

def classical_distribution(T, start=8):
    p = np.zeros(N_POS); p[start] = 1.0
    for _ in range(T):
        p = 0.5 * np.roll(p, 1) + 0.5 * np.roll(p, -1)
    return p

def sigma(p, mean):
    xs = np.arange(N_POS)
    d = np.minimum(np.abs(xs - mean), N_POS - np.abs(xs - mean))
    return float(np.sqrt(np.sum(p * d ** 2)))

start = 8
print(f'{"步数 T":>6}{"量子 σ":>10}{"经典 σ":>10}{"σ_q / σ_c":>12}{"σ_q / T":>10}')
for T in (2, 4, 6, 8):
    pq, pc = quantum_distribution(T, start), classical_distribution(T, start)
    sq, sc = sigma(pq, start), sigma(pc, start)
    print(f'{T:>6d}{sq:>10.4f}{sc:>10.4f}{sq / sc:>12.4f}{sq / T:>10.4f}')

# 直方图
T = 6
pq = quantum_distribution(T, start)
print(f'\nT ={T}步后量子位置分布（环面，x_0 = 8）：')
for x in range(N_POS):
    print(f'  x={x:>2}:{pq[x]:.4f}{"█" * int(round(pq[x] * 80))}')

运行结果：

  步数 T       量子 σ       经典 σ    σ_q / σ_c    σ_q / T
     2     1.4142     1.4142       1.0000     0.7071
     4     2.2361     2.0000       1.1180     0.5590
     6     3.3541     2.4495       1.3693     0.5590
     8     4.3732     2.8284       1.5462     0.5467

T = 6 步后量子位置分布（环面，x_0 = 8）：
  x= 0: 0.0000
  x= 1: 0.0000
  x= 2: 0.0156  █
  x= 3: 0.0000
  x= 4: 0.1562  ████████████
  x= 5: 0.0000
  x= 6: 0.0781  ██████
  x= 7: 0.0000
  x= 8: 0.1250  ██████████
  x= 9: 0.0000
  x=10: 0.2031  ████████████████
  x=11: 0.0000
  x=12: 0.4062  ████████████████████████████████
  x=13: 0.0000
  x=14: 0.0156  █
  x=15: 0.0000

观察：

弹道传播：$\sigma_q / T$ 趋于一个常数（~0.55，与解析群速度 $\cos k|_{k = \pi/4} = 1/\sqrt{2}$ 一致），即 $\sigma_q \propto T$；
量子 vs 经典加速比：$\sigma_q / \sigma_c$ 由 $1$（$T = 2$ 时来不及发展量子干涉）渐增到 $\sim T^{1/2}$，验证了文中”传播速度从 $O(\sqrt{n})$ 提升至 $O(n)$”；
奇偶守恒 + 不对称分布：所有奇数位置概率严格为 $0$（一步只能改变 1 个奇偶性，因此 $T = 6$ 步后只能到偶数位置）；分布明显右偏（$x = 12$ 概率最大），是 Hadamard 硬币 + $|coin = 0\rangle$ 初始化的标志性”对称破缺”——文献中常用初始硬币态 $(|0\rangle + i|1\rangle)/\sqrt{2}$ 来恢复左右对称。

量子行走算法的应用

元素区分问题（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、哈密顿量模拟等高级技术的直觉来源。

参考文献：

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

返回目录：量子计算算法教程系列

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

经典随机行走回顾

离散时间量子行走（DTQW）

定义与构造

一维线上的量子行走

数学分析

图上的离散量子行走

连续时间量子行走（CTQW）

定义

一维线上的 CTQW

CTQW 的搜索算法

完全图上的 CTQW

DTQW 与 CTQW 的关系

代码示例（uniqc 实现）

量子行走算法的应用

元素区分问题（Element Distinctness）

图同构问题（部分情形）

三角形发现（Triangle Finding）

空间搜索

理论推导

DTQW 传播速度的证明

CTQW 搜索的能隙分析

量子行走的加速下界

实验实现

光子量子行走

离子阱量子行走

超导量子处理器

总结

Schrödingerization 详解：将经典微分方程量子化的新方法

QAOA 算法详解：量子近似优化算法

agony

Comments | NOTHING

经典随机行走回顾

离散时间量子行走（DTQW）

定义与构造

一维线上的量子行走

数学分析

图上的离散量子行走

连续时间量子行走（CTQW）

定义

一维线上的 CTQW

CTQW 的搜索算法

完全图上的 CTQW

DTQW 与 CTQW 的关系

代码示例（uniqc 实现）

量子行走算法的应用

元素区分问题（Element Distinctness）

图同构问题（部分情形）

三角形发现（Triangle Finding）

空间搜索

理论推导

DTQW 传播速度的证明

CTQW 搜索的能隙分析

量子行走的加速下界

实验实现

光子量子行走

离子阱量子行走

超导量子处理器

总结

Schrödingerization 详解：将经典微分方程量子化的新方法

QAOA 算法详解：量子近似优化算法

agony

Comments | NOTHING

你想搜索什么...