1. 量子退火求解组合优化问题的建模与求解
问题定义与建模：5 节点最大割
最大割（Max-Cut）的目标是把无向图的顶点分成两组，使跨越两组的边权之和最大。选一个 5 节点、6 条边的小图作为教学对象，边权如下：
| 边 | (0,1) | (0,2) | (1,2) | (1,3) | (2,4) | (3,4) |
|---|---|---|---|---|---|---|
| 权重 | 1 | 2 | 1 | 3 | 2 | 1 |
用自旋变量 s_i ∈ {−1, +1} 表示顶点归属（+1 与 −1 分属两组）。一条边 (i,j) 被割断当且仅当 s_i ≠ s_j，此时 (1 − s_i s_j)/2 = 1。因此最大化割值等价于最小化下面的伊辛能量：
E(s) = Σ_(i,j) w_ij · (1 − s_i s_j) / 2
= 常数 − (1/2) · Σ w_ij s_i s_j量子退火器（如 D-Wave）求解的是 E = Σ J_ij s_i s_j + Σ h_i s_i 形式。对照可得耦合系数 J_ij = −w_ij/2，局部场 h_i = 0。常数项不影响最优解位置，可忽略。于是建模只需给出 J 矩阵与 h 向量。
量子退火求解流程与参数设置
量子退火的核心是让系统从初始哈密顿量 H_init = −Σ σ_i^x 缓慢演化到问题哈密顿量 H_problem = Σ J_ij σ_i^z σ_j^z。演化时间（annealing time）越长，系统越可能停留在基态，但受噪声与退相干限制，并非越长越好。关键参数：
- 退火时间：本例取 20 μs，属于小规模问题的常用量级。
- 读取次数（num_reads）：每个退火周期结束后测量一次，取 1000 次以统计解分布。
- 链强度（chain_strength）：本例 5 节点图可完整嵌入，无需链，设为默认。
若使用 D-Wave 的 Ocean SDK，建模与提交代码如下（dimod 的 BQM 接口同时兼容模拟器与真实退火器）：
import dimod
from dwave.system import DWaveSampler, EmbeddingComposite
# 1. 构造 BQM：J 为耦合，h 为局部场
J = {(0,1): -0.5, (0,2): -1.0, (1,2): -0.5,
(1,3): -1.5, (2,4): -1.0, (3,4): -0.5}
h = {i: 0.0 for i in range(5)}
bqm = dimod.BinaryQuadraticModel(h, J, 0.0, dimod.SPIN)
# 2. 提交到量子退火器（需配置 D-Wave 凭证）
sampler = EmbeddingComposite(DWaveSampler())
sampleset = sampler.sample(bqm, num_reads=1000, annealing_time=20)
# 3. 读取最优解
best = sampleset.first
print(best.sample, best.energy)没有 D-Wave 访问权限时，用 dimod.ExactSolver() 或 neal.SimulatedAnnealingSampler() 替代 sampler 即可跑通同一套建模代码，验证 BQM 构造是否正确。
经典模拟退火对比验证
为判断量子退火结果是否可信，用经典模拟退火在同一 BQM 上求解并对比。经典模拟退火通过温度参数 beta（逆温度）控制接受劣解的概率，从高温逐步降温：
import neal
sa = neal.SimulatedAnnealingSampler()
sa_sampleset = sa.sample(bqm, num_reads=1000, beta_range=[0.1, 5.0])
sa_best = sa_sampleset.first
print("SA 最优:", sa_best.sample, sa_best.energy)
# 穷举验证（5 节点仅 32 种自旋配置）
exact = dimod.ExactSolver().sample(bqm)
print("精确最优能量:", exact.first.energy)5 节点问题共 2⁵ = 32 种自旋配置，穷举可得到精确基态能量，作为两种退火方法的上界参照。预期现象：精确解能量应为 −3.0（对应割值 8），量子退火与经典模拟退火在 1000 次读取中应大概率命中该能量；若量子退火的最优能量高于精确值，说明退火时间不足或噪声导致未收敛。
结果解读与判读要点
拿到 sampleset 后，不要只看 first，应统计能量分布与解的出现频率：
import collections
energies = sampleset.record.energy
counts = collections.Counter(energies)
for e, c in sorted(counts.items()):
print(f"能量 {e:+.1f}: {c} 次")判读逻辑：
- 最优能量等于精确值：建模正确，退火参数合理。
- 最优能量高于精确值但差距小：退火时间偏短，可增大
annealing_time或num_reads。 - 最优能量明显偏高：检查 J 符号是否写反（最大化割值对应负 J），或链强度不足导致嵌入失败。
- 最优解出现频率极低：说明基态与激发态能量间隙小，属于问题本身的难度，不是参数错误。