量子退火应用：组合优化、D-Wave 与工业实践

物理退火（冶金）：
  把金属加热到高温 → 原子随机排列（高能态）
  缓慢冷却 → 原子找到低能排列（晶体结构）
  → 慢冷得到好结构，急冷得到缺陷

模拟退火（经典算法）：
  用「温度参数」控制随机扰动强度
  高温时大胆跳出局部最优，低温时精细收敛
  → 靠「热涨落」逃离局部极小

量子退火：
  用「量子涨落」替代「热涨落」
  通过横向磁场诱导隧穿，穿透势垒
  → 靠「量子隧穿」而非「热跳跃」探索解空间

绝热定理：
  若演化足够慢（相对能隙），系统保持在瞬时基态
  所需时间 ∝ 1 / g_min²
  g_min = 演化过程中的最小能隙

问题：
  最小能隙可能指数小（尤其是「难」实例）
  → 「足够慢」可能需要指数长时间
→ 这就是退火的根本困难：能隙决定成败

绝热量子计算（AQC）：
  理论模型，理想化、无温度、无噪声
  可证明与门模型量子计算等价（多项式意义下）

量子退火（QA）：
  工程实现，有限温度、有噪声、有限时间
  只求解 Ising 型优化问题（不做通用门）
→ 「AQC 是理想模型，QA 是它的工程近似」

D-Wave 已有 5000+ 量子比特
  但：
  1. 连接性稀疏（需要嵌入，见第 6 章）
  2. 无纠错（每个物理比特直接用）
  3. 有效比特数远小于物理比特数
→ 「比特数多」不等于「算力强」，需要看有效连通性

物理载体：超导磁通量子比特（flux qubit）
工作温度：~15 mK（稀释制冷机）
耦合方式：可调磁耦合器（实现 J_ij）
控制：
  h_i（局域场）与 J_ij（耦合强度）可编程
  横向磁场（退火驱动力）全局统一控制
→ 「Ising 机器」：直接硬件实现 Ising 模型

QUBO（Quadratic Unconstrained Binary Optimization）：
  minimize  x^T Q x  ，x_i ∈ {0, 1}

与 Ising 的关系（变量替换 s_i = 2x_i - 1）：
  QUBO ↔ Ising 一一对应
  硬件原生是 Ising，软件接口常是 QUBO
→ 「建模」= 「把业务目标翻译成 QUBO」

硬约束「每个任务恰好分配一次」：
  Σ_j x_ij = 1

转成惩罚项：
  λ · (Σ_j x_ij - 1)²
  = λ · (Σ_j x_ij² + 2Σ_{j<k} x_ij x_ik - 2Σ_j x_ij + 1)

λ 的选择至关重要：
  λ 太小 → 约束被违反（解不可行）
  λ 太大 → 数值范围失衡（退火机精度不够）
→ 「惩罚权重调参」是 QUBO 实践的头号难点

问题：把图的节点分成两组，使「跨组边」数量最大
QUBO 形式（最简洁的例子）：
  变量 x_i ∈ {0,1} 表示节点 i 的分组
  目标：最大化 Σ_{(i,j)∈E} [x_i(1-x_j) + (1-x_i)x_j]
  等价于最小化：-Σ_{(i,j)∈E} (x_i + x_j - 2 x_i x_j)
→ 无约束，天然 QUBO，是退火机的「Hello World」

- 建模最简单（无约束）
- 是 NP 困难的，且与「自旋玻璃」物理直接对应
- 常作为退火机性能基准（benchmark）
- 与量子近似优化（QAOA）的目标问题一致
→ 「Max-Cut 跑得好不好」是退火机的入门体检

问题：给图节点着色，使相邻节点颜色不同，用色数最少
QUBO 建模：
  变量 x_{i,c} = 1 表示节点 i 用颜色 c
  约束 1：每个节点恰好一种颜色 → 惩罚 (Σ_c x_{i,c} - 1)²
  约束 2：相邻节点颜色不同 → 惩罚 Σ_{(i,j)} Σ_c x_{i,c} x_{j,c}
  目标：最小化总惩罚（等价于找可行着色）
→ 「可行性问题」通过「惩罚最小化」来求解

- 最大独立集：约束「相邻不能同时选」
- 最小顶点覆盖：与最大独立集互补
- 二次分配问题（QAP）：工厂-位置分配
- 集合覆盖：用最少集合覆盖全集
- 数独：经典「约束满足转 QUBO」的玩具问题
→ 共性是「离散决策 + 组合约束」

退火机在「小规模 + 特定结构」上表现好
随问题规模增长：
  嵌入开销上升（见第 6 章）
  退火时间需要更长
  与最优解的差距（近似比）下降
→ 目前没有「大规模 + 通用」的优势证据

问题：问题图（稠密）无法直接映射到硬件图（稀疏）
解决：把一个「逻辑变量」用「多个物理比特」表示
  这组物理比特称为一个「链」（chain）
  链内比特通过强耦合 J_chain 强制取相同值

代价：
  一个逻辑变量占 k 个物理比特 → 有效规模缩小 k 倍
  稠密问题图的 k 可能很大（几十个比特/变量）
→ 「嵌入开销」是退火机规模化的最大障碍

现象：
  退火结束时，同一条链内的物理比特「不一致」
  （有的取 0、有的取 1）

原因：
  链内耦合 J_chain 不够强
  热涨落或量子涨落破坏了一致性
  问题本身的耦合与链耦合竞争

后果：
  该逻辑变量的取值「模糊」→ 需要用「多数投票」修复
  投票可能给出错误值 → 解的质量下降

J_chain 太小：
  链断裂频繁 → 解不可靠

J_chain 太大：
  占用硬件的动态范围 → 问题耦合被压缩
  等效于「降低问题项的精度」
→ 存在最优 J_chain（工程上靠自动调参搜索）

基本参数：
  退火时间 t_a：从 H_0 演化到 H_P 的总时长
  调度曲线 s(t)：横向磁场的关闭速率
  停顿（pause）：在中途暂停，给系统「时间」隧穿

直觉：
  t_a 越长 → 越接近绝热 → 质量越好（但有上限，受退相干限制）
  非均匀调度（前快后慢）常优于线性调度
  中途停顿可以「等待」系统穿过小能隙
→ 「调度设计」是退火优化的核心手段

理论：绝热定理说越慢越好
现实：
  退火期间有热噪声与退相干 → 时间越长，噪声累积越多
  硬件有相干时间上限
  → 存在「最优退火时间」，不是越长越好
→ 这是退火机与理想 AQC 的关键差别

- 车辆路径规划（VRP）：多车配送的路线优化
- 航班/列车调度：资源冲突消解
- 仓储拣货路径：仓库内最优行走路线
- 作业车间调度（Job Shop）：机器-任务分配
现状：多为「概念验证」，规模受嵌入开销限制

- 投资组合优化：在风险约束下最大化收益
  （Markowitz 模型的离散版本天然是 QUBO）
- 交易结算：多边净额结算的最优匹配
- 信用评分 / 反欺诈：特征选择（选哪些特征）
现状：组合优化是退火最「对口」的金融应用

1. 求解质量优势：
   同样时间预算下，退火给出更优解
2. 求解速度优势：
   达到同样质量，退火用时更短
3. 规模化优势：
   问题越大，退火相对经典的优势越明显
→ 三者都需「公平基线」，而基线选择常引发争议

常见问题：
  □ 经典基线用了「朴素算法」而非「最优求解器」
  □ 时间预算不对等（退火用长预算，经典用短预算）
  □ 只报告「成功案例」而非「全实例分布」
  □ 忽略嵌入开销（退火的有效变量数远小于声明）
→ 「量子优势」的声称必须通过「公平基线」的检验

值得尝试：
  □ 问题天然是二进制离散决策
  □ 变量数在「几十到几百」量级
  □ 图结构相对稀疏（嵌入开销可控）
  □ 已有经典解，想「再压一压」质量
  □ 有探索性研究的预算

不值得尝试：
  □ 规模上万变量
  □ 需要精确最优解
  □ 已有成熟专用求解器且性能足够
  □ 约束极复杂（惩罚权重难以调平）
  □ 要求「生产级」可靠性

主流架构：
  1. 经典前端：问题建模 → QUBO
  2. 经典预处理：分解、热启动、参数搜索
  3. 量子退火：求解子问题 / 局部改进
  4. 经典后端：解修复、可行性校验、迭代

关键：量子只做「经典做不好的那部分」
  → 不是「用量子替代经典」，而是「量子做协处理器」
→ 见 /quantum-hybrid-quantum-classical/

1. 先建经典基线：用最优经典求解器测出「最好能到哪」
2. 再建 QUBO：注意系数归一化与惩罚权重
3. 调参：退火时间、链强度、采样次数、调度
4. 公平对比：同时间预算、同实例分布、报全分布
5. 记录嵌入开销：报告「有效变量数」而非物理比特数
6. 迭代：混合方案 + 问题分解逐步扩大规模
→ 六步是「退火项目」的最小可行流程