Quantum Inspired Optimization

Microsoft introduced a public preview of Azure Quantum! This is awesome, it gives the power of actual working Quantum computers to everyone via the cloud. Besides a working Quantum computer there is one more service available called Azure Quantum Inspired Optimization, which I will expand a bit further here.

What is Quantum Inspired Optimization?

In short: Quantum Inspired Optimization (QIO) takes learnings that we have from quantum mechanics and applies it to solve optimization problems on classical hardware. This might sound very vague, if you want to have a better understanding I would recommend this free Microsoft Learn resource.

Let's first look what I mean with optimization. Let's take the traveling salesman problem as example. Let's imagine that you are a door to door salesman and you have x amount of possible addresses that you can visit. You want to find the shortest route to visit all the addresses. The amount of possible routes exponentially grows with the growing number of places to visit, this will get so large that it will be near impossible to calculate all routes and find the optimal route. This problem to find the best route, is what we call an optimization problem, and that is what we will try to tackle here.

Another example is a shipping problem, which is in detail described and solved with QIO here. The problem is as follows: if we have X amount of shipping containers and we have two different ships. Which container should be placed on which ship to have almost the same weight on both ships? Having an equal amount of weight on each ship will minimize fuel consumption. Let's see how this would be solved on Quantum Inspired Optimization (QIO).

The goal with QIO is to define a cost function, with some variables and let the QIO solver minimize the total cost. So we need to think of a cost function and variables. Let's get started with a cost function.

This would look like this:

\[ total \space cost = (Weight \space containers \space ship \space 1) -  (Weight \space containers \space ship \space 2) \]

If the total cost is \(0\) this means that each ship has the same weight and therefore we have an optimal solution. How can this be achieved? For this we will use some variables. In these QIO problems the variables can take two values; either -1 or 1. There are other ways of writing QIO, which use 0 or 1 as variable values, but let's skip that for now.

So we will give each container a variable with the value \(-1\) if it is on ship 1, or value \(1\) if it is on ship 2. Finding which value each variable has will be the job of the QIO solver. Let's say we have 4 containers with these weights: 10, 8, 4, 2, and we want to create a cost function we would get the following:

\[ total \space cost  = 10 \cdot x_0 + 8 \cdot x_1 + 4 \cdot x_2 + 2 \cdot x_3 \]

Each variable \(x_n\) can take the value -1 or 1 as said before. This is just a simple example but the outcome could be \(x_0\) and \(x_3\) =1 and  \(x_1\) and \(x_2\) =-1. This would mean that the weight on each ship is 12, which would be an optimal solution.

Finding which variable takes which value is the task of the solver, in traditional algorithms this can take a long time with a large number of variables. With the new Azure Quantum solution, Quantum inspired solvers are offered. These solvers can solve problems in fractions of time compared to classical solvers.
If you want to know how you can use Azure Quantum to solve this problem take a look here.

This Azure Quantum service means completely new possibilities are becoming available in areas like logistics, finance and healthcare.

Take a look at the next post which goes in depth on how to solve the traveling salesman problem here.