量子近似优化算法（QAOA）#

背景与理论#

QAOA（Farhi 等人，2014）是一种用于求解组合优化问题的量子-经典混合算法。它通过交替施加代价酉和混合酉来逼近最优解。

MaxCut 问题#

给定图 \(G = (V, E)\)，MaxCut 寻求将 \(V\) 划分为两个集合，使得跨越分割的边数最大化。

代价哈密顿量：

\[H_C = -\frac{1}{2} \sum_{(i,j) \in E} (1 - Z_i Z_j)\]

最大化 \(-H_C\) 等价于最大化切割数。

QAOA 拟设#

QAOA 态的制备方式为：

\[|\psi(\boldsymbol{\beta}, \boldsymbol{\gamma})\rangle = \prod_{l=1}^{p} e^{-i\beta_l H_M} e^{-i\gamma_l H_C} |+\rangle^{\otimes n}\]

其中 \(H_M = \sum_i X_i\) 是混合哈密顿量，\(p\) 是层数（\(p\) 越大 → 近似效果越好）。

算法流程#

初始化 |+⟩⊗n → 施加 e^{-iγ₁ Hc} → 施加 e^{-iβ₁ Hm} → ... → 测量 ⟨Hc⟩
                     ↑                                                    ↓
                     └──────── 经典优化器（更新 β, γ） ←────────────────┘

使用的组件#

组件	模块	功能
`qaoa_ansatz`	`algorithmics.ansatz`	参数化 QAOA 电路
`OriginIR_Simulator`	`simulator`	态矢量模拟

运行示例#

# 默认：p=2 层，三角形图
python examples/algorithms/qaoa.py

# 更多层数
python examples/algorithms/qaoa.py -p 3

# 更多迭代次数
python examples/algorithms/qaoa.py -p 2 --maxiter 200

代码解析#

1. 定义代价哈密顿量#

def maxcut_hamiltonian(edges, n_nodes):
    terms = []
    for i, j in edges:
        terms.append((f"Z{i}Z{j}", 0.5))
    return terms

2. 构建拟设#

from uniqc.algorithmics.ansatz import qaoa_ansatz

circuit = qaoa_ansatz(
    cost_hamiltonian=[("Z0Z1", 0.5), ("Z1Z2", 0.5), ("Z0Z2", 0.5)],
    p=2,
    betas=[0.5, 0.3],
    gammas=[0.7, 0.2],
)

3. 评估与优化#

能量 \(\langle H_C \rangle\) 由态矢量计算得出，并输入坐标下降优化器。

预期结果#

对于三角形图（3 条边）：

最优切割：2 条边（将一个顶点与其余两个分开）
\(p=2\) 的 QAOA 应以高概率达到最优切割

扩展方向#

加权 MaxCut：在哈密顿量中添加边权重。
不同图结构：尝试随机图、平面图等。
更高的 \(p\)：更多层数可将近似比提升至接近 1.0。
基于采样的模拟：使用 QASM_Simulator 进行真实噪声测量模拟。

References#

Farhi, E., Goldstone, J., & Gutmann, S. (2014). “A Quantum Approximate Optimization Algorithm.” arXiv:1411.4028.
Zhou, L. et al. (2020). “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.” Frontiers in Physics 10, 585524.