量子退火与组合优化问题
量子退火（Quantum Annealing）是一种基于量子力学隧穿效应的启发式搜索算法，专门用于求解 组合优化问题。相较于传统的模拟退火，量子退火利用量子叠加与隧穿，使系统能够在高维能量景观中更快地逃离局部最优，从而有望在多项 NP‑hard 问题上获得更优的近似解。下面从理论到实践，系统阐述量子退火在组合优化中的应用方法。
哈密顿量的构造
- 初始哈密顿量 (H_B = -\sum_i \sigma_i^x)，对应全局超位置态（所有自旋均为 (|+\rangle)）。
- 目标哈密顿量 (H_P) 表示待优化的成本函数，通常为 Ising 模型或 QUBO（Quadratic Unconstrained Binary Optimization）形式。
退火过程
[
H(t) = A(t) H_B + B(t) H_P,\qquad t\in[0,T]
]- (A(t)) 从大到小、(B(t)) 从小到大，系统在演化过程中逐渐从量子隧穿主导转向经典能量最小化。
- 若演化足够慢（满足阿迪亚巴蒂定理），系统最终会落在 (H_P) 的基态，即全局最优解。
量子隧穿的优势
- 在高能量屏障（局部最优）之间，经典热激发需要克服能量差，而量子隧穿可以直接穿过屏障，提升搜索效率。
2. 组合优化问题概述
| 类别 | 典型问题 | 形式化描述 |
|---|---|---|
| 图割类 | Max‑Cut、最小割 | 将图的顶点划分，使跨边权和最大/最小 |
| 排列类 | 旅行商问题（TSP） | 在给定城市集合中寻找最短哈密顿回路 |
| 分配类 | 二进制背包、任务调度 | 在约束条件下最大化收益或最小化成本 |
| 约束满足 | SAT、图着色 | 满足布尔或整数约束的可行解搜索 |
这些问题均可映射为二进制变量的二次函数，即 QUBO：
[
\min_{x\in{0,1}^n} ; x^\top Q x + c^\top x
]
其中矩阵 (Q) 与向量 (c) 完全描述了问题的约束与目标。
3. 量子退火求解流程
建模
- 将实际问题抽象为 QUBO 或 Ising 模型。
- 需要注意变量的二进制化（如 0/1 ↔ (\pm1)）以及约束的惩罚项。
嵌入（Embedding）
- 量子退火硬件（如 D‑Wave）拥有固定的拓扑结构（Chimera、Pegasus）。
- 使用 minor‑embedding 将逻辑变量映射到物理量子比特上，必要时引入链（chain）来实现变量间的强耦合。
参数调度
- 设定退火时间 (T)、链强度、采样次数（samples）等。
- 对于噪声较大的实际机器，可通过 reverse annealing 或 pause 等技巧提升解的质量。
采样与后处理
- 读取多次测量结果，统计出现频率最高的解。
- 对链断裂的样本进行 majority vote 或 energy correction。
- 若需要满足硬约束，可在后处理阶段进行局部搜索（如 2‑opt、局部爬山）进一步优化。
4. 实际案例：使用 D‑Wave Ocean SDK 求解 Max‑Cut
# 1. 导入库
import dimod
from dwave.system import DWaveSampler, EmbeddingComposite
# 2. 构造图（这里使用 4 个节点的完全图）
import networkx as nx
G = nx.complete_graph(4)
# 3. 将 Max‑Cut 转为 QUBO
# 对于每条边 (i,j)，若两端自旋相同则贡献 0，异则贡献 1
Q = {}
for i, j in G.edges:
Q[(i, i)] = Q.get((i, i), 0) + 1
Q[(j, j)] = Q.get((j, j), 0) + 1
Q[(i, j)] = Q.get((i, j), 0) - 2
# 4. 使用嵌入复合器提交到量子退火机
sampler = EmbeddingComposite(DWaveSampler())
sampleset = sampler.sample_qubo(Q,
num_reads=1000, # 采样次数
annealing_time=20) # 单次退火时间 (µs)
# 5. 结果分析
best = sampleset.first.sample
cut_value = sampleset.first.energy * -1 # 能量为 -cut
print("最佳切割:", best)
print("切割大小:", cut_value)
解释
EmbeddingComposite自动完成 minor‑embedding。num_reads越大，统计误差越小；annealing_time越长，系统越接近基态。- 通过
sampleset.first.energy可以直接得到最大割的大小（负号是因为 QUBO 求最小化）。
5. 与经典算法的对比
| 维度 | 量子退火 | 经典模拟退火 | 分支限界 / 整数规划 |
|---|---|---|---|
| 搜索机制 | 量子隧穿 + 热激发 | 纯热激发 | 系统性剪枝 |
| 并行度 | 硬件内部天然并行（上千量子比特） | 单核或多核并行模拟 | 受限于 CPU 核心 |
| 时间复杂度 | 受退火时间、链长度影响，常数因子大 | 与退火调度线性相关 | 指数级最坏情况 |
| 解的质量 | 对特定稀疏图表现优异 | 依赖退火速率，易陷局部最优 | 可得到全局最优（但计算成本高） |
| 可扩展性 | 受硬件拓扑限制，需要嵌入 | 受限于内存与 CPU | 受限于求解器实现 |
实验表明，在 稀疏、弱耦合 的大规模图上，量子退火往往能在数毫秒内给出质量可接受的近似解，而经典模拟退火需要数秒甚至数分钟。
6. 常用开发平台
| 平台 | 主要特性 | 适用场景 |
|---|---|---|
| D‑Wave Ocean SDK | 完整的 QUBO/Ising 建模、嵌入、后处理工具 | 直接调用真实量子退火硬件或模拟器 |
| Qiskit Optimization | 将组合优化映射为量子线路，可在 IBM Q 上运行量子近似优化（QAOA） | 研究量子门模型与退火的对比 |
| Microsoft Q# | 提供 QuantumSimulator 与 HybridOptimizer，支持混合量子‑经典工作流 |
教学与原型验证 |
| OpenJij | 基于模拟量子退火（SQA）的开源实现，可在 CPU/GPU 上快速原型 | 无硬件访问时的离线实验 |
使用时，建议先在 模拟器（如 dwave-system 的 SimulatedAnnealingSampler）上验证模型正确性，再迁移到真实硬件，以避免因嵌入错误导致的链断裂。
7. 实践中的注意事项
链强度（chain strength）
- 过小导致链断裂，解失真；过大则占用过多能量，抑制问题本身的求解。
- 常用经验值：
chain_strength = 1.5 * max(|Q_ij|)。
约束惩罚系数
- 约束转化为惩罚项时，系数必须大于任何合法解的目标函数差值，否则会出现违规解。
退火时间与采样次数的平衡
- 对于小规模问题，
annealing_time=5µs、num_reads=100已足够； - 对于大规模稀疏图，建议
annealing_time≥20µs、num_reads≥1000。
- 对于小规模问题，
后处理
- 链断裂后采用 majority vote，但仍可能产生不合法解，需额外的 repair 步骤（如局部搜索）。
硬件拓扑限制
- 在 Chimera 上嵌入密集图会产生长链，导致误差放大。Pegasus 拓扑相对宽松，但仍需合理划分变量。
8. 发展趋势与前景
- 硬件升级：从 2000 量子比特的 D‑Wave Advantage 向 5000+ 量子比特的下一代系统演进，链长度将显著缩短。
- 混合算法：将量子退火与经典元启发式（如遗传算法、局部搜索）结合，形成 Hybrid Quantum‑Classical 框架，已在 D‑Wave 的
HybridSolver中实现。 - 问题特化：针对特定行业（物流、金融、材料设计）定制 QUBO 模型，使量子退火成为 行业加速器。
- 理论突破：研究更优的退火调度曲线（非线性、逆向退火）以及 量子纠错 在退火中的潜在作用，可能进一步提升求解质量。
通过上述步骤，技术人员可以从 问题建模、硬件映射、参数调优 到 结果验证 完整地使用量子退火求解组合优化问题。随着硬件性能的提升和软件生态的成熟，量子退火有望在大规模 NP‑hard 场景中发挥越来越重要的作用。