出处已验证第 3 级
量子行走
量子行走是经典随机行走的量子版本：行走者以位置叠加态移动，路径间的干涉使其扩散比经典行走快二次方（距离 ~ t 对比 ~ sqrt(t)）。
这是什么意思
离散时间量子行走（Aharonov, Davidovich, Zagury, 1993）有位置寄存器和硬币量子比特。每步先对硬币施加操作（常为阿达马门），再按硬币状态条件移位。行走途中不测量，各路径振幅发生干涉，位置分布呈弹道式扩散（标准差正比于t）且为双峰形。连续时间量子行走直接按图的邻接结构给出的哈密顿量演化。量子行走是空间搜索、元素相异性等算法的设计工具，在合适的图上可实现通用量子计算。生活类比
普通行走者抛硬币后向左或向右走一步；量子行走者用魔法硬币同时朝两边走 -- 之后重叠的路径混合在一起，离起点远得多。
像池塘涟漪与游荡的蚂蚁：蚂蚁（经典行走）慢慢挪，涟漪波前（量子行走）以恒定速度向外冲。
常见误解
- 量子行走不只是随机性来自量子的随机行走 -- 路径间干涉产生完全不同的双峰、弹道式分布。
- 每步都测量位置会破坏量子行为 -- 反复测量使叠加坍缩，退回经典随机行走。
- 二次方扩散优势不会自动变成所有问题的量子加速 -- 算法优势要逐个问题证明。
要点总结
- 离散时间量子行走 = 硬币操作 + 条件移位，中途不测量。
- 弹道式扩散：标准差 ~ t（经典为 ~ sqrt(t)）。
- 支撑空间搜索、元素相异性等算法；在合适的图上计算通用。
检验你的理解
离散时间量子行走的扩散（标准差）随步数t如何增长？
- A.像经典行走一样正比于sqrt(t)
- B.正比于t（弹道式）
- C.完全不扩散
- D.正比于t^2
查看答案
答案: B. 正比于t（弹道式）
原因: 路径间干涉使标准差正比于t，而经典随机行走为sqrt(t)。
先修概念
一次文献: Aharonov, Davidovich, Zagury, Quantum random walks, Phys. Rev. A 48, 1687 (1993), doi:10.1103/PhysRevA.48.1687
Graded 2026-07-10 (human sign-off): established per Aharonov, Davidovich, Zagury, Phys. Rev. A 48, 1687 (1993).