quantum

QAOA 与量子组合优化：MaxCut、哈密顿量与混合变分求解

深入 QAOA（量子近似优化算法）：组合优化问题编码、Ising 哈密顿量、QAOA 电路结构（交替算子）、变分优化循环、MaxCut 实战（Qiskit）、与经典求解器对比与适用边界。

Leeting Yan 6 分钟阅读 2948 字

引言

组合优化（路径规划、排班、网络分割）是量子计算最有潜力的应用之一——**QAOA（量子近似优化算法）**是其中最著名的变分方法。本文讲透 QAOA：先从「怎么把优化问题编码成哈密顿量」讲起（MaxCut 为例），再给 QAOA 的电路结构（交替的相位分离算子 + 混合算子），接着用 Qiskit 从零实现并优化 MaxCut，然后讲参数优化循环与收敛、与经典求解器的对比，最后明确 QAOA 的适用边界（什么时候值得用量子）。

前置：/quantum-qubit-gates-basics/（旋转门与测量）、/quantum-qiskit-programming/（Qiskit）、/quantum-hardware-annealing/（量子退火对比）。

目录

1. 组合优化问题：为什么难

组合优化 = 从指数级候选里找最优解：

例：MaxCut 把图顶点分两组，最大化「被切开」的边数
n 个顶点 → 2^n 种分组方案
n=50 → 2^50 ≈ 10^15 → 穷举不可能

经典困难：

MaxCut 是 NP-hard（一般图）
近似：经典算法给近似比（如 0.878 的 Goemans-Williamson）
QAOA：量子变分方法，期望给出更好的近似比
问题目标经典
MaxCut切最多的边近似比 0.878
最大团最大的完全子图NP-hard
旅行商最短路径近似算法

心智：组合优化难在「候选指数爆炸」——量子优化的思路：把问题编码成哈密顿量，让量子态在能量景观里找最低点。

2. 问题编码：从目标函数到 Ising 哈密顿量

核心思想：把「优化目标」变成「量子哈密顿量的期望值」：

变量 x_i ∈ {0,1}（选/不选）
目标函数 f(x) → 改写成 Pauli 算符 Z 的多项式
→ 构造哈密顿量 H_C（成本算子）
→ 解的最优 = H_C 的最小本征态

Ising 模型（量子优化的标准语言）：

H_C = Σ w_ij · Z_i · Z_j + Σ h_i · Z_i
Z = 泡利 Z 算符（Z|0⟩=|0⟩, Z|1⟩=-|1⟩）
二进制变量 ↔ 自旋：x_i = (1 - Z_i)/2

# Qiskit 里把优化问题转哈密顿量（用 QAOA 模块）
from qiskit_optimization.translators import from_docplex_mp
# 或用 qiskit_optimization.applications 直接建 MaxCut
from qiskit_optimization.applications import Maxcut

maxcut = Maxcut(graph)
qp = maxcut.to_quadratic_program()      # 二次规划

记忆：编码 = 把「0/1 选边」翻译成「Z 算符的能量」——优化找最小能量，就是找最优解。

3. MaxCut 案例：把问题变成哈密顿量

MaxCut 的数学：

图 G(V,E)，分两组 S 与补集
边 (i,j) 被切 = 顶点在不同组
目标：最大化被切边数
变量 x_i ∈ {0,1}（0=组A, 1=组B）
边被切：x_i XOR x_j = x_i + x_j - 2x_i·x_j
MaxCut → minimize -Σ_{边} (x_i + x_j - 2x_i x_j)

转 Ising（用 Z 代替 x，x = (1-Z)/2）：

H_C = Σ_{(i,j)∈E} (1 - Z_i·Z_j)/2
要最大化被切边 → 最小化 H_C 的能量

# 用 Qiskit Optimization 直接构造 MaxCut
from qiskit_optimization.applications import Maxcut
import networkx as nx

G = nx.Graph()
G.add_edges_from([(0,1),(0,2),(1,2),(2,3),(1,3)])  # 例图

maxcut = Maxcut(G)
qp = maxcut.to_quadratic_program()
print(qp.prettyprint())    # 看目标函数

记忆：MaxCut 的哈密顿量 = Σ(1 - Z_i Z_j)/2——每条边一项，能量最低的态就是最优分组。

4. QAOA 电路结构：相位分离 + 混合算子

QAOA 电路 = 交替两族算子，共 p 层：

初始态：所有比特 |+⟩（等权重叠加）
每层：
  1. 相位分离算子 U_C(γ) = e^{-iγ·H_C}   → 按成本哈密顿量给态「加相位」
  2. 混合算子 U_M(β) = e^{-iβ·ΣX}        → 在解空间里「混合探索」
参数 γ, β 由经典优化器调 → 期望 <H_C> 降到最低

p 层结构：

|+⟩ → U_C(γ₁)U_M(β₁) → U_C(γ₂)U_M(β₂) → … → U_C(γₚ)U_M(βₚ) → 测量

# Qiskit 里 QAOA 电路（用内置库）
from qiskit.circuit.library import QAOAAnsatz

qaoa_circuit = QAOAAnsatz(cost_operator=cost_hamiltonian,
                          reps=1)   # p = 1 层
qaoa_circuit.measure_all()

记忆：QAOA = p 组「相位门 + 混合门」交替——γ 偏向好解、β 负责探索，p 越大越接近最优。

5. 变分循环：参数优化与收敛

QAOA 是「量子-经典混合」算法：

循环：
1. 经典选参数 (γ, β)
2. 量子机跑电路 → 测量 → 估 <H_C>
3. 经典优化器调 (γ, β) 再试
4. 直到 <H_C> 收敛 → 输出最优解

参数优化器：

from qiskit.algorithms.minimizers import COBYLA, SPSA, NFT

# COBYLA：简单稳健（小参数少）
# SPSA：噪声环境友好（梯度估计）
# NFT：二阶，更快收敛

初始参数的重要性：

随机初始化 → 收敛慢、易陷入局部
启发式初始化（利用 p-1 层的解）→ 快且稳

记忆：QAOA = 量子给「能量采样」、经典给「参数调优」——优化器选对、初始参数选好，收敛快一半。

6. Qiskit 实战：MaxCut 的 QAOA 求解

完整实现：

from qiskit import QuantumCircuit, Aer, execute
from qiskit.circuit.library import QAOAAnsatz
from qiskit.quantum_info import Pauli, SparsePauliOp
from qiskit.algorithms.minimizers import COBYLA
import numpy as np, networkx as nx
from qiskit_optimization.applications import Maxcut

# 1. 图与 MaxCut 哈密顿量
G = nx.Graph(); G.add_edges_from([(0,1),(0,2),(1,2),(2,3),(1,3)])
maxcut = Maxcut(G)
qp = maxcut.to_quadratic_program()
cost_h = qp.to_ising()          # 转 Ising 哈密顿量

# 2. 构造 QAOA 电路（p=2）
qaoa = QAOAAnsatz(cost_operator=cost_h, reps=2)
qaoa.measure_all()

# 3. 参数优化循环（简化：网格试参数）
backend = Aer.get_backend('qasm_simulator')
best = (np.inf, None)
for gamma in np.linspace(0, np.pi, 20):
    for beta in np.linspace(0, np.pi, 20):
        params = np.array([gamma]*2 + [beta]*2)
        bound = qaoa.assign_parameters(params)
        counts = execute(bound, backend, shots=4096).result().get_counts()
        # 期望能量
        exp = sum(energy_from_bitstring(bits) * prob for bits, prob in counts.items())
        if exp < best[0]: best = (exp, params)

# 4. 取最优比特串 → 解
_, params = best
bound = qaoa.assign_parameters(params)
counts = execute(bound, backend, shots=8192).result().get_counts()
best_bitstring = max(counts, key=lambda b: -cost_of(b))
print("最优分组:", best_bitstring)

记忆：QAOA 实战五步——建图转哈密顿量、构造 Ansatz、调参数、测能量、取最优串——小问题模拟器秒解。

7. 与经典求解器对比：何时值得用量子

QAOA 不是万能银弹——对比现实：

维度经典（Gurobi/GW）QAOA
小问题秒级最优慢且有近似
大问题可到十万变量受比特数限制
噪声无有（需缓解）
近似保证GW 有 0.878无严格保证
优势条件—深度够 + 噪声低

什么时候值得考虑 QAOA：

1. 问题规模受限（几十比特）
2. 有结构性问题（局部哈密顿量友好）
3. 研究/教学/验证量子优势路径
4. 深度 p 足够 + 噪声可控

记忆：QAOA 目前「研究价值 > 实用价值」——小问题经典更快更准，量子优势要等容错硬件。

8. QAOA 的深度 p：近似比与量子优势

p 与质量的关系：

p = 1：一层 → 类似经典局部搜索，近似比有限
p 增大：更接近最优，但电路更深 → 噪声更大
极限：p → ∞ 可逼近最优（但无噪声时）
噪声机器：p 大到一定程度反而更差

近似比：

近似比 = 得到的解质量 / 最优解质量（≤ 1）
QAOA p=1 对 MaxCut 有理论近似比（最优的 0.5~0.7 量级）
p 增加可提升，但受噪声天花板

# 看 p 对能量收敛的影响
for p in [1, 2, 3]:
    qaoa = QAOAAnsatz(cost_operator=cost_h, reps=p)
    # 优化后看 <H_C>
    print(f"p={p}: 最优能量 = {optimize(qaoa):.3f}")

记忆：p 是「精度旋钮」——p 大更准但更深更噪——噪声机器有「最佳深度」，不是越深越好。

9. 工程要点：噪声、初始参数与扩展

QAOA 工程化的三个要点：

要点做法
噪声错误缓解（ZNE/测量缓解）、低深度
初始参数启发式（用上一层解过渡）
扩展问题分解、并行、硬件感知布局

错误缓解配合（见 /quantum-error-mitigation/）：

from qiskit_ibm_runtime import SamplerV2, QiskitRuntimeService
# 用 SamplerV2 + 测量错误缓解
sampler = SamplerV2(backend=service.backend("ibm_sherbrooke"))
job = sampler.run([bound], shots=4096)

参数维度的「尺缩」：QAOA 的参数空间随 p 线性增长——优化器选 SPSA 抗噪。

记忆：QAOA 工程三件事——降噪（缓解+低深度）、稳初始化（启发式）、可扩展（分解）——别裸奔上噪声真机。

10. 速查表

需求做法
问题转哈密顿量qp.to_ising()
MaxCut 建模Maxcut(graph).to_quadratic_program()
QAOA 电路QAOAAnsatz(cost_operator, reps=p)
参数优化COBYLA / SPSA / NFT
估能量测量统计 → 期望值
深度 p大更准但更深更噪
噪声缓解ZNE / 测量缓解
初始参数启发式（上层解过渡）
对比经典小问题经典更快

一句话记忆：QAOA = 组合优化编码成 Ising 哈密顿量 + p 层「相位门-混合门」交替电路 + 经典优化器调参；MaxCut 建图转 H_C、Qiskit Ansatz 一键生成；p 是精度旋钮但噪声有天花板；小问题经典更实用、量子优势待容错硬件——QAOA 是量子优化的旗舰，但要用得清醒。

延伸阅读

  • /quantum-qubit-gates-basics/ — 旋转门与测量
  • /quantum-qiskit-programming/ — Qiskit 编程
  • /quantum-hardware-annealing/ — 量子退火对比
  • /quantum-chemistry-simulation/ — VQE（另一个变分算法）
  • /quantum-error-mitigation/ — 噪声缓解
  • [[ml]] — 优化与梯度下降

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「quantum」更多文章

  1. 量子错误缓解：ZNE、测量缓解与概率错误消除实战
  2. 量子纠缠与 Bell 态：EPR 悖论、贝尔不等式与量子隐形传态
  3. 量子电路编译与优化：门分解、电路深度与 Qiskit 编译管线