Combinatorial Optimization

Combinatorial optimization is a subfield of the optimization field of mathematics. In combinatorial optimization, a problem has a finite set of possible solutions. The challenge is to find the optimal solution within that finite set. 

The advantage of this approach is that although large search spaces can be infeasible to search in their entireties, large swaths of each search space can be disregarded, thus making the problem effectively smaller. An alternate approach, and possibly a complementary approach, is to find approximate solutions in lieu of precise solutions. In other words, even if a solution is not optimal, it may be sufficient for it to be near optimal, and there are combinatorial optimization algorithms for that.

The significance of this subfield is that combinatorial optimization applications have widespread usefulness. Use cases probably span all industries, as well as organizations of all sizes. 

What is Combinatorial Optimization?

Quantum combinatorial optimization is a subset of both quantum computing and combinatorial optimization. One possible goal of using quantum computers in this manner is to efficiently explore entire problem spaces simultaneously, which is something classical computers just can’t do. 

Another possible goal is to leverage quantum computers to find approximate solutions. The most widely used quantum algorithm to do this is called the Quantum Approximate Optimization Algorithm (QAOA), which has actually evolved into a family of algorithms. Secondarily, an algorithm called the Variational Quantum Eigensolver (VQE) may be used, however it is more commonly used to approximate solutions for chemistry problems. Like QAOA, VQE has evolved into a family of algorithms.

An alternate approach involves quantum annealing, although this approach presents two challenges. First, it is only applicable to a subset of problems. And, second, it can be efficiently simulated classically.

Finally, the Rydberg blockade mechanism of neutral atoms is a natural solver for certain classes of problems. The most heavily researched are Maximum Independent Set (MIS) and Maximum Clique problems, however the applicability is broader. Our article titled “Maximum Independent Set” defines MIS is the largest possible set of vertices in a graph in which no two vertices are adjacent. Max Clique is the complement of MIS, finding the adjacent vertices in the graph.

Types of Combinatorial Optimization Problems

Combinatorial optimization problems have broad applicability. At a high level, some of the most common classes of these problems include:

• Routing, which may involve finding the shortest route, the fastest route, the least expensive route, etc.; a famous example is the Traveling Salesperson Problem (TSP)
• Scheduling, which is conceptually similar to routing, except using durations instead of distances to minimize total completion times of various processes
• Knapsack, which selects contents for a container, given the contents’ sizes and weights, as well as the constraints of the container, that maximize the final value of the container
• Matching, which finds optimal pairings within weighted graphs; a famous example is the Marriage Problem
• Minimum Spanning Tree, which finds the tree with the minimum possible total edge weight within a graph

Combinatorial optimization is an important contributor to the field of artificial intelligence (AI), which includes machine learning (ML). The taining of machine learning models involves the optimization of neural network parameters and hyperparameters. Therefore, all of those applications are dependent on optimal optimization algorithms.

Quantum Algorithms for Combinatorial Optimization

The most common quantum combinatorial optimization algorithms, as previously noted, are the Quantum Approximate Optimization Algorithm (QAOA), the Variational Quantum Eigensolver (VQE), and their respective families of algorithms. There is a class of problem called Quantum Least Squares Fitting which uses the Harrow, Hassidim, and Lloyd (HHL) algorithm, but HHL is too large to run on the current generation of quantum computers. Furthermore, a paper titled “Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations” by the team of Yuki Sano, Kosuke Mitarai, Naoki Yamamoto, and Naoki Ishikawa, discusses use of the well-known Grover’s Algorithm to solve combinatorial problems. And, again, there is the Rydberg blockade mechanism of neutral atoms to solve certain combinatorial optimization problems naturally.

A doctoral dissertation titled “Combinatorial Optimization Algorithms on Quantum and Quantum Inspired Devices,” by Xiaoyuan Liu of the University of Delaware, is an exploration of the current landscape. Of particular interest, and something that has recently been demonstrated on our 256-qubit “Aquila” device, is the process of dividing large problems into sets of smaller problems, each of which can then be solved on today’s quantum computers.

‍