A new algorithm breaks down project scheduling into 30-qubit daily batches

Raul Martinez, Miguel Sánchez-Beato, Matilde Osa, Jorge Parra and Mario Calonge of the Quantum Technologies Department at ITECAM have simulated a variational quantum algorithm designed to tackle realistic, complex project scheduling. Their work addresses the multi-skill resource-constrained project scheduling problem, a notoriously difficult task where efficient distribution of work impacts not only productivity but also employee well-being.

To accommodate the limitations of near-term quantum hardware, the researchers decomposed the scheduling problem into daily 30-qubit batches, and found that an entanglement-free approach produced feasible schedules at a fraction of the computational cost of entangled topologies. The results indicate that, for the instance studied, entanglement did not improve the solutions found by the algorithm.

Variational Quantum Algorithm for Multi-Skill Project Scheduling

The algorithm manages complexity by dividing multi-skill project scheduling into temporal batches, each solved independently for a single day before propagating remaining workload to the next period. This decomposition technique allows the researchers to address a realistic Multi-Skill Resource-Constrained Project Scheduling Problem (MS-RCPSP) while keeping the computational demands within the limits of near-term quantum hardware. Each daily batch is further constrained to a maximum size of 30 qubits, a deliberate choice to accommodate current technology and facilitate simulation.

The work challenges the assumption that entanglement always improves quantum algorithm performance by comparing different ansatz topologies. Specifically, the team tested a configuration without entangling layers against those employing linear and brick-wall entanglement schemes, all with an equivalent number of parameters. Using the COBYLA optimizer, the entanglement-free ansatz generated feasible schedules closest to the required workload, and it did so at a reduced simulation cost compared to the entangled alternatives.

This finding stems from simulating a Variational Quantum Algorithm (VQA) designed to account for realistic project constraints, including worker skill sets, task priorities and deadlines. The simulation incorporated calendar stability during rescheduling, a feature often absent in simplified models. The researchers formulated the MS-RCPSP as a Quadratic Unconstrained Binary Optimization (QUBO) problem, a standard approach for adapting optimization tasks to quantum algorithms.

They also explored training the ansatz with both COBYLA and Adam optimizers, using SPSA gradient estimation to improve efficiency. The study’s results suggest that, for the instance examined, the ground state of the QUBO Hamiltonian can be represented without entanglement, potentially simplifying circuit design and reducing resource requirements.

MS-RCPSP Formulation: Worker Skills and Daily Capacities

The algorithm addresses realistic project constraints by explicitly modeling worker daily capacities, individual skills, task priorities and deadlines, alongside a calendar-stability feature that minimizes disruption when rescheduling is needed. This detailed formulation goes beyond simplified models often used in quantum algorithm development, acknowledging the practicalities of workforce management and the impact of changes on ongoing projects. The inclusion of calendar stability, for example, penalizes deviations from previously established schedules, reflecting the real-world costs associated with frequent adjustments.

To manage the complexity of the multi-skill resource-constrained project scheduling problem, the researchers employed a temporal batch decomposition technique, solving the schedule one day at a time. This approach breaks down a larger, intractable problem into smaller, more manageable segments, allowing the quantum algorithm to focus on optimizing the immediate timeframe before propagating the remaining workload to subsequent days.

This strategy, combined with a logarithmic binary encoding, ensures that each batch of calculations remains within the limits of current quantum hardware, specifically maintaining a qubit count at or below 30 variables. The logarithmic binary encoding method allows for a clear representation of the number of working hours assigned to each worker, task and day combination.

This encoding method allows for a compact representation of the problem, reducing the number of qubits required to model the schedule. This work has presented a complete variational quantum algorithm pipeline for the MS-RCPSP, incorporating a QUBO formulation, a logarithmic binary encoding, and the temporal batch decomposition strategy.

Temporal Batch Decomposition Limits Problem to 30 Qubits

The algorithm manages computational complexity by limiting each daily scheduling batch to 30 qubits, a deliberate constraint designed for implementation on existing quantum processors. To keep the problem within a near-term circuit size, a temporal batch decomposition solves one day at a time, propagates the remaining workload, and combines it with a logarithmic binary encoding. A calendar-stability term was also incorporated, penalizing deviations from previously established schedules during rescheduling, a feature intended to minimize disruption and maintain a consistent workflow.

Ansatz Architectures: Linear, Brick-Wall, and Entanglement-Free

Researchers tested three ansatz architectures, linear, brick-wall and an entanglement-free reference, all sharing the same number of trainable parameters to isolate the impact of entanglement on performance. This approach allowed for a focused comparison of how different circuit topologies affect the optimization process for a multi-skill resource-constrained project scheduling problem.

The entanglement-free ansatz served as a baseline, removing the entangling stage entirely to determine if entanglement provides a demonstrable benefit in this context. Both linear and brick-wall topologies were constructed with three repetitions, ensuring each ansatz family possessed an equivalent parameter count, and then trained using both COBYLA and Adam optimizers with SPSA gradient estimation.

The brick-wall topology arranges two-qubit gates in alternating layers, while the linear topology entangles each qubit with its immediate successor, creating distinct pathways for quantum information to flow. For the instance and initialization studied, the entanglement-free reference produced feasible schedules under both optimizers. With COBYLA, it produced the feasible schedule closest to the required workload at a fraction of the simulation cost of the entangled topologies, indicating that entanglement did not improve the solutions found by the VQA.

COBYLA and Adam Optimizers with SPSA Gradient Estimation

The choice of optimization algorithm significantly impacted runtime during simulations of a quantum approach to project scheduling. Each ansatz-optimizer pairing began with the same randomly generated initial parameters, ensuring a fair comparison of training dynamics. The researchers tracked performance across different batch sizes, generating curves that illustrate the optimization process for each configuration.

This setup allowed for a focused evaluation of how each optimizer and ansatz combination performed in finding optimal or near-optimal solutions to the scheduling problem. The results contribute to a growing understanding of how to effectively use variational quantum algorithms for complex optimization tasks, even with the limitations of current quantum technology.

Entanglement’s Impact on VQA Training for Job Scheduling

This involved comparing ansatz architectures with and without entanglement to determine if entanglement aids in the optimization process, despite not being strictly necessary to represent a solution. The team focused on a hardware-efficient ansatz, testing both linear and brick-wall entangling topologies alongside an entanglement-free reference design, all while maintaining a consistent number of trainable parameters. The simulations used a matrix product state (MPS) simulator to evaluate the expectation value of the Ising Hamiltonian, a key step in the VQA training loop.

Each configuration, a specific combination of ansatz architecture and optimization algorithm, was trained on the same QUBO instance, a 30-qubit problem representing a single day’s workload within the larger project. The choice of 30 qubits reflects a practical constraint imposed by the limitations of near-term quantum hardware, necessitating the temporal batch decomposition strategy used to manage problem complexity.

Simulation on Bull Qaptiva 802 with myQLM Software

Simulations of a variational quantum algorithm for job scheduling ran on a Bull Qaptiva 802 appliance, using the myQLM software stack for matrix product state (MPS) simulation, a method that remains exact as long as the bond dimension is not truncated. Each CNOT gate within the ansatz could at most double the bond dimension, influencing the computational cost of the simulation, and highlighting a key constraint in scaling these algorithms to larger problems.

The team ran all six ansatz-optimizer configurations, linear, brick-wall and entanglement-free, each with COBYLA and Adam using SPSA gradient estimation, on the same multi-skill resource-constrained project scheduling problem instance. The simulations employed a consistent setup across all configurations, including a QUBO formulation, identical Lagrange multipliers and a batch decomposition with a one-day window and three ansatz repetitions. With COBYLA, it produced the feasible schedule closest to the required workload at a fraction of the simulation cost of the entangled topologies, indicating that entanglement did not improve the solutions found by the VQA.

Feasible Schedules Achieved with Entanglement-Free Ansatz and COBYLA

The entanglement-free ansatz consistently produced feasible schedules regardless of the optimization algorithm used, a result suggesting that incorporating entanglement does not necessarily improve performance in this multi-skill resource-constrained project scheduling problem. This efficiency stems from the fact that the ground state of the Ising Hamiltonian, central to the quantum algorithm, can be represented exactly by a product state, which an entanglement-free ansatz readily provides. However, the researchers note that this theoretical consistency does not fully explain why the product state also proved easier to train.

The team observed that COBYLA typically reached its tolerance threshold before the maximum iteration limit, while Adam+SPSA often exhausted the allotted iterations, contributing to the faster solution times with the entanglement-free ansatz. This difference in computational efficiency was not solely due to cost per iteration, but rather the number of iterations required to converge. The study prioritized capacity feasibility over strict deadline adherence, highlighting a realistic constraint in project management. The entanglement-free reference was the only ansatz family that maintained feasibility across both optimizers, demonstrating robustness in its performance.

More like this

Quantum Research NewsResearchers show how to certify entangled qubits without full device control

Quantum Research NewsPost-selection games formalise a paradox of quantum possibility

Quantum AlgorithmsGenome in a Bottle data will test quantum optimisation for regulatory genomics

Quantum AlgorithmsMultiplying integers now speeds up quantum Fourier transforms