技术摘要：用于人员排班的约束保持型 QAOA

问题陈述

人员排班是一个具有硬性操作约束（如每日覆盖需求和连续工作天数限制）的组合优化问题。虽然经典方法（整数规划、元启发式算法）已取得成功，但随着系统规模增长带来的指数级搜索空间增长，促使人们使用量子算法，特别是量子近似优化算法（QAOA）。

标准的约束问题 QAOA 表述通常依赖于基于惩罚项的方法。在这种框架下，通过在相位哈密顿量中添加能量惩罚项来强制执行硬约束。这种方法存在显著缺陷：

1. 校准敏感性： 性能高度依赖于惩罚系数的选择。
2. 景观扭曲： 过大的惩罚会扭曲优化景观。
3. 不可行性可达性： 不可行配置在变分演化过程中在动力学上仍然是可达的，这使得量子振幅可能会在那些本应被禁止的区域积累，即使这些区域在能量上受到了惩罚。

本文旨在解决对约束保持型 QAOA 框架的需求，该框架将硬约束直接嵌入到混合器（mixer）哈密顿量中，从而将量子演化严格限制在可行子空间内。

方法论

1. 数学表述

作者将一个包含 $N$ 名员工和 $D$ 天的二元人员排班问题进行了建模。状态由二元矩阵 $q \in \{0,1\}^{N \times D}$ 表示，其中 $q_{n,d}=1$ 表示员工 $n$ 在第 $d$ 天被分配值班。
该问题涉及最小化分配成本 $C(q)$，并受两个硬约束限制：

• 每日覆盖： $\sum_{n} q_{n,d} = W_d$（每日固定劳动力人数）。
• 禁止连续值班： $q_{n,d} q_{n,d+1} = 0$（员工不得连续两天工作）。

配置空间具有层级结构：

• $\mathcal{H}$：完整的二元希尔伯特空间。
• $\mathcal{F}_{cov}$：仅满足覆盖约束的子空间。
• $\mathcal{F}_{full}$：同时满足两个约束的子空间（完全可行流形）。

2. 混合器构建

论文提出了对应于不同可行扇区的层级混合器哈密顿量：

• Penalty-X（基准）： 使用标准的横向场混合器 ($\sum X_{n,d}$)，并通过相位哈密顿量中的能量惩罚来强制执行两个约束。
• Coverage-XY： 使用 XY 混合器，该混合器为每一天保留激发数（劳动力数量）。这在动力学上保留了 $\mathcal{F}_{cov}$，但仍需通过惩罚项来处理禁止连续值班的约束。
• Guarded-XY（提议方法）： 引入了一种受保护的转换算符（guarded transition operator），将两个约束都直接嵌入到混合器中。
  • 保护机制： 对于在第 $d$ 天提出的两个员工 $u$ 和 $v$ 之间的交换，该算符包含一个“保护投影算符” $\hat{G}$。该投影算符会评估相邻天数（$d-1, d+1$）的状态，如果交换会导致违反禁止连续值班的规则，则该算符将变为零。
  • 结果： 混合器 $\hat{H}_{M}^{guard}$ 仅在 $\mathcal{F}_{full}$ 内产生转换。因此，相位哈密顿量简化为仅包含目标函数本身（$\hat{H}_C = \hat{H}_{obj}$），消除了对硬约束惩罚系数进行校准的需求。

3. 可达性与紧凑模式扩展

作者指出，精确的约束保持并不保证可达性（即可行图的连通性）。在“饱和”的工作量片段中，当 $W_d + W_{d+1} = N$ 时，禁止连续值班的约束会迫使分配方案互补，从而可能将可行图分割成不连通的分量。

• 解决方案： 引入了紧凑模式扩展（tight-pattern extension）。它增加了集体交换算符，可以在饱和片段中交换整个交替分配模式，从而在不违反约束的情况下恢复 $\mathcal{F}_{full}$ 内的连通性。

4. 模拟协议

研究使用精确态矢量模拟在基准实例（$N=4, D=4$，工作量 $W=[2,1,2,1]$）上进行。

• 对比： 对比了 Penalty-X、Coverage-XY 以及带有紧凑模式扩展的 Guarded-XY。
• 优化： 在期望值（Expectation-Value）和条件价值风险（CVaR, $\alpha=0.2$）目标下进行评估。
• 校准： 基准方法的惩罚系数经过严格校准以确保公平比较，而 Guarded-XY 则无需此类校准。
• 初始化： 测试包括在可行扇区上的均匀叠加态以及局部的可行起始态。

关键结果

1. 消除了惩罚校准

Guarded-XY 方法成功消除了调节硬约束惩罚系数的需求。其相位哈密顿量仅包含分配成本，简化了变分景观。

2. 更优的输出分布质量

• 可行性： 通过构造，Guarded-XY 保持 $P_{full} = 1$（100% 的可行状态概率）。相比之下，Coverage-XY 和 Penalty-X 即使在优化了惩罚项后，仍表现出向不可行区域的泄漏（$P_{full} < 1$）。
• 最优浓度： 在 CVaR 优化下，Guarded-XY 始终能比其他方法获得更高的采样精确最优调度方案的概率（$P_{opt}$）。
• 解的质量： Guarded-XY 实现了最高的平均近似比（$\langle r \rangle$）。论文指出，部分约束保持方法（如 Coverage-XY）经常会将显著概率分配给具有人为极低原始成本的不可行调度方案，这会使优化偏离真实的可能可行最优解。

3. 结构敏感性与初始化

• 饱和工作量： 研究表明，为了在高度饱和的工作量场景中维持连通性，紧凑模式扩展是必要的，否则会防止可行图发生破碎。
• 初始化： 该框架在从单个局部可行调度（而非均匀叠加态）进行初始化时依然有效，前提是应用少量的“扩散”混合器层。这表明了一种硬件友好的初始化策略。
• 可扩展性： 在不同量子比特数（12, 16, 20）的实例测试显示，虽然由于搜索空间增大导致原始最优概率下降，但最优态富集度（$\eta_{opt}$）保持在高水平，表明该算法能够持续相对于均匀采样来放大最优解。

意义与主张

该论文声称提出了第一个针对人员排班的系统性约束保持型 QAOA 表述，其中两个硬性调度约束都直接嵌入到了混合器哈密顿量中。

核心贡献包括：

1. 约束处理方式的转变： 将约束强制执行从能量相位哈密顿量转移到动力学混合器中，确保演化在构造上被限制在可行流形内。
2. 设计原则的分离： 区分了可行性保持（确保混合器留在可行集内）与可达性设计（确保可行集是连通的）。Guarded-XY 混合器处理前者，而紧凑模式扩展处理后者。
3. 通用性： 作者断言，这种转换图框架和受保护转换原则适用于一类广泛的受限量子优化问题（如调度、路由、资源分配），其中可行性可以通过局部转换规则来表征。

这项工作证明了约束保持型混合器可以提供比基于惩罚的方法更高质量的输出分布和更强的最优解集中度，且无需对惩罚系数进行校准。