Qiskit-Optimization module Internals-Part 1

I spent some time in the last few days diving deeper into some parts of Qiskit Optimization module’s source codes. In this blog, I will be documenting my experience and what I learnt in the process. Going through Qiskit’s source codes has been in my to-do list for some time now. I feel there are many benefits of going through source codes of such well-maintained and active open source frameworks. Understanding source code can help us identify potential issues from both a user’s as well as a developer’s perspective, we might be able to contribute to documentations better, we could understand Qiskit and Quantum Computing better, we could compare implementation of algorithms vs their original documentation in research papers, we could also help resolve some existing issues, it can help us understand good programming practices and learn few tips from the experienced developers that create such wonderful frameworks that we, as users love to work with. Why did I choose Qiskit Optimization among so many repositories in Qiskit? There is no major reason, I would like to dive deeper into everything that Qiskit has, but one reason is that I was working on an issue raised in Qiskit Optimization, so it seemed like a natural choice. The other reason is that Optimization problems are among important problems that we all would want to solve using Quantum Computing. The primary focus for the this blog and the one immediately following it, would be the converters in Qiskit Optimization and of course, we will also cover some parts of other modules that are essential to understand converters. To follow this blog, we need to be comfortable with basics of Python programming. My aim here is to describe what my approach was.

To understand source codes, I think the top-down approach is the best. In this regard, the tutorial on using Quadratic program was really helpful. The reason I realized I need to understand Quadratic Program in Qiskit Optimization is because when we go through the codes for each converter within converters, we would realize that there is no way to understand those without understanding all the methods, attributes and properties (decorators) of a Quadratic program in Qiskit. Once I went through this tutorial, I started diving deeper into the source code of Quadratic program. Through the source code, the tutorial and in my approach to just generally create a quadratic program and solve it without Qiskit, I realized there is a well known python package called Docplex created by IBM itself. I then started realizing that the Quadratic program in Qiskit is designed very similar to Docplex and that makes sense. In fact, the very first quadratic program in the tutorial is basically a docplex model converted into Qiskit’s quadratic program.

I tried randomly creating quadratic programs with linear and quadratic constraints and then, tried solving it with docplex. I couldn’t solve many because they were not solvable because they either did not have a ‘convex’ objective or a ‘convex’ quadratic constraint. What does this even mean? Let’s look at plots of some functions and consider that we are aiming to find the minimum of these functions:

The above is a typical quadratic convex function. You can see that it’s bowl shaped and it’s very intuitive that such a function would have a minimum and I could even highlight that it would be around point A. Let’s take another example:

In the above, when one sees locally, there are 2 minimums, one at A and one at B, though the global minimum is at B. There is a high chance for an optimizer to get stuck at A and treat that as a minimum. Though in this function, one can say that there are 2 convex parts, the overall function is not convex. Docplex can’t solve such objective functions.

The above actually doesn’t have a minimum and is also not convex, if we think of convex as some bowl-shaped function. The best way to understand a convex function mathematically is to first understand what a convex set means. We might have learnt about sets in high school. Even if any of us hasn’t learnt it or doesn’t remember it, we can think of a set as just a collection of distinct points. A convex set is a set where all points on the line joining 2 points in the set are within the set itself. So, if we consider the surface of a book as a set of points, clearly that is a convex set. If we consider our fingers as a set of points and open up our fingers, that’s clearly a non-convex set. You can see pictorial examples of convex set and non-convex set on wikipedia: https://en.wikipedia.org/wiki/Convex_set. A convex function is a function for which the set of points on and above the graph form a convex set. So for docplex to solve quadratic problems, the objective and all the constraints need to be convex. It seems intuitive by all that we discussed so far that a linear objective and a linear constraint are clearly convex.

A typical example of quadratic program written with docplex is:

and when you see a quadratic program with qiskit, it’s actually quite similar:

The methods in docplex and qiskit quadratic program are very similar. You could check docplex in detail here: http://ibmdecisionoptimization.github.io/docplex-doc/mp/docplex.mp.model.html.

Coming back to Qiskit and quadratic program, if you actually run the tutorials from the IBM Quantum Lab, as of today, you will notice that the qiskit optimization module used in the lab is not the most updated one. Even the tutorials on the Lab are not updated, as of today. When you just open IBM Quantum Lab, you will see qiskit-tutorials folder in the lab files which further has a folder for qiskit optimization tutorials. I went through the release notes and found that the specific differences I am referring to have been made just 19 days ago. Even on PyPI, it has not been updated yet. I will highlight some differences below:

There are some ways to display a quadratic program. You can see all the different ways here. One of them is in LP (linear program) format, which is again related to how docplex models are usually displayed. You will find export_as_lp_string method in the source code of quadratic program. This method is there even in docplex, so all this method in qiskit optimization’s quadratic program does is to convert it to docplex by using the same method from docplex. The display of the above quadratic program using export_as_lp_string method would look like below:

In the most recent version of qiskit optimization, there is an addition of another display method called prettypink in the quadratic program source code. The source code for this type of display is here. The display with prettypink looks like this:

The major difference I notice now after the update is the way objects are displayed. For example, one can get the list of all variables in a quadratic program using the variables property. For the quadratic program below,

the variables property would earlier give a list like below:

This is how typically in Python, objects are displayed when we print them. We can see that the class of each element in the list above is called Variable. The path of the code for Variable within qiskit optimization is also displayed. The hexadecimal values is just the location in the memory where these objects are stored. This can be non-intuitive for some users, which is why I think in the updated version of the module, they have ensured it displays differently. The display by default happens with some in-built methods called __str__ and __repr__. They have just overridden these default methods. So the variables are now displayed as (for some other quadratic program):

They have done this change for every class in the qiskit optimization module. For eg: the linear constraints could be fetched by the linear_constraints property and it previously looked like below:

and now it looks like:

This was as far as the differences I noticed that just happened within last 19 days or so and if we really think, we could come up with such ideas as users or developers. Let’s briefly go over Quadratic program source code.

One very useful and interesting aspect of all open source python codes these days is the use of type annotations. This was not there in Python before and got introduced only since python 3.5 if I am not wrong. This is extremely helpful to understand source codes. Let’s take examples from qiskit optimization’s quadratic program source code. See the constructor __init__ and the signature of the method _add_variables from quadratic program below:

By type annotations, we mean things like List[Variable], Dict[str,int], Union[float, int], Tuple[list[str], List[Variable]]. So, in __init__, when we say self.__linear_constraints: List[LinearConstraint], we mean that the attribute _linear_constraints of the class should be of the type list and all elements of that list need to be of the type LinearConstraint and you will see that LinearConstraint is a class created within qiskit optimization, the source code of which is here. Union[float,int] means that the function argument or the attribute in case of the constructor can either take a value which is float or it can take an int. This type of type hinting is extremely useful because with this, one exactly knows what type of inputs/arguments/attributes need to passed and what is the type expected out of a method. If we didn’t have this, we might often end up getting type errors, which is common in Python.

To further understand qiskit optimization’s quadratic program class, we will have to understand other classes because we will notice that for a lot of methods and properties, the outputs are objects of the classes created within qiskit optimization. Let us start with the Variable class. The source code starts with the following:

The Enum class which VarType has inherited, helps in enumerating categories. We can see how this helps below (snapshot of the Variable class with just its constructor or __init__ method:

We notice that within __init__, we have the class attribute vartype of the class type VarType and it’s default value is set to VarType.CONTINUOUS. This value VarType.CONTINUOUS makes sense only because of Enum. We also see that Type = VarType, this means that for an object v of type Variable, its vartype can be seen as v.Type.CONTINUOUS or v.Type.BINARY or v.Type.INTEGER.

Note that in the LP representation of the quadratic program, we saw variables were described as either binary or general. The general refers to integer type and any variable in the quadratic program that’s neither mentioned under binary or general, is continuous. This is the format followed in docplex LP representation and it’s the same here.

We also see that the Variable class inherits QuadraticProgramElement. If we see the source code of QuadraticProgramElement, we will see that it just has properties to get and set Quadratic program. The reason we can’t let Variable directly inherit Quadratic Program is because that would require us to import QuadraticProgram in the source code of Variable class, but we also import Variable class in the source code of Quadratic Program and this would lead to cyclical reference.

The rest of the methods are just properties (created with property decorator). Creating properties makes it easy for users to access and set details related to an object of a class. For example, for a variable v, we can get upper bound and lower bound of v by simply executing v.upperbound and v.lowerbound. The Variable object properties that would be helpful for us when we look at converters are name, upperbound, lowerbound, varType.

Next, let’s see the QuadraticObjective class. Like the source code of Variable class, the source code of QuadraticObjective class starts with a class called ObjSense that inherits Enum (see below). QuadraticObjective class also inherits QuadraticProgramElement.

The important properties here are constant, linear, quadratic, sense. The linear property gives out the linear component of the quadratic objective and is of the type LinearExpression, the quadratic property gives out quadratic component and is of the type QuadraticExpression. The property sense gives out object of the type ObjSense. So for a given quadratic program qp, all these properties would be accessed via qp.objective (eg: qp.objective.linear).

The source code for LinearExpression class starts with ExpressionBounds class that is decorated by dataclass. We will see its usage a little later, but here’s how that looks:

This has a coefficients property for getting the coefficients of the linear expression or setting the coefficients of a linear expression. A useful method is to_dict that just expresses the linear expression as a dict. One can also pass use_names=True while executing to_dict. So, the output with to_dict would be something like {0:3,1:4,2:8} or {‘x’:3,’y’:4,’z’:8} if we set use_names to True.

QuadraticExpression is similar to LinearExpression in the way it is designed, but here we need to deal with tuples of variables (eg: (‘x’,’y’), (‘y’,’y’)).

LinearConstraint class inherits Constraint class, the source code of which starts with the ConstraintSense class that inherits enum (shown below). The constraint class has some useful properties like name, rhs, sense etc. Further the LinearConstraint class has the linear property that gives out the linear expression (type LinearExpression, so all we discussed for LinearExpression would work here.) with respect to the LHS of the constraint.

QuadraticConstraint is designed similar to LinearConstraint. It inherits Constraint class. Along with linear property, it also has a quadratic property that gives out object of type QuadraticExpression.

Coming back to the Quadratic program source code. By the above discussion about some other classes, we have actually discussed a lot about Quadratic programs itself. The source code has useful properties, several simple methods for adding variables, adding constraints etc. A couple of interesting methods are to_ising and from_ising for conversion between the quadratic program and the ising model, but I will cover those in a future blog. You can see the entire list of methods, attributes and properties here.

We now know everything that can help us understand the source code of converters. We will dive into converters in Qiskit Internals- Part 2