Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

本文提出了一种基于对称性的方法，用于在量子计算的开放车间调度问题中编码硬约束，并设计了一种新颖的变分算法，该算法利用保持可行性的置换群，仅通过优化二次方数量的参数即可确保以确定性方式达到最优解。

要点

以下是该研究论文的通俗解释，辅以富有创意的类比。

宏观图景：量子谜题盒

想象你是一位物流经理，正在调度一支送货卡车车队。你有一份工作清单（送货任务）、一组机器（卡车）和一个时间线（时间段）。规则非常严格：

1. 每份工作必须且只能完成一次。
2. 任何卡车不能同时出现在两个地方。
3. 任何时间段不能安排两份工作。

这被称为开放车间调度问题（OSSP）。这是一个经典的“困难”谜题。如果你尝试用普通计算机解决它，可能需要耗费永恒的时间，因为需要检查的错误组合实在太多了。

这篇论文的作者问道：我们能否利用量子计算机更快地解决这个问题？

问题在于，目前的量子计算机就像笨拙的蹒跚学步幼儿；它们很容易犯错。如果你只是让它们“找到最佳时间表”，它们往往会误入“禁区”（即违反规则的时间表，例如在同一时间将两份工作分配给同一辆卡车）。

该团队的解决方案是构建一个只懂得在“安全路径”上行走的量子机器人。他们设计了一种新算法，从物理上防止计算机考虑任何非法的时间表。

---

核心思想：“对称性”钥匙

要理解他们的技巧，想象一个挤满了人（代表所有可能的时间表）的房间。

• 坏的时间表： 站在错误位置的人（违反规则）。
• 好的时间表： 站在正确位置的人。

大多数量子算法试图通过给“坏”人施加沉重惩罚（比如罚款）将他们推出房间。但这很混乱。坏人可能仍然徘徊不去，或者惩罚力度不够。

作者的方法：
他们意识到，与其惩罚坏人，不如利用“好的时间表”所具有的隐藏对称性。
把工作想象成舞者，把时间段想象成舞伴。如果你有一套完美的舞蹈编排（一个有效的调度方案），你可以以特定的方式交换舞伴，而你仍然拥有一套完美的编排。

作者发现了一个数学上的“群”（一组规则），精确描述了如何在不违反规则的情况下对这些工作进行洗牌。他们称之为可行性保持群。

类比：
想象一个魔方。

• 标准方法： 你试图通过随机转动各个面来还原它，同时希望不要弄乱你已经固定的颜色。
• 本文的方法： 你意识到，如果你只按照特定的、预先批准的方式（对称性）转动魔方，你就保证会保持在颜色依然对齐的状态。你完全不必担心“弄坏”魔方，因为你的每一步移动在数学上都是设计用来保持其还原状态的。

新算法：“洗牌”机器

这篇论文提出了一种利用这种对称性的新型量子算法（变分量子算法）。

1. 从安全开始： 你让计算机从一个有效的调度方案（一个“种子”解）开始。
2. 混合器： 计算机不应用随机噪声，而是应用一种特殊的“混合器”门。这个门就像一个洗牌按钮，它只以数学上保证能保持调度方案有效的方式交换工作。
3. 保证： 作者证明了一个非常强有力的数学事实：如果你有 $J$ 份工作，你只需要调整特定且可管理的数量的“旋钮”（参数），就能到达任何可能的有效调度方案，包括绝对最佳的那个。

“旋钮”类比：
想象你有一个带有组合锁的巨大保险箱。

• 旧量子方法： 你必须通过尝试数十亿个随机数字来猜测组合。你可能会走运，但也可能陷入死胡同。
• 这种方法： 作者找到了地图。他们证明，你只需要转动 $J^3$（大约是工作数量的立方）个特定的旋钮，就能打开保险箱里的每一扇门。这就像拥有一把万能钥匙，只要你按正确的顺序转动正确的拨盘，就能打开每一扇门。

他们实际做了什么（证明）

这篇论文不仅仅停留在理论上；他们进行了测试。

1. 模拟： 他们在经典计算机上模拟了一个小型问题版本（4 份工作，2 台机器）。

   • 结果： 旧方法（对坏时间表使用“罚款”）未能找到好的解决方案。它被困在了“禁区”里。
   • 结果： 他们的新方法严格保持在“安全路径”上，迅速找到了完美解决方案。

2. 真实硬件测试： 他们将一个微小版本的问题（3 份工作，1 台机器——基本上是一个旅行商问题）在真实的量子计算机（IBM Q System One）上运行。

   • 结果： 即使真实计算机充满噪声（就像带有静电的收音机），他们的算法仍然比随机猜测更频繁地找到最佳解决方案。这表明即使在不完美的硬件上，“安全路径”的逻辑也是有效的。

结论

这篇论文是关于为量子计算机建立护栏。

与其指望计算机留在道路上，他们重新设计了汽车，使其无法离开道路。通过利用调度问题的数学对称性，他们创造了一种算法，该算法：

• 从不考虑不可能的调度方案。
• 可以通过转动特定且有限数量的旋钮到达完美解决方案。
• 即使在当今嘈杂、不完美的量子机器上，其表现也优于现有方法。

他们尚未为世界上每个行业解决该问题，但他们为求解这种特定类型的调度谜题构建了一个更可靠的新引擎。

技术摘要

技术摘要：基于对称性的开放车间调度硬约束量子算法

问题陈述
本文探讨了开放车间调度问题（OSSP），这是一个组合优化问题，要求将 $J$ 个作业分配到 $M$ 台机器上，每台机器拥有 $T$ 个时间槽。约束条件要求每个作业必须恰好执行一次，且每个机器 - 时间槽分配不能包含超过一个作业。该问题是旅行商问题（TSP）的推广，其中 $TSP = OSSP(1, T, T)$。

核心挑战在于如何将此类“硬约束”编码到变分量子算法（VQAs）中。与无约束问题（如 MAX-CUT）或具有“软编码”约束的问题（即在目标函数中对不可行性进行惩罚）不同，OSSP 要求优化过程严格保持在可行子空间内。软编码往往导致次优的优化景观或可行性问题。虽然量子交替算子 ansatz（QAOA）通过保持可行性的混合器为硬约束提供了框架，但现有针对调度问题的构建往往是启发式的，未能充分利用问题底层的对称结构。

方法论
作者采用严谨的群论方法结合图论来分析 OSSP 的可行结构：

1. 约束图模型：问题被映射到约束图 $G=(V, E)$，其中顶点代表潜在的作业分配（位），边代表禁止同时分配的约束。解对应于大小为 $J$ 的独立集（团）。
2. 保持可行性的群（$F$）：作者识别出将可行解映射为其他可行解的位值置换群 $F$。他们证明，对于 OSSP，该群同构于约束图的自同构群，即 $\text{Aut}(G)$。
   • 对于“繁忙”情况（$MT = J$），群结构是涉及对称群的半直积（wreath product）。
   • 关键的是，他们证明了 $F$ 在所有可行解集合上传递作用。这意味着任何可行解都可以通过 $F$ 中的一系列置换转换为任何其他可行解。
3. 算法设计：
   • QAOA 扩展：通过直接从 $F$ 的生成元构建混合器来完善 QAOA 框架。由于 $F$ 具有传递性，由其元素导出的混合器保证了整个可行子空间的可访问性。
   • 新型 VQA（量子群优化）：针对繁忙的 OSSP 实例，作者提出了一种绕过标准相位分离器的新算法。通过将对称群 $S_J$（代表繁忙 OSSP 的解空间）中的置换分解为对换的乘积，他们利用 SWAP 门构建了参数化电路。
   • 参数化：该算法利用将置换分解为 $J(J-1)/2$ 个对换的特定分解。每个对换被实现为跨作业块的互不相交 SWAP 门的乘积。

主要贡献

• 理论表征：本文提供了 OSSP 保持可行性的群的完整表征，证明了其同构于约束图的自同构群，并确立了其在解集上的传递作用。
• 保证可达性：与通用 QAOA 仅在电路深度无限（$p \to \infty$）时保证达到最优解不同，所提出的 VQA 提供了参数的严格上界。作者证明，$O(J^3)$（具体为 $J(J-1)/2$）个参数足以以确定性概率到达任何可行解，包括全局最优解。
• 硬约束实现：该工作展示了一种系统性的方法来构建严格保持可行子空间的混合器，避免了软编码约束的陷阱。
• 硬件实现：作者在真实量子设备（IBM Q System One）上针对 $OSSP(1, 3, 3)$ 实例（等价于 3 城市 TSP）实现了该算法，并针对 $OSSP(2, 2, 4)$ 实例进行了无噪声模拟。

结果

• 无噪声模拟（$OSSP(2, 2, 4)$）：带有硬编码约束的所提 VQA 在六次迭代内（优化 12 个参数）成功达到了全局最小值（近似比为 100%）。相比之下，带有软编码约束的标准 QAOA 即使访问所有 18 个参数，由于难以在微小的可行子空间中集中振幅，其近似比也未超过 30%。
• 真实硬件（$OSSP(1, 3, 3)$）：在 IBM Q System One 上，该算法展示了离开初始状态并增加与局部最优解重叠的能力。然而，作者指出，硬件噪声严重掩盖了向全局最优解的收敛，噪声背景主导了信号。经典噪声模拟显示出更好的收敛性，这表明当前的硬件限制（相干时间、门保真度）是主要瓶颈，而非算法设计本身。

意义与主张
本文声称其主要意义在于为 VQAs 中的硬编码约束提供了一个系统性的、基于对称性的框架，超越了启发式的混合器设计。通过将问题的可行结构与图自同构联系起来，作者推导出了一个算法，该算法具有理论保证，即多项式数量的参数（$O(J^3)$）足以探索整个解空间。

作者对实际可扩展性持谨慎态度。他们承认，虽然理论参数界限很强，但这些参数的实际优化受到“ barren plateaus（ barren 高原）”和高维空间中指数级局部最小值的阻碍。此外，他们明确指出，他们的方法依赖于等式约束（对称性），可能不直接适用于缺乏此类对称性的不等式约束问题（如背包问题）。这项工作作为一个原理验证，证明了只要未来的硬件改进解决了噪声和连通性问题，保持可行性的群结构就可以被用来为调度问题设计更高效且具有理论基础的量子算法。