Quantum annealing: a game-changer for complex project management?
11/21/2024
3 min
Share
In a world where project management increasingly involves juggling complex schedules and tight resource constraints, finding more efficient solutions is critical. New research looks at the potential of quantum annealing, a quantum computing approach, to optimize scheduling challenges for complex project management. In this video, one of the authors, Luis PEREZ ARMAS explores how this emerging technology can potentially help deal with problems that may be too complicated for classical computing methods.
Quantum annealing and project scheduling
Project scheduling can become particularly complex when the resources available are limited, a challenge known as the resource-constrained project scheduling problem (RCPSP). This can be the case for projects across a variety of sectors such as software development, event planning, pharmaceutical R&D, construction or infrastructure.
While quantum computers have existed for some time, there have been challenges in terms of making them more widely usable. Traditional approaches often rely on a technique called mixed integer linear programming (MILP), but this can be expensive and slow when scaling up.
This is where the researchers from IESEG, KU Leuven and the Université de Louvain, Junia/Centrale Lille believed quantum annealing could potentially excel. Unlike classical gate-based quantum computers, quantum annealers are optimized for finding the lowest energy states in complex problems, making them particularly well-suited for complex tasks.
Luis PEREZ ARMAS, one of the researchers on the project, explains: “To test this, we generated multiple project instances and evaluated more than 12 different ways to formulate the project using mixed integer linear programming (MILP) formulations to find out which one adapts better to the quantum annealer. “
“Once we identified the best formulation, we mapped over 30 project schedule instances of different sizes and complexity onto quantum devices and performed thousands of quantum evolutions. We fine-tuned parameters like the annealing time, scheduling, number of pauses, and even tested an advanced technique known as reverse quantum annealing, which is the equivalent of a ‘warm start’ but in the quantum realm.”
Pauses improve the process
The researchers found that simpler formulations from the past, which had long been discarded, are actually the most suitable for the current quantum annealing devices. Moreover, they discovered that the inclusion of pauses consistently improves the performance of the annealing process, while longer annealing times beyond 20 microseconds tend to deteriorate the quality of the solutions.
The most significant challenge identified was ‘problem embedding’ which refers to mapping the problem onto the quantum chip. This was mostly due to the lack of sufficient qubit connectivity. Qubits are the basic unit of quantum information -and the way these pieces of information are connected – are a crucial aspect of quantum computing.
Outperforming classical computing techniques
Overall, for the resource constrained scheduling problems and with short evolution times (less than 5 seconds), they found that quantum annealing outperforms classical optimization techniques, making it an ideal candidate for online scheduling processes (real time optimization with shorter times to produce a solution).
Additionally, more complex variations of the scheduling problems, which involve more intricate objective functions or constraints, naturally align with the capabilities of a quantum annealer. Finally, the researchers suggest that the results from the quantum annealer can be integrated into classical computing techniques, thereby combining the strengths of both approaches. These last topics are part of the team’s ongoing research.
Practical applications and future directions
The researchers believe, therefore, that annealing holds significant promise for project scheduling, particularly in scenarios where time constraints are critical. For example, when time delays come into play or project budgets need to be revisited rapidly.
However, they also found that annealing still faces some challenges, including improving problem embedding and qubit connectivity.
Despite these challenges, the researchers believe that further refinements, such as adapting the way the technology is scheduled, could unlock even greater potential.
The study also suggests several avenues for future exploration, such as applying quantum annealing to larger project scheduling instances or combining it with other quantum computing techniques like Quantum Approximate Optimization Algorithms (QAOA). Additionally, alternative quantum technologies like neutral atom systems could also enhance the performance of quantum project management tools.
Find out more in this paper published in the journal Scientific Reports (Nature Publishing) Solving the resource constrained project scheduling problem with quantum annealing | Scientific Reports (nature.com)
Accompanying homepage image: Istock – credit bpawesome
Contributors
Luis Fernando PÉREZ ARMAS
Operations Management, Operations Research, Project Management
Full biography