Quantum Optimization for Constraint-Aware Scheduling

by José A. Tirado-Domínguez, Eladio Gutiérrez, and Oscar Plata (University of Malaga)

Could quantum computing help address complex scheduling problems? We explore this question by proposing a structured problem representation that isolates constraints from optimization objectives. Our framework improves solution quality using fewer circuit layers than conventional implementations.

In the field of high-performance computing, task scheduling remains one of the most important optimization challenges. Across domains as diverse as air traffic control, hospital operating rooms, and future 6G communications networks, the challenge is to schedule activities with fixed durations within strict time windows while making efficient use of limited resources and avoiding overlaps. The combination of these temporal and resource constraints gives rise to problems that are often classified as NP-hard, with complexity growing exponentially as the number of tasks increases, making them difficult to solve using traditional classical methods.

Quantum computing offers a promising avenue for tackling complex optimization problems. While current Noisy Intermediate-Scale Quantum (NISQ) devices are still limited in scale and highly sensitive to noise, they provide an ideal platform for exploring new computational paradigms. In this context, we have developed QTIS (Quantum Time Interval Scheduler) [1], a hybrid quantum–classical framework designed to manage time intervals while exploring new approaches to resource allocation and constraint-aware scheduling.

The Hybrid Approach: A Bridge to the Future
At the core of QTIS lies a variant of the Quantum Approximate Optimization Algorithm (QAOA) [2], one of the most promising optimization techniques in the current NISQ era. Inspired by the principles of quantum annealing, QAOA builds a solution through a sequence of parameterized quantum operations that alternate between encoding the optimization problem and exploring new candidate states. The parameters governing these operations are iteratively tuned by a classical optimizer, which acts as a "coach" that guides the quantum circuit toward increasingly better solutions. This creates a hybrid quantum–classical workflow capable of tackling complex combinatorial problems.

What Makes QTIS Different? Divide and Conquer
Most conventional quantum scheduling approaches encode both the optimization objective and the scheduling constraints within a single mathematical formulation known as the problem Hamiltonian, which guides the quantum optimization process. QTIS takes a different approach.

Rather than treating this formulation as a single block, QTIS decomposes it into separate terms, each responsible for a specific aspect of the scheduling problem:

• The objective Hamiltonian: focused exclusively on what we want to achieve, namely selecting the best possible set of tasks.
• The constraint Hamiltonian: a guardian that ensures the rules of the problem are respected by preventing tasks assigned to the same resource from overlapping in time.
• The mixer operator: the quantum mechanism that enables the exploration of different candidate solutions across the search space. 

nlike the complex problem-specific mixers proposed in [3], we employ the standard mixer to reduce circuit overhead.
This separation is more than a mathematical convenience. By assigning independent parameters to the objective and constraint components, QTIS can balance optimization goals and scheduling constraints more effectively than conventional QAOA implementations. Experimental results show that QTIS consistently outperforms standard QAOA when using circuits of the same depth (see Figure 1). In most cases, QTIS with 10 layers achieves better solutions than a conventional QAOA implementation using 15 layers, demonstrating that a more structured problem representation can improve solution quality while reducing quantum resource requirements.

The Damselfly Gate: Detecting Scheduling Conflicts
One of the greatest challenges in scheduling is determining whether two tasks assigned to the same resource overlap in time. To address this issue, QTIS introduces an ancilla-assisted quantum subcircuit that explicitly incorporates conflict detection into the optimization process.

The framework supports two alternative approaches. In the Full Quantum variant, task overlaps are estimated directly within a quantum circuit by encoding temporal relationships into quantum states through parameterized rotations. Ancillary qubits are then used to mark potential conflicts between pairs of tasks. In the hybrid quantum–classical variant, overlap detection is performed classically and the resulting conflict information is transferred to the quantum circuit, providing a more deterministic alternative for noisy quantum hardware.

At the heart of the quantum approach lies a custom structure, which we call the Damselfly gate. Whenever an overlap is detected, the corresponding ancilla qubit activates a penalty in the constraint component, increasing the cost of invalid schedules. In this way, QTIS is naturally guided away from conflicting task assignments while converging on the optimal schedule. 

A Smarter Starting Point
The quality of the solutions produced by QTIS depends not only on the quantum circuit itself, but also on how its parameters are initialized and optimized. To explore this aspect, we evaluated three optimization strategies: conventional parameter minimization, a progressive approach known as T-QAOA, and our newly developed method, Homotopy-Transfer QAOA (HT-QAOA).

Inspired by the principles of quantum annealing and homotopy optimization, HT-QAOA first optimizes a simple quantum circuit and then uses the resulting parameters as a guide for circuits with a larger number of layers. By transferring information from a simpler optimization stage to a more complex one, the algorithm starts its search from a more informed configuration.

This strategy improves the chances of finding high-quality schedules without increasing the computational cost. In the QTIS experiments, HT-QAOA achieved competitive performance while maintaining execution times comparable to those of standard optimization methods.

Looking Ahead
QTIS demonstrates how quantum computing can already contribute to solving real-world scheduling problems, even within the limitations of current NISQ hardware. By combining a novel problem decomposition, ancilla-assisted conflict detection through the Damselfly gate, and advanced optimization strategies such as HT-QAOA, the framework provides a new perspective on constraint-aware scheduling. Although practical quantum advantage remains a long-term goal, QTIS highlights how today's quantum devices can serve as a valuable testbed for developing the optimization technologies of tomorrow.

References: 
[1] J. A. Tirado-Domínguez et al., “QTIS: A QAOA-based quantum time interval scheduler,” Future Gener. Comput. Syst., 2026.
[2] E. Farhi et al., “A quantum approximate optimization algorithm, » 2014. 
[3] S. Hadfield et al., “From the quantum approximate optimization algorithm to a quantum alternating operator ansatz,” Algorithms, 12(2), 34, 2019.

Please contact: 
José Antonio Tirado Domínguez
University of Malaga, Spain
This email address is being protected from spambots. You need JavaScript enabled to view it.