3. QAOA核心原理

QAOA（Quantum Approximate Optimization Algorithm）的核心思想，是把一个组合优化问题编码进量子电路的“相位”里，再用一个可调的混合过程把相位信息转化为可测量的概率分布。整个算法可以拆成四个数学对象：初态、相位分离算子、混合算子、以及末端测量与期望值估计。理解这四个对象的数学结构，就理解了 QAOA 为什么能工作、参数如何影响结果。

一、从问题到哈密顿量：目标函数的量子化

设组合优化问题的目标函数为 C(z)，其中 z = (z₁, z₂, …, zₙ) 是 n 个二进制变量的取值，zᵢ ∈ {0,1}。QAOA 的第一步是把 C(z) 映射为对角哈密顿量 H_C，使其在计算基 |z⟩ 上的本征值恰好等于 C(z)：

H_C |z⟩ = C(z) |z⟩

例如最大割问题中，每条边 (i,j) 的贡献是 zᵢ ⊕ zⱼ，对应哈密顿量项为 (1 − ZᵢZⱼ)/2，其中 Z 是泡利 Z 矩阵。这样，寻找 C(z) 的最小值就等价于寻找 H_C 的最小本征值。

二、相位分离算子：把目标值写进相位

相位分离算子定义为 U_C(γ) = e^{−iγH_C}，其中 γ 是变分参数。由于 H_C 是对角的，作用在计算基上只产生相位：

U_C(γ)|z⟩ = e^{−iγC(z)}|z⟩

这意味着：目标函数值越小的 z，其相位旋转越“慢”；目标函数值越大的 z，相位旋转越“快”。相位分离算子本身不改变测量概率，它只是把 C(z) 的信息编码进量子态的相位中。这是 QAOA 的“信息写入”阶段。

三、混合算子：把相位转化为概率

混合算子通常取 U_B(β) = e^{−iβH_B}，其中 H_B = Σᵢ Xᵢ，X 是泡利 X 矩阵。它的作用是让各个计算基态之间发生干涉和混合。单独看 U_B，它会把一个基态变成所有基态的均匀叠加；与 U_C 交替作用后，相位差就会转化为振幅差，从而改变测量到不同 z 的概率。

QAOA 的完整变分态为：

|ψ(γ,β)⟩ = U_B(β_p) U_C(γ_p) … U_B(β₁) U_C(γ₁) |+⟩^⊗n

其中 p 是电路层数，γ = (γ₁,…,γ_p)、β = (β₁,…,β_p) 是 2p 个变分参数。初态 |+⟩^⊗n 是所有计算基态的均匀叠加，保证算法从“无偏”状态出发。

四、测量与期望值估计

电路执行完毕后，对每个量子比特在计算基下测量，得到比特串 z。重复测量 N_shots 次，统计每个 z 出现的频率 P(z)，即可估计目标哈密顿量的期望值：

⟨H_C⟩ ≈ (1/N_shots) Σ_{k=1}^{N_shots} C(z_k)

这个估计值就是经典优化器的目标函数。经典优化器（如 COBYLA、Nelder-Mead 或梯度下降）根据 ⟨H_C⟩ 调整 γ 和 β，再送回量子电路执行，形成“量子采样—经典优化”的闭环。当 p 足够大且参数优化充分时，⟨H_C⟩ 会逼近问题的最优值。

五、一个可手算的示例

考虑两个比特的最大割问题，边为 (1,2)，目标函数 C(z) = z₁ ⊕ z₂。最优解是 01 或 10，最优值为 1。取 p=1，初态 |+⟩|+⟩，参数 γ、β。

经过 U_C(γ) 后，四个基态的相位分别为：|00⟩: e^{0}、|01⟩: e^{−iγ}、|10⟩: e^{−iγ}、|11⟩: e^{0}。再经过 U_B(β) 混合，最终测量到 01 和 10 的概率为：

P(01) = P(10) = (1 + sin(2β) sin(γ)) / 4

当 γ = π/2、β = π/4 时，P(01) = P(10) = 1/2，P(00) = P(11) = 0，期望值 ⟨H_C⟩ = 1，达到最优。这个例子说明：相位分离算子负责“标记”好解，混合算子负责“放大”好解的概率，两者缺一不可。

六、参数初始化与层数选择

实际实现中，γ 和 β 的初始化通常取小值，例如 γᵢ ∈ [0, 2π)、βᵢ ∈ [0, π) 内随机采样，或使用线性插值策略。层数 p 的选择需要权衡：p 越大，变分态的表达能力越强，但参数空间维度为 2p，经典优化难度也随之增加。对于小规模问题，p=1~3 通常就能观察到明显效果；对于更大规模问题，可能需要 p=5~10 甚至更多。

测量次数 N_shots 直接影响期望值估计的统计误差。若 C(z) 的取值范围为 [0, C_max]，则估计标准差约为 C_max / (2√N_shots)。例如 N_shots = 1000、C_max = 10 时，标准差约为 0.16。若需要更高精度，应增加测量次数或使用方差缩减技术。

七、数学结构小结