Solving a Constrained Project Scheduling Problem with Quantum Annealing
I'm really excited to share this article with you because it's closely tied to my current research: optimizing project schedules with quantum computing. My passion for this topic comes from my background as a project manager and my ongoing research into how quantum computing can help solving complex optimization problems. During my PhD, I specifically looked into how today's quantum technology could be used to tackle complex scheduling challenges, that are specific for the field of Project Management.
We're living in an incredible era where quantum computers are no longer just a concept – they're real and being used. Imagine what Richard Feynman would say about them! However, these machines aren't fully ready yet. They're often referred to as NISQ (Noisy Intermediate-Scale Quantum) devices, a term coined by quantum computing pioneer John Preskill. These machines are still considered early versions of the more advanced quantum computers we hope to see in the future.
Currently, they're small, with only a few qubits (quantum bits of information) available. For comparison, it's not uncommon today to have a laptop with 16GB of RAM, which equates to around 128 billion bits of information, that we can work with. In contrast, the largest quantum computers have fewer than 6,000 qubits. Moreover, qubits are highly sensitive to noise, and the limited number of qubits makes it challenging to correct errors and perform complex calculations.
Despite these challenges, the quantum computers we have today are powerful enough to test out algorithms and see their potential for solving tough problems. In broad terms there are two main types of quantum computers: universal quantum machines, like the ones from IBM and Google, which work on a circuit-gate model of computation, and quantum annealers, which use adiabatic evolution principles (Technically speaking there is a third type of quantum computer, which are measurement based quantum machines, but these ones are still in early development). In Quantum Computing, "universal" means that these machines can, in theory, run any quantum algorithm by implementing any quantum mechanical gate (including classical gates). While quantum annealers might not be universal, they're still super promising for optimization tasks.
In this article, I'll walk you through how you can use a quantum annealer provided by a company called D-Wave to optimize project schedules, this article is based on one of my recently published research papers [1]. If you're interested in a deeper dive, I invite you to read my full research article, which you can access using the link down below.
Solving the resource constrained project scheduling problem with quantum annealing – Scientific…
Before we get into the coding, I'll give you a quick intro to quantum annealing and how it's used in optimization. Let's get started!
Article index:
- What is quantum annealing?
- The RCPSP and it's binary MILP formulation
- Installing the libraries and setting up the Colab environment
- D-wave CQM for the RCPSP
- Solving the instance and extracting the output
- Conclusions
- References
What is quantum annealing?
Quantum Annealing is a quantum metaheuristic designed to solve combinatorial optimization problems by leveraging the principles of quantum mechanics [2]. This approach is inspired by simulated annealing [4], a classical metaheuristic where a system is gradually cooled to reach a state of minimum energy. In quantum annealing, quantum phenomena such as superposition (where a quantum system can exist in multiple states simultaneously until measured, at which point it collapses into one of the possible states) and quantum tunneling are utilized to efficiently navigate through local minima, with the goal of finding the global minimum of a cost function.
Quantum annealing devices are primarily employed for optimization purposes, such as finding the minimum or maximum value of a problem. Imagine trying to find the lowest point in a rugged, hilly landscape aka the "best" solution to a problem. Traditional methods might get stuck in small dips, mistaking them for the lowest point. In contrast, a quantum annealer leverages the properties of quantum mechanics, attempting to tunnel through these local minima and guide the system to the true lowest point, or optimal solution. The effectiveness of quantum annealing, compared to its classical counterpart, can vary depending on the specific problem and the hardware used. The literature presents both theoretical proofs [3] that highlight the advantages of quantum annealing, as well as contrasting perspectives, particularly when compared to simulated annealing
At the core of quantum annealing is the profound concept that the universe naturally tends to seek states of minimum energy, known as ground states. Quantum annealing also relies on the "adiabatic theorem" of quantum mechanics and the evolution of quantum systems as described by the time-dependent Schrödinger equation.
Optimization problems can be represented as physical systems and formulated as energy Hamiltonian problems, which are mathematical representations of a system's total energy. A common approach is to use the ISING model to encode the optimization problem into a physical system. In this model, the optimization problem is mapped onto a representation of the magnetic spin of each qubit, interacting in a two-dimensional lattice grid, as shown in Figure 1 below.
The mathematical representation of the energy Hamiltonian H₁ in the ISING model is given by the formula below:
Here, σᵢ is the Z-Pauli gate applied to qubit i, which takes the value +1 if the qubit is pointing upwards and -1 if it is oriented downwards. Jᵢ ⱼ represents the interaction coefficient between qubits i and j, while Hᵢ represents the coefficient of an external magnetic field interacting with qubit i. Fortunately, most common optimization problems can be encoded using this model, as the ISING problem is NP-Complete, as demonstrated by Istrail in 2000 [5]. In this model, each variable is binary, acting like a magnet that can only point up or down. These magnets will naturally try to orient themselves to minimize the energy of the entire grid, resulting in the system's minimum energy. The solution to the problem is simply the configuration of the magnets after they have evolved and properly aligned themselves.
You've likely already encountered some of the principles of this model without even realizing it. If you've ever played with magnets, you know that when you have two or more, they naturally try to align their poles in opposite directions to minimize the total energy of the system, as illustrated in Figure 2.
Mother Nature is a giant optimizer, that tries to solve this problem on her own. As illustrated in Figure 3 if we start with a random assortment of spin particles, each oriented in a different direction, they will naturally attempt to realign themselves, seeking the minimum energy state. Quantum annealing leverages this principle. However, this process doesn't always guarantee finding the absolute global minimum, as nature can still get stuck in local minima. That's why we also rely on the power of the adiabatic theorem.
The adiabatic theorem, first formally stated by Max Born in 1928 (although Einstein had also explored the concept earlier), tells us that:
If a system starts in its lowest energy state and changes "slowly enough", it will remain in that minimum energy state as it evolves.
This theorem and its impact on quantum annealing can be challenging to grasp, so I'm going to use a metaphor that has worked well for me in the past. Keep in mind that, like all metaphors, it may not be entirely accurate from a formal physics perspective (it is not), but it serves as a helpful way to illustrate the concept.
Imagine we have a toddler who, in this example, represents a quantum system. Let's get creative, like Elon Musk, and call this child Psi Ψ. Now, Psi Ψ can interact with various environments within the house where they live. These environments represent what we'll call energy Hamiltonians. For instance, one Hamiltonian could be the living room of the house, with a comfy couch in front of the TV, as shown in Figure 4.
Another Hamiltonian could be for example the bedroom of Psi Ψ, as depicted in Figure 5.
Now, Psi Ψ can exist in various energetic states. For example, Psi Ψ could be in an excited state, let's say they're in the middle of a sugar rush, as shown in Figure 6.
Psi Ψ can also be in a ground state, a state of minimum energy. For example Psi Ψ might be in deep sleep as shown in Figure 7.
Now, there are certain Hamiltonians, which we'll call H₀, where Psi Ψ will naturally evolve toward a minimum energy ground state. For instance, if we let Psi Ψ play in the living room, even if they start in an excited state, they'll eventually tire out and fall asleep on that comfy sofa, as shown in Figure 8. (I remember a childhood friend's house with a terrace overlooking a beautiful valley, where you could feel the fresh mountain breeze. The terrace had a sofa and was filled with chimes that sang with the wind. It was one of the most relaxing environments I've ever experienced, and I'm sure anyone would naturally settle into a ground state in that kind of "Hamiltonian".)
In contrast, there are other Hamiltonians – typically the ones we're most interested in – called H₁, where it's much more difficult for Psi Ψ to reach the ground state. For example, Psi Ψ really struggles to fall asleep when they are in their bedroom, as shown in Figure 9.
Unfortunately, what we really want is for Psi Ψ to be in the ground state of H₁ – in other words, we want Psi Ψ to be fully asleep in their bedroom . But that's tough to achieve, so what do we do?
Quantum annealing advises us not to fight against the current. Instead of directly seeking the ground state of H₁, it suggests leveraging the power of the adiabatic theorem. Quantum annealing says, "Look, the starting point of this process should be an easy Hamiltonian, H₀". We first allow Psi Ψ to naturally evolve into a ground state because it's easy to achieve this in H₀. So, we let Psi Ψ play in the living room, and once they are fully asleep on that comfy sofa, then – and only then – do we very gently, very softly, without disturbing their sweet dreams, begin to slowly change the Hamiltonian from H₀ to H₁. We gently pick them up from the sofa, slowly climb the stairs, and softly place them in their bed. If we do this process correctly and "slowly enough" (adiabatically), by the end of it, we should find Psi Ψ in the ground state – not of H₀, but of H₁, as shown in Figure 10. And voila
