4. 离散时间量子游走

离散时间量子游走（Discrete-Time Quantum Walk, DTQW）是经典随机游走在量子力学框架下的直接推广。经典随机游走中，行走者每一步以概率选择向左或向右；而在量子版本中，行走者拥有一个内部的“硬币”量子态，硬币的翻转由硬币算子实现，位置的移动由移位算子实现，两者交替作用构成完整的游走算子。理解这三个算子的定义与作用顺序，是掌握离散时间量子游走的关键。

硬币算子：产生量子叠加

硬币算子是作用在硬币空间上的幺正算子。以一维情形为例，硬币空间是二维的，基态记为 |0⟩ 和 |1⟩，分别对应“向左”和“向右”的方向倾向。最常用的硬币算子是 Hadamard 算子：

H = (1/√2) [[1,  1],
             [1, -1]]

它作用在硬币基态上得到：H|0⟩ = (|0⟩+|1⟩)/√2，H|1⟩ = (|0⟩−|1⟩)/√2。与经典随机游走“以 1/2 概率选方向”不同，硬币算子并不立即产生概率分布，而是产生方向态的量子叠加。正是这种叠加，使得不同路径之间可以发生干涉。除 Hadamard 硬币外，常用的还有 Grover 硬币、Fourier 硬币等，不同硬币会改变游走的扩散速度与分布形状。

移位算子：条件平移

移位算子根据硬币态控制行走者位置的移动。一维移位算子 S 定义为：

S |x⟩|0⟩ = |x−1⟩|0⟩
S |x⟩|1⟩ = |x+1⟩|1⟩

即硬币为 |0⟩ 时位置减一，硬币为 |1⟩ 时位置加一。这里约定位置坐标 x 取整数，向右为正方向。移位算子是置换算子，因此也是幺正的。它把硬币的内部状态与外部位置耦合起来，是量子游走区别于单纯量子叠加的核心机制。

游走算子：一步演化

一步游走算子由硬币算子与移位算子复合而成，通常写作 W = S·(I⊗H)，其中 I 是位置空间上的恒等算子。作用顺序是：先翻转硬币，再按硬币结果移位。若初始态为 |ψ₀⟩ = |0⟩|0⟩（位置 0、硬币 |0⟩），则一步后：

W|0⟩|0⟩ = S·(I⊗H)|0⟩|0⟩
        = S·(|0⟩+|1⟩)/√2 ⊗ |0⟩
        = (|−1⟩|0⟩ + |1⟩|1⟩)/√2

可见一步之后，行走者同时出现在位置 −1 和 +1，且硬币态与位置纠缠。经过 t 步，状态为 Wᵗ|ψ₀⟩。由于 W 是幺正的，演化保持总概率为 1，但位置分布不再是简单的二项分布，而呈现出干涉条纹。

一维与高维网格上的演化

在一维整数线上，位置空间为 {…, −2, −1, 0, 1, 2, …}，硬币空间为二维。若把位置截断到有限范围 [−N, N] 并采用周期性边界，则可用 2(2N+1) 维向量表示量子态，游走算子为幺正矩阵。实际数值模拟中，常用 Python/NumPy 构造该矩阵并迭代作用。

推广到 d 维网格时，硬币空间维度变为 2d，每个方向对应一对基态。例如二维方格上，硬币基态可取 |→⟩、|←⟩、|↑⟩、|↓⟩，移位算子分别沿 x 或 y 方向平移一格。硬币算子则作用在 2d 维硬币空间上，常用 Grover 硬币：C = 2|s⟩⟨s| − I，其中 |s⟩ 是所有方向态的等权叠加。高维游走同样保持幺正性，但干涉结构更复杂，扩散行为也更丰富。

与经典随机游走的对比

经典随机游走中，行走者每步以概率 p 向左、1−p 向右，位置分布满足二项分布，标准差随步数 t 增长为 O(√t)。而离散时间量子游走由于量子干涉，位置分布的标准差随 t 线性增长，即 O(t)，这一现象称为弹道扩散（ballistic diffusion）。这是量子游走最重要的特征之一，也是其在量子搜索、图遍历等算法中具有加速潜力的根源。

总结来说，离散时间量子游走由硬币算子、移位算子以及二者复合而成的游走算子共同定义。硬币算子负责产生方向叠加，移位算子负责条件平移，游走算子描述一步完整演化。一维与高维网格上的区别主要在于硬币空间维度和移位方向数。与经典随机游走相比，量子游走的核心优势在于干涉带来的弹道扩散，这为后续图问题求解算法提供了加速基础。