2. 量子计算最小必要基础
量子游走算法建立在量子力学的一组最小概念之上。若把经典随机游走理解为“一枚硬币按概率决定向左或向右”，那么量子游走就是把硬币换成量子比特、把概率换成概率幅、把随机选择换成酉演化。要读懂后续的图问题求解，必须先掌握八个基础对象：量子比特、叠加、纠缠、测量、酉演化、密度矩阵、量子线路模型与复杂度记号。它们不是并列的八个名词，而是一条从“状态如何表示”到“状态如何变化”再到“结果如何读出”的完整链条。
量子比特与叠加：状态不是0或1，而是幅的线性组合
经典比特只能取0或1。量子比特（qubit）的状态写成二维复向量：
|ψ⟩ = α|0⟩ + β|1⟩， α, β ∈ ℂ， |α|² + |β|² = 1其中 α、β 称为概率幅，不是概率。|0⟩ 与 |1⟩ 是计算基。若 α=1、β=0，则状态确定是0；若 α=β=1/√2，则测量得到0或1的概率各为1/2，但此时状态本身既不是0也不是1，而是两者的叠加。叠加的关键在于幅可以带相位：α=1/√2 与 α=−1/√2 的测量概率相同，但相位不同，后续干涉结果完全不同。量子游走中“硬币”通常就是这样一个处于叠加态的量子比特。
多量子比特系统的状态空间是张量积。两个量子比特的基为 |00⟩、|01⟩、|10⟩、|11⟩，一般态为四个幅的线性组合。n 个量子比特的态由 2ⁿ 个幅描述，这是量子并行性的来源，也是模拟量子系统需要指数级经典资源的原因。
纠缠：不可分解的联合状态
若两个量子比特的联合态能写成 |ψ₁⟩⊗|ψ₂⟩，则称其为可分离态；否则为纠缠态。最典型的纠缠态是 Bell 态：
|Φ⁺⟩ = (|00⟩ + |11⟩)/√2它不能写成两个单比特态的乘积。测量第一个比特得到0，第二个必为0；得到1，第二个必为1。纠缠不是“通信”，而是联合幅结构导致的强关联。在量子游走中，硬币与位置之间、多个游走者之间常通过纠缠建立关联，从而影响扩散速度与命中目标的概率分布。
测量：把幅变成经典结果
测量是量子与经典的交界。对态 |ψ⟩=α|0⟩+β|1⟩ 在计算基下测量，得到0的概率为 |α|²，得到1的概率为 |β|²，测量后态坍缩到对应基态。若测量的是可观测量 A，则先做谱分解 A=ΣλᵢPᵢ，得到结果 λᵢ 的概率为 ⟨ψ|Pᵢ|ψ⟩，测量后期望值为 ⟨A⟩=⟨ψ|A|ψ⟩。
量子算法通常不在中间随意测量，因为测量会破坏叠加与纠缠。正确做法是让酉演化把目标幅放大，最后再测量。量子游走求解图问题的核心，正是设计演化使目标顶点的幅在测量时具有高概率。
酉演化：唯一允许的封闭系统演化
封闭量子系统的演化由酉算子 U 描述，满足 U†U=I。离散时间下 |ψ(t+1)⟩=U|ψ(t)⟩；连续时间下由薛定谔方程 iℏ d|ψ⟩/dt = H|ψ⟩ 给出，解为 |ψ(t)⟩=e^{−iHt}|ψ(0)⟩，其中 H 是厄米哈密顿量。酉性保证内积与总概率守恒，因此演化可逆。
量子游走的“行走”就是反复施加一个酉算子。离散时间量子游走常用硬币算子 C 与移位算子 S 组合：U=S(C⊗I)。硬币算子把 |0⟩、|1⟩ 变成叠加，移位算子根据硬币结果把位置幅向相邻顶点搬运。连续时间量子游走则直接以图的邻接矩阵或拉普拉斯矩阵作为 H，让幅在顶点间连续流动。
密度矩阵：混合态与退相干的描述
纯态可用向量表示，但若系统以概率 pᵢ 处于 |ψᵢ⟩，则需用密度矩阵 ρ=Σpᵢ|ψᵢ⟩⟨ψᵢ|。纯态满足 Tr(ρ²)=1，混合态满足 Tr(ρ²)<1。酉演化下 ρ→UρU†；测量结果 i 的概率为 Tr(Pᵢρ)。密度矩阵还能描述与环境耦合导致的退相干：非对角元衰减，叠加被破坏。对量子游走而言，退相干会降低干涉效应，使扩散从量子弹道式扩散退化为经典扩散，这是实际硬件上必须评估的误差来源。
量子线路模型：把算法写成门序列
量子线路模型用门序列描述计算：初始态 |0…0⟩，依次施加单比特门、双比特门与测量。常用门包括 Hadamard 门 H、相位门 S/T、旋转门 Rₓ/R_y/R_z、受控非门 CNOT 与受控相位门 CZ。H 门把 |0⟩ 变为 (|0⟩+|1⟩)/√2，是制造叠加的基本工具；CNOT 与 H 配合可制备 Bell 态。量子游走的一步可编译为“硬币门 + 受控移位门”的线路，位置寄存器用若干量子比特编码顶点编号。
复杂度记号：衡量量子优势的尺子
复杂度记号用于比较算法资源。O(·) 表示上界，Ω(·) 表示下界，Θ(·) 表示紧界。量子查询复杂度统计调用黑箱的次数，门复杂度统计基本门数量，深度表示线路可并行层数。经典随机游走在一般图上命中目标约需 O(N) 步，而量子游走在若干结构上可达到 O(√N) 的加速；但这一加速依赖图结构、硬币选择与测量策略，并非所有图问题都能直接获得平方加速。理解这些记号，才能判断后续算法究竟快在哪里、代价是什么。
把上述概念串起来看：量子比特提供状态空间，叠加与纠缠提供并行与关联，酉演化负责可控地搬运和干涉幅，测量把幅转成可读结果，密度矩阵刻画噪声与混合，线路模型给出可编译的门序列，复杂度记号则回答“这样做的代价与收益”。后续量子游走算法，本质上就是在这套框架内设计硬币、移位与测量策略，使目标顶点的幅被放大到可观测的程度。