QTIS：一种基于QAOA（Quantum Optimization Algorithm）的量子时间间隔调度器

《Future Generation Computer Systems》：QTIS: A QAOA-based Quantum Time Interval Scheduler

　　何塞·A·蒂拉多-多明格斯（José A. Tirado-Domínguez）| 埃拉迪奥·古铁雷斯（Eladio Gutiérrez）| 奥斯卡·普拉塔（Oscar Plata）
马尔加大学计算机架构系，安达卢西亚理工大学，马尔加，29010，西班牙

**摘要**
在制造、物流、云计算和医疗保健等领域，具有时间间隔限制和资源限制的任务调度仍然是一个基本挑战。本研究提出了一种新型的量子近似优化算法（QAOA）变体，用于解决被构建为二次无约束二进制优化（QUBO）模型的任务调度问题。所提出的方法称为量子时间间隔调度器（QTIS），它整合了一个辅助量子电路来动态检测和惩罚重叠任务，从而增强了调度约束的执行。探索了两种互补的重叠检测实现方式：一种基于RY旋转和CCNOT门的量子方法，另一种依赖于预处理区间比较的经典方法。

QTIS将问题哈密顿量（HP）分解为两个部分，每个部分由不同的角度参数化。第一部分编码目标函数，而第二部分捕获与重叠区间相关的惩罚项，这些惩罚项由辅助电路控制。随后评估了三种最小化策略：标准QAOA最小化、T-QAOA和HT-QAOA，结果表明，为问题哈密顿量的不同部分使用不同的参数可以降低能量值并提高解决方案的质量。

结果证实了QTIS在调度具有固定时间窗口的任务同时最小化冲突方面的有效性，突显了其作为结构化、考虑约束的调度问题的混合量子-经典框架的潜力。

**引言**
任务调度是一个基本的优化问题，在工业[1]、[2]、物流和运输[3]、计算[4]、[5]或医疗保健[6] [7]等多个现实世界领域中都有应用。
传统上，任务调度使用经典旅行商问题（TSP）[8] [9]或作业车间问题（JSP）[10]进行建模，其目标是确定任务到资源的最佳序列和分配，以满足预定目标，例如最小化成本、最大化吞吐量或确保及时完成[11]。
这些问题属于NP难组合优化问题[12]类别，正如Graham等人[13]所指出的，随着问题规模的增加，找到保证的最优解在计算上变得不可行。这种固有的复杂性需要使用近似方法，如启发式[14] [15]和元启发式[16] [17] [18] [19]，以便在合理的时间内解决现实世界中的大规模实例。
尽管经典算法可以加速解决方案的搜索，但优化问题也可以从先进的计算范式中受益，特别是量子计算，它为在高并发环境中管理复杂场景提供了有前景的方法[20] [21]。
在这方面，绝热量子计算（AQC）[22] [23]是一种特别适合解决组合优化问题的范式[24] [25]。在AQC中，优化问题被编码到一个哈密顿量中，其基态对应于最优解。系统最初被准备在一个简单哈密顿量的基态，然后根据绝热定理缓慢演化到问题哈密顿量的基态[26]。
除了绝热量子计算之外，其他量子计算范式，如基于门的量子计算，在解决组合优化问题方面也被证明是有效的[27] [28] [29]。这些通用量子计算系统通过执行由门组成的量子电路来操作量子比特，这些门在一组量子比特上实现幺正算子。对量子比特的相干和受控操作使得量子算法能够在某些优化情境中超越经典方法[21] [30]。
尽管量子优势在理论上很有前景，但量子算法在现实世界应用中的实际部署目前受到噪声中等规模量子（NISQ）设备[31] [32]可用硬件的限制。这些系统对噪声非常敏感，仍然存在短退相干时间的问题，并且在可可靠执行的量子比特数量和电路深度方面受到限制。因此，它们的固有局限性阻止了它们独立解决大规模优化问题，从而激发了混合经典-量子框架[33] [34]的发展。
混合经典-量子范式结合了量子算法和经典计算资源，利用了量和经典计算的互补优势，并在某些方面明显优于纯经典技术。特别是，变分量子算法（VQAs）已成为NISQ时代优化任务的主要候选者[35]。这些混合方法依赖于参数化的量子电路来生成候选解，而经典优化器则迭代更新参数以最小化预定义的成本函数。通过这种反馈循环，量子-经典系统逐步引导电路接近问题的最优解。
最广泛研究的两种变分算法是变分量子特征值求解器（VQE）[30]和量子近似优化算法（QAOA）[21] [36]。
VQE算法旨在确定系统哈密顿量的最低特征值及其对应的本征态。最初是为量子化学和材料科学[37] [38]开发的——其中分子或材料的基态决定了其性质——VQE后来被扩展到连续优化、图论问题和各种工业应用。该方法依赖于量子力学的变分原理，该原理保证任何试探态（ansatz）C=Ψ(s)|H|Ψ(s)的哈密顿量期望值提供了真实基态能量的上界。
量子近似优化算法（QAOA）[21]是一种领先的变分算法，用于组合优化问题，如MaxCut、TSP、VRP和作业车间调度。它通过模拟从问题哈密顿量HP和混合器哈密顿量HB派生的交替幺正算子序列的绝热演化来近似最优解。这些算子由变分角度γ和β控制，这些角度由经典优化器迭代更新，以最小化预期能量，从而引导系统朝向编码所需解决方案的HP的基态配置。
已经提出了多种QAOA变体来提高性能、可扩展性和适用性，包括多角度QAOA[39]、XQAOA[40]、QAOA+ [41]、两步QAOA[42]和量子交替算子ansatz[43]。在这项工作中，我们提出了一种新型的QAOA算法，用于解决具有严格时间限制（包括开始时间和持续时间）的任务调度问题。
正式地，问题定义如下：
给定一组具有预定义持续时间和开始时间的任务，以及一组有限的资源，目标是确定一个可行的调度方案，该方案满足将每个任务分配给单个资源的要求，同时严格避免在同一资源上同时执行。
图1展示了一个问题的示例。一组八个任务（T1…T8），每个任务都有预定义的开始时间和持续时间，被分配到三个资源（R1、R2、R3）上。调度的可行性由具体的资源分配决定：在调度A中，实现了无冲突的分配，满足了所有时间约束。相比之下，调度B显示了一个不可行的分配，其中资源发生重叠，导致执行冲突，尽管所有任务都被正式分配给了一个资源。
这种涉及固定时间间隔和有限资源的调度问题出现在许多实际情境中。示例包括工业维护、准时生产、飞机起飞和降落、公共交通、计算集群、云作业分配和外科手术程序调度。在所有情况下，任务必须在预定义的时间窗口内分配给资源，同时遵守容量约束。高效的调度对于优化资源利用和最小化延迟或停机时间至关重要。这些应用的多样性表明了时间约束调度问题的普遍性，并激发了探索量子计算方法以实现更有效优化的需求。
为了解决这个调度问题，我们将其构建为一个二次无约束二进制优化（QUBO）问题，将时间和资源约束编码到一个成本函数中，其可行解代表近似最优的任务分配。
与基线QAOA框架相比，我们的方法引入了一个辅助量子电路，该电路明确检测任务冲突并将这些信息编码在变分框架中。在这种情况下，ansatz涉及将问题的哈密顿量分为两个不同的哈密顿量。第一个用于编码问题并将其分配给资源，第二个负责处理两个任务不能在同一资源上同时执行的约束。

**主要贡献**
首先，具有严格时间限制的任务调度问题被构建为一个二次无约束二进制优化（QUBO）模型，允许其在量子优化框架中表示。其次，定义了一个用于检测时间冲突的量子电路，结合了两种针对不同调度情境的替代方案。第三，提出了一种新型的原始量子近似优化算法（QAOA）变体，称为量子时间间隔调度器QAOA（QTIS-QAOA）。这种构建引入了三个哈密顿量，Hp、Hc和HB，其中Hp编码优化目标，Hc执行时间冲突约束，HB代表标准混合器哈密顿量。此外，还证明了可以使用来自辅助量子子电路的元素构建ansatz电路，有效地将约束信息嵌入到变分形式中。还表明，为Hc哈密顿量使用不同的参数集，而不是与Hp共享相同的γi参数，可以提高QTIS-QAOA算法的优化性能。最后，引入了一种ansatz电路的参数初始化方法HT-QAOA，能够在不显著增加计算成本的情况下提高解决方案的准确性。

本文的其余部分组织如下：第2节提供了关于QAOA和相关工作的背景。第3节介绍了问题的构建及其转换为QUBO模型的过程。第4节描述了修改后的QAOA算法的原理。第5节说明了辅助量子电路在执行约束中的作用。第6节讨论了实验结果和性能分析。最后，第7节总结了关键见解和未来研究的方向。

**QAOA**
量子近似优化算法（QAOA）是一种受绝热定理[44]启发的优化算法。它基于时间依赖的薛定谔方程，该方程描述了在哈密顿量下量子系统状态的时间演化：i???t|Ψ(t)〉=H?(t)|Ψ(t)〉
如果H(t)是时间独立的，方程（1）的解形式为：|Ψ(t)〉=∑ncn(0)e?iEn(0)?t|n(0)〉
其中En(0)和|n(0)〉是由初始哈密顿量定义的特征值和特征向量。

**问题构建**
我们考虑在资源有限的情况下调度一组任务的问题，受到以下约束：
1. 每个任务都有固定的执行持续时间和预定义的时间窗口，由开始时间和结束时间（tend=tstart+duration）确定，这些时间不能任意修改。
2. 可用的执行资源是有限的，每个资源在任何给定时间只能执行一个任务。
3. 一些任务可能在时间上重叠，阻止它们在同一资源上执行。

**QTIS-QAOA**
在第3节中提出的构建基础上，本节介绍了QTIS（量子时间间隔调度器），这是标准QAOA算法的一个修改版本，旨在解决相应的任务调度问题。
如理论背景所述，QAOA通过交替两个参数化的幺正算子U(HP,γi)和U(HB,βi)在深度为L的电路上操作，这两个算子分别来自问题哈密顿量HP和混合器哈密顿量HB。在每一层，

**冲突检测**
如前一节所述，重叠系数cik将作为一组辅助量子比特包含在QTIS-QAOA ansatz中，用于控制Hc哈密顿量中编码的约束惩罚的应用。
在这项工作中，我们提出了两种不同的策略来在控制量子比特中编码重叠信息。第一种方法——全量子——使用量子电路估计任务重叠，这只需要最小的经典预处理来规范化时间。

**模拟和结果**
为了验证QTIS算法，我们进行了一系列测试，具有双重目标：
1. 为QTIS-QAOA ansatz确定一个合适的最小化策略，能够在可用资源中找到有效的任务分配。
2. 确定引入第三组参数ζ→（专门用于Hc电路，而不是与Hp电路共享γ→参数）是否可以改进最小化过程。

**结论**
本文解决了任务调度问题，这是一个属于NP难组合优化问题类的挑战。与通常旨在最小化总执行时间（makespan）的标准作业车间调度（JSSP）方法不同，本研究解决了一个具有严格时间约束的情景，其中任务必须在特定的、不可协商的时间窗口内执行。因此，优化目标从时间压缩转变为在CRedi内最大化可行性。

**作者贡献声明**
何塞·A·蒂拉多-多明格斯（José A. Tirado-Domínguez）：撰写——审阅与编辑、撰写——原始草稿、可视化、验证、方法论、调查、形式分析、概念化。埃拉迪奥·古铁雷斯（Eladio Gutiérrez）：负责写作、审稿与编辑工作，以及项目的监督和概念构思。奥斯卡·普拉塔（Oscar Plata）：同样负责写作、审稿与编辑工作，以及项目的监督和概念构思。

利益冲突声明：
作者声明他们不存在任何可能影响本文研究结果的已知财务利益冲突或个人关系。