Optimization

We read and hear, that quantum computing will be useful at a range of tasks. One of them is optimization, which is the problem of finding the best solution from all possible solutions. Optimization problems are common in business. For example, you might want to find the optimal portfolio of financial assets (lowest cost, highest return, least risk, or some combination of these factors that you care about). Or you might want to figure out the best way to deliver packages. In this case, “best” might mean shortest time or lowest fuel cost or some combination of the two. To get a feeling for why optimization problems are a huge challenge for conventional computers, let's consider a particular optimization problem...

Max-Cut problem

The specific problem, we want to look at, is called the Max-Cut problem.
Given a graph with vertices and connections between these vertices, the goal is to find two subsets of red and green vertices so that the number of cut edges between the two subsets gets maximized. Only edges that connect vertices of different color are cut (cuttable edges are shown in the figure below as a dashed line). If the edge connects vertices of the same color, it can’t be cut (solid line).

Consider the following graph and two different cuts.

The number of cut edges for the left cut is 2, while it is 4 for the right one. The right cut is indeed the optimal solution as the number of edges between the red and green subsets can't be higher than 4 (there are only 4 edges after all 😊).

The Max-Cut Problem is not only of theoretical interest, but it has applications in fields such as network design, statistical physics, circuit layout design, or data clustering. While we just used a weight (i. e. the value attributed to a connection) of 1 for each connection, for real-world tasks those weights have some concrete implication, e. g. they might represent the cost of building infrastructure between those two nodes.

Go ahead and give it a try. We prepared three Max-Cut problem sets for you and invite you to try and come up with solutions. Pay attention to how you approach the problem.

Exercise

Find a subset of vertices such that the number of edges between the two subsets gets maximized. Click on a vertex to change its subset.

Try out all three graphs to continue ...

Solving optimization problems using a quantum computer

You may find it difficult to come up with exact solutions when graph size increases. Actually, the Max-Cut problem is so difficult, that there are no efficient algorithms providing the optimal solution. At this point, we may want to give up in resignation. Often, however, an approximately optimal solution is sufficient. This is true for a lot of tasks we need to solve. Finding the best route for a fleet of logistics trucks in terms of time and fuel consumption is awesome, but finding very good routes that reduce the amount of fuel and time used significantly is already great.

Actually, many industrial and financial problems, such as finding routes in logistics, positioning sensors in an automobile or pricing financial instruments, are optimization problems like Max-Cut. As the number of variables in these problems increases, solving an optimization problem using conventional computers becomes intractable as it would require too much time to check all possible solutions. However, due to an inherent parallelism in quantum computers, it is possible to improve the sub-optimal solutions that conventional computers find without incurring the cost of exponentially longer computation times.

Why is it so hard to solve optimization problems?

  • A

    Optimization problems are hard to do because they only allow for one correct answer.

  • B

    With increasing problem size the number of possible solutions explodes making it impossible to check them all if the only way is brute forcing a solution.

  • C

    It is very hard to describe optimization problems in a language a classical computer understands.