The Quantum Wrench Initiative

Every problem has a solution. Sometimes, many problems have many solutions and 1 key, especially when the underlying mathematical formulation is the same, but variables and conditions differ. Wouldn't it be interesting to have a tool, a wrench, that opens many doors?

In information theory, NP hard problems are those problems that typically involve searching through an exponentially large number of possibilities, like scheduling, routing, or optimization tasks, i.e. are difficult to solve. These problems become difficult to handle when constraints, uncertainty, and last-minute changes are involved. Combinatorial optimization problems are part of this family of problems, with a main objective to minimize and constraints that must be respected.

Classical tools like Gurobi are great in solving many optimization problems, but they struggle when the problems become highly complex, with several overlapping constraints. In addition to that, these tools give 1 optimal solution only. And what happens when that solution fails due to unexpected circumstances?

In practice, the challenge is not only finding one optimal solution, but having several high-quality alternatives when conditions change — for example when a nurse calls in sick or demand shifts unexpectedly. As an alternative, we propose Quantum Markov Chain Monte Carlo. It is a sampler that finds the solutions that minimize a combinatorial optimization problem by proposing new potential solutions, and accepting those with low energy, sampling from a so-called Boltzmann distribution, i.e. sampling solutions based on how good they are. Basically, solutions that are better for a given optimization problem have lower energy and higher probability to be sampled. After many iteration steps, the algorithm will not be limited to only 1 solution but will generate several good solutions (it's a sampler!). The quantum version of MCMC explores the solution space differently from standard methods, with the goal of efficiently identifying multiple high-quality solutions. It exploits quantum tunneling and quantum superposition to find solutions with lower energy (that optimize the problem better).

This ability to generate multiple viable solutions is particularly valuable in real-world environments where plans frequently need to adapt.

Our Q-MCMC helps us reach solutions where classical tools like Gurobi get stuck (we call them local minima) due to those constraints that we mentioned earlier creating a rugged energy landscape. Compared to classical MCMC, our Q-MCMC mixes faster, due to better choice of parameters. This means, it converges faster to the theoretical distribution of states/solutions.

Solving logistics problem with Q-MCMC

As an example, let's consider logistics / supply chains problems. Suppose you have thousands of customers in America that you want to serve, but limited budget to open only P warehouses from which you deliver goods to these customers. If you open more than P warehouses, you shorten the distances to your customers, but you break your budget constraint. There is a heavy penalty for such proposed solution. It is important to respect the number of warehouses you can open, and choose the locations of these P warehouses wisely, such that you minimize the distances between them and your customers, and even better, they should be closer to customers with more demands. I.e. minimize the demand*distance product over all customer-warehouse combinations. Sometimes demands can peak, especially on holidays. In December you consider opening one extra warehouse, which comes with opening costs, of course, but you will still open it, because it is beneficial to you. Thus, you have time windows now, where demand changes (more demand in December compared to November). But where to put this new warehouse? Suppose you run your solver and it tells you Chicago is the best city where to build your initial warehouse in November (as a young business you can only afford 1). For peace of mind, it would be nice if the solver gave you a solution for December too (one extra warehouse, 2 warehouses in total for December). You run the Q-MCMC nd it gives you Chicago + Los Angeles.

These solutions were generated using our Q-MCMC algorithm. Green sphere: chosen warehouse. Blue: customers.

Take another example, with different settings. Demand is normal. P=1. The solver tells you that you must open the warehouse in Boston for your customer in NYC. However, there is a sudden storm and the warehouse must close. If you had used a standard solver, you'd be left without a backup solution. However, with Q-MCMC you don't need to worry. When you execute Q-MCMC it gives you the most optimal solution with highest probability, and the second (third, fourth, etc) solutions with lower probability (but still sufficiently high) as your alternative solutions in case of emergencies and dynamic situations.

First solution (Boston, for your customer in NYC):

Second best solution, Chicago:

In real life, there are many warehouses, many customers and various dynamic situations.

A more complex logistics case

In this case we consider 5 warehouses and 5 customers. For month 1 we can open no more than 2 warehouses; for month 2 no more than 3 warehouses. We also have a table of transportation costs from warehouse w (i) to customer c (j).

We define volumes of how much goods we can transport from warehouse w to customer c on a single trip. A warehouse cannot transport more than the given value towards a given customer, which is another constraint.

Running our Q-MCMC, it gave us several good solutions in one execution. We ranked the top 10 in terms of energy: lower energy, better solution.

The top best solution (rank 1), is decoded and projected into this map, where customers are in blue, open warehouses in green and unused warehouses in orange:

In the left: no more than 2 warehouses allowed, in the right: no more than 3. You find the result in the right surprising, as to why is customer 4 served by warehouse 3, and not by warehouse 2 which is closer. The reason is that the transportation cost from warehouse 2 to customer 4 is 4x larger than from warehouse 3 to customer 4 (check the previous picture).

Here we show the second-best solution (rank 2), which we can use in case for some reason, due to unexpected events, solution 1 doesn't work:

We can do the decoding and mapping for as many solutions as we are interested in.

Nurse Scheduling

Nurse scheduling or nurse rostering is also an NP hard, combinatorial optimization problem. What makes it particularly nasty, is the overlap of several constraints, some of which are hard conditions (e.g. a nurse must not work more than a permitted number of hours, or it is prohibited to work two sequential shifts). It helps to take their preferences into account (another constrain), holidays must be respected, skill levels need to be appropriate for a given shift, etc. Sometimes nurses do last minute cancellations and nurse schedulers must fill their shift quickly. A solution that respects all or most constraints, will have low energy and will be chosen with higher probability by our Q-MCMC sampler. The advantage of Q-MCMC is that it gives you several good solutions, exactly to handle the last-minute cancellations, or other dynamic situations without having to re-run everything from the start or calling a nurse who is already overworked (nurse burnout, plus more expenses for the hospital)!

As an analogy to our logistics example, think of nurses as variables that need to be combined with shifts and days, where days are analogous to the monthly time windows in the supply chain problem. If a ward has e.g. 100 nurses, we don't operate with 100 nurses every day. The key is to predict (via ML/AI) how many nurses are expected to come to work a certain day. This also determines the number of variables used and qubit bits.

Other technical advantages of our Q-MCMC algorithm:

• The result is not damaged by the noise in quantum computers. Our approach is designed to remain effective even in the presence of noise in current quantum hardware.

• The number of qubits is kept under control, because some constraints are solved quantumly, some classically. The reason for this choice is to use an encoding that saves enough qubits (quantum bits) but also uses enough quantum that it provides advantages to classical solvers.

• We are using intelligent mixing parameters that makes the algorithm faster than classical MCMC.