量子行走与搜索：离散/连续时间行走、加速与图搜索

经典随机游走：
  位置：一个概率分布（我在每个节点的概率）
  演化：按转移矩阵随机移动
  应用：PageRank、采样、搜索、扩散

量子行走：
  位置：一个叠加态（我「同时」在所有节点的振幅）
  演化：按酉算符相干移动
  应用：搜索、元素不同性、模拟、算法加速

- 相干性：量子行走同时探索所有路径 → 干涉效应
- 加速：某些搜索问题从 O(N) 加速到 O(√N)（二次加速）
- 统一性：Grover 搜索可看作「行走搜索」的特例
- 模拟：量子行走能高效模拟物理中的扩散/传输
→ 量子行走是「算法加速 + 物理模拟」的双料框架

系统状态：|位置⟩ ⊗ |硬币⟩
  位置：我在哪个节点
  硬币：决定下一步方向（|左⟩ / |右⟩ / 图上的方向）

一步 = 两个算子：
  硬币算子 C：翻转硬币叠加（Hadamard/任意酉）
  移位算子 S：按硬币方向移动位置

    |ψ⟩ → C 翻转硬币 → S 移动位置 → 下一态

状态：|x⟩ ⊗ |c⟩，硬币 c ∈ {左, 右}
硬币翻转（Hadamard）：
  H|左⟩ = (|左⟩ + |右⟩)/√2
  H|右⟩ = (|左⟩ - |右⟩)/√2
移位：
  |x⟩|右⟩ → |x+1⟩|右⟩（右移）
  |x⟩|左⟩ → |x-1⟩|左⟩（左移）

量子行走的分布：不像经典那样「展平」，而是出现「双峰干涉峰」
  → 速度更快（线性扩散 vs 经典的平方根扩散）

经典随机游走 t 步：标准差 ∝ √t（扩散慢）
量子行走 t 步：标准差 ∝ t（弹道扩散，快得多）
→ 「不走回头路」的干涉让量子行走「跑得更远」

连续时间行走：
  |ψ(t)⟩ = e^(-iHt)|ψ(0)⟩
  H = 邻接矩阵（或图拉普拉斯）
  → 振幅按图的连接结构「持续演化」

无硬币：方向由「图的边」自然决定
  → 更简单的数学，更适合图论问题

H = 邻接矩阵 A（元素 1 表示相连）
或 H = 拉普拉斯 L = D - A（度矩阵减邻接）
不同选择影响干涉模式与加速常数
→ 连续行走的「能量」由图的谱结构决定

经典：随机游走碰运气 → 期望 O(N) 步找到
量子行走：叠加 + 干涉 → O(√N) 步找到（二次加速）

经典随机搜索：每次随机尝试，成功概率 1/N
  → 期望尝试 N 次

量子行走搜索：
  1. 叠加态均匀覆盖所有位置
  2. 「标记位置」反射（相位翻转标记）
  3. 「行走一步」扩散振幅
  4. 重复「标记翻转 + 扩散」≈ √N 次
  → 标记振幅被「放大」，测量高概率命中
→ 与 Grover 的振幅放大同构，只是「扩散算子」从均匀叠加换成行走

干涉需要「相位累积」：
  每次循环让标记振幅增长一点
  √N 次循环达到最大增长（过则下降）
→ 这是「旋转半径」的物理极限（Grover 下界同样适用）

输入：图 G + 标记集合 M
步骤：
  1. 初始化：均匀叠加所有节点（或固定起始）
  2. 循环 ≈ 1/√δ 次：
     a. 标记反射：标记节点相位翻转
     b. 行走扩散：沿图结构扩散振幅
  3. 测量位置 → 高概率命中标记
  δ = 图的相关谱参数（决定步数）

加速程度取决于「标记浓度」与图的谱：
  稀疏标记 + 稠密图 → 明显加速
  标记过多/图结构差 → 加速减弱
核心：行走的「展开速度」要匹配「标记密度」
→ 谱间隙（spectral gap）是加速的关键参数

任何「可高效模拟的行走」都能给出搜索加速
  → 行走搜索是「模块化的」：
     换一个行走 = 换一个图/问题 = 保持加速框架
→ 不必每次从零设计算法，套行走搜索框架即可

典型图与行走：
  完全图/超立方体 → 快速混合 → 搜索 O(√N)
  二维网格 → 行走搜索仍有加速（含空间开销）
  稀疏图（树/链）→ 加速依赖具体结构

网格上的行走搜索：
  标记翻转 → 振幅聚焦标记
  行走扩散 → 把「聚焦」扩散到附近
  循环 → 「搜索波」在图上推进
→ 图搜索 = 「聚焦-扩散」的量子波传播

经典：
  排序后扫描 → O(N log N)
  或随机采样 → 最优量子加速前接近 O(N)

量子行走：
  行走搜索「三合游走」→ O(N^(2/3))
  → 比经典的 O(N) 好，比 O(√N) 弱
→ 元素不同性是最著名的「行走量子加速」之一

问题需要「同时看到多个元素」：
  状态 = 一组已看元素（子集）
  行走在「子集的图」上移动
  标记 = 子集内含重复
→ 行走的状态空间复杂度影响指数（N^(2/3)）

- 第一个「超过 Grover 二次加速」的直觉？不——
  Grover 是 N→√N，这里是 N→N^(2/3)
  （对「图搜索」是二次，对「元素不同性」是 2/3 幂）
- 展示行走框架的「问题定制能力」
→ 元素不同性是行走搜索在「具体数据问题」上的旗舰例子

物理中的传输/扩散 = 随机游走或量子行走
  光子传播、量子热化、输运
  量子行走能「模拟」这些物理过程（天然匹配）

结构化模拟：
  把哈密顿量分解成行走算符
  → 用行走实现某些量子模拟（e^(-iHt) 分解）

连续时间行走 e^(-iHt) 本身就是「哈密顿量模拟」：
  选择 H = 目标哈密顿量 → 行走 = 模拟
→ 行走框架是「哈密顿量模拟」的一种实现途径
（详见 /quantum-hamiltonian-simulation/）

行走 = 按图结构演化的酉变换
  「演化」可以是模拟（物理系统）
  也可以是搜索（图算法）
→ 行走是「图驱动演化」的通用语言

- 光子：线性光学实现离散行走（成熟、可扩展）
- 原子/离子：光晶格中的原子行走
- 超导：量子电路实现行走算符
- 核磁共振：早期原理验证
→ 光子平台是行走实验的主流（干涉天然匹配）

- 一维光子行走（2013 前后）验证弹道扩散
- 多维/图上行走逐步实现
- 行走搜索在光子系统验证加速
- 集成光波导把行走「芯片化」
→ 行走是可「真实跑」的量子计算范式（NISQ 友好）

行走实验规模在「几十步、几百模式」量级
  → 超过经典模拟的边界尚未达到
  → 但作为「原理验证 + 物理模拟」已非常实用
→ 行走是「最容易实验验证」的量子算法之一

- 二次加速「只在特定问题」（搜索类）
- 多数实用问题缺少「可模拟行走 + 清晰标记」
- 图结构差 → 加速退化
- 需要「相位相干」维持 → 噪声破坏加速
→ 行走不是万灵药，是「图搜索/特定问题」的加速器

- 噪声：退相干把量子行走「退化」成经典随机游走
- 实现：大规模图行走的物理实现仍在早期
- 误差：谱间隙的精确估计难
- 实用：与真实业务的「图」接轨（社交/网络图）仍在研究
→ 从「玩具图」到「实用图」是最大鸿沟

- 行走搜索在「真实网络图」的加速
- 行走 + 变分/混合算法的结合
- 容错框架下的行走实现
- 行走与量子机器学习结合
→ 行走框架仍在「扩展应用面」