Solving Optimization Problems in Azure Quantum Using Quantum-Inspired Algorithms

This story is part of the Q# Holiday Calendar 2022. Check it out for other interesting posts!

The aim of this blog is to show you one of my projects that I have worked on over the past few months, and to depict one of the many riveting capabilities of Azure Quantum.

I am a Computer Science master’s student at the Technical University of Munich, specialising in Quantum Computing. I am interning as a Cloud Solution Architect — Engineering for Cyber Security at Microsoft, and simultaneously, I am taking part in Azure Quantum related projects.

In November 2022, my Microsoft colleagues, Elisabeth Weigel and Holger Sirtl, and I conducted a workshop on the topic of “Quantum Computing and Quantum Inspired Optimization with Azure Quantum” at the Deggendorf Institute of Technology for students of the High-Performance Computing M.Sc. programme. In this blog, I will give a short overview of our Quantum Inspired Optimization (QIO) project that we have implemented.

Quantum Inspired Optimization

Optimization problems are found in every industry, such as manufacturing, finance, transportation, and logistics. The goal of optimization algorithms (optimizers) is to solve these problem by finding a solution that satisfies the criteria of the cost function. ​Given a function, its landscape can come in many different shapes and forms; however, in our case, we will take a look at two distinct examples. In a single and smooth landscape there is only one minimum point. Locating this exact spot can be easily done with the help of some of the well-known optimizers: Stochastic Gradient Descent, Adam, or if one has access to high computational power, then one could utilise higher-order optimization methods such as K-FAC or Adahessian. However, if the landscape of the function is rugged, another problem arises. Multiple minima points can be found in the landscape here. In order to escape a local and locate the global minimum point, we need a different type of solution, one approach is quantum tunneling.

Figure 1. Single, smooth landscape (left); Structured, rugged landscape (right)

Entering the quantum age, scientists have started emulating quantum effects on classical computers, which has paved the way for the development of a new group of methods called “Quantum Inspired Algorithms”. These algorithms borrow ideas from quantum mechanics. One such example is Simulated Annealing with quantum tunneling, also known as Quantum annealing. Simulated Annealing is an algorithm, where the walker in the landscape always moves downhill, however, there is a non-zero probability that it makes an uphill move (also known as a “thermal jump”) to overcome the barrier, which then can lead to a better minimum point. Quantum tunneling is a phenomenon where a walker can travel through these barriers.

Figure 2. Depicting the various terms of a cost function

QIO with Azure Quantum

When solving optimization problems in Azure Quantum, one can easily use the already enabled Microsoft QIO provider, which offers various quantum inspired approaches. Some examples include: the previously mentioned Simulated Annealing method; Parallel Tempering — which can simulate both classical and quantum annealing; Population Annealing — quite similar to Simulated Annealing although it simulates a population of walkers.

Let’s define one simple example! Let C = -9x -3y +5z be our cost function, where the three variables x, y, and z only take values -1 and +1. By running our Paraller Tempering solver, we obtain x = 1, y = 1, and z = -1. This solution set delivers us minimal value for our cost function.

from azure.quantum import Workspace​

from azure.quantum.optimization import Problem, ProblemType, Term​

from azure.quantum.optimization import ParallelTempering​

​

workspace = Workspace ( ... )​

​
problem = Problem(name="My Simple Problem", problem_type=ProblemType.ising)​

terms = [ ​

    Term(c=-9, indices=[0]),​

    Term(c=-3, indices=[1,0]),​

    Term(c=5, indices=[2,0])​

]​

​
problem.add_terms(terms=terms)​

​
solver = ParallelTempering(workspace, timeout=100)​

​
result = solver.optimize(problem)​

print(result)​

​

.....{'version': '1.0', 'configuration': {'0': 1, '1': 1, '2': -1}.....

Cost functions where the interaction between variables is evaluated with -1 or +1 values (as in our previous example), are also known as Ising models. Another variation of this is the Quadratic Unconstrained Binary Optimization, for which the values take only 0 or 1 values. Both models are supported by Microsoft QIO, and they are frequently used to solve well-known NP problems such as graph coloring, set partitioning, set cover, and so on.

In our project, we tried solving the Graph Coloring problem. The goal is to color all the nodes in the graph, such that each pair of connecting nodes has a different color from one another, and for the number of different colors to be minimal. We try to solve this, in order to complete an exam scheduling task, i.e., we represent each school subject as a node, and the connecting edge between two nodes says that there is at least one student taking both of these exams. This means that these two exams need to take place at different timeslots, so that the student can take both exams. Which leads to the fact, that these two nodes (subjects) need to be coloured with different colors. We also want to have the minimum number of timeslots (colors), so that the school uses less time for the exam period, which makes this an optimization problem. The hardest hurdle to overcome when dealing with problems like these is trying to find a suitable cost function.

Ising formulation for the Coloring Problem

As seen in the function H, we need to construct two summands. The first term represents the fact that each node must receive exactly one colour, and the second element depicts the statement that two neighbouring nodes must not receive the same color. The next steps include tranlating the formula into python code, and the rest of the problem is solved by using the Parallel Tempering solver, as seen in the previous example.

Final remarks

First and foremost, I would like to thank Mariia Mykhailova from the Microsoft Q# team for organising the Q# Holiday Calendar!

If you, the reader, would like to connect and exchange interesting Quantum related topics and ideas, feel free to reach out on Petar Petrov | LinkedIn.