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

Introduction

A team from ITECAM’s Quantum Technologies Department has demonstrated a practical variational quantum algorithm (VQA) for the multi‑skill resource‑constrained project scheduling problem (MS‑RCPSP). By breaking the schedule into daily batches limited to 30 qubits, the researchers kept the workload within the reach of near‑term quantum hardware. Surprisingly, an entanglement‑free ansatz outperformed more complex entangled circuits, delivering feasible schedules at a fraction of the computational cost.

Temporal‑Batch Decomposition to 30 Qubits

The core innovation is a temporal‑batch decomposition: the full project horizon is sliced into one‑day sub‑problems, each encoded with at most 30 qubits. This limit matches current quantum processors and allows exact simulation using matrix‑product‑state methods. A logarithmic binary encoding captures the number of work‑hours assigned to each worker‑task‑day combination, dramatically reducing the qubit count while preserving the richness of the constraints (skill sets, task priorities, deadlines, and a calendar‑stability penalty that discourages disruptive rescheduling).

Ansatz Architectures and the Role of Entanglement

Three hardware‑efficient ansätze were compared:

1. Linear entangling – qubits linked sequentially.
2. Brick‑wall entangling – alternating two‑qubit gates.
3. Entanglement‑free – only single‑qubit rotations.

All shared the same number of trainable parameters, isolating the effect of entanglement. Training employed both the gradient‑free COBYLA optimizer and the gradient‑based Adam optimizer with SPSA gradient estimation. Across all configurations, the entanglement‑free ansatz consistently produced feasible daily schedules, and with COBYLA it achieved the closest match to required workloads while using far fewer simulation resources. The results suggest that, for this instance, the ground state of the QUBO Hamiltonian can be represented as a product state, making entanglement unnecessary.

Practical Implications for Near‑Term Quantum Computing

The study offers several takeaways for practitioners:

• Hardware alignment: By capping each batch at 30 qubits, the algorithm fits comfortably on existing superconducting or trapped‑ion devices, avoiding the steep overhead of deep entangling layers.
• Optimization strategy: COBYLA proved more efficient than Adam+SPSA for this problem, converging quickly to a feasible solution. Choosing an optimizer that respects the limited parameter landscape can be as important as circuit design.
• Model realism: Incorporating worker capacities, skill matrices, and calendar‑stability penalties yields schedules that reflect real‑world project management concerns, moving quantum optimization beyond toy examples.
• Entanglement caution: While entanglement is a hallmark of quantum advantage, this work reminds us that more entangling gates do not automatically translate to better performance, especially when the problem’s optimal solution lies in a low‑entanglement subspace.

Closing Thoughts

Dividing a complex scheduling problem into 30‑qubit daily slices and employing an entanglement‑free VQA demonstrates a viable pathway for quantum‑enhanced project management on near‑term hardware. The approach balances algorithmic sophistication with practical hardware limits, delivering feasible schedules without the overhead of deep entanglement. As quantum processors scale, the same batch‑decomposition framework could be extended to larger horizons, potentially unlocking genuine quantum speed‑ups for large‑scale operational planning.