Maximum Independent Set

The Maximum Independent Set (MIS) problem is a well-known optimization problem in graph theory and computer science. Given an undirected graph, an independent set is a subset of vertices in which no two vertices are adjacent. The MIS problem seeks to find the largest such set, i.e., the independent set of maximum size.

The MIS problem is related to other combinatorial optimization problems, such as the Minimum Vertex Cover and Maximum Clique problems. Variants of the MIS problem, with additional constraints or objectives, are also studied, and the techniques developed for solving the MIS problem can often be adapted to these related problems.

The MIS problem is NP-hard, meaning that there is no known algorithm that can solve all instances of the problem in polynomial time (unless P = NP). It has applications in various fields, including network design, scheduling, resource allocation, and more. The complexity of the problem makes it a significant subject of study in both classical and quantum computing.

Quantum computing offers new avenues for tackling the MIS problem. Quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), have been applied to find approximate solutions to the MIS problem. While finding the exact maximum independent set remains a complex task, quantum algorithms like QAOA may provide advantages in terms of speed or quality of approximations for specific instances of the problem. 

Precisely solving the MIS problem, especially for large and complex graphs, remains a challenging task. Research continues to explore new algorithms, heuristics, and quantum approaches to address the problem. Understanding the structure and properties of specific graphs can lead to more efficient solutions, and the interplay between classical and quantum methods is an area of ongoing exploration. One quantum approach under investigation is the use of neutral atom quantum computers, which have been garnering attention for their ability to precisely solve MIS problems, not just approximate them.

The Maximum Independent Set problem is a fundamental and challenging problem in computer science. Its complexity and wide-ranging applications make it a subject of interest in both classical and quantum computing. Quantum approaches to the MIS problem represent an exciting frontier, with potential to enhance our ability to solve this and related optimization problems.

What is the Maximum Independent Set?

The short definition of MIS is the largest set of vertices in a graph such that no two vertices in that set share an edge. However, the long definition has a few additional elements to it:

• The “independence number” of a graph is the size of the set, the number of vertices in the set, that represents the largest possible independent set that can be found
• Despite the term “set” being singular, there may be more than one independent set within a graph that has a number of vertices equal to the independence number
• Describing the complexity of MIS problems as NP-hard is for finding just one of the potentially many correct solutions
• The maximum should not be confused with the maximal, which cannot add vertices to the set, but for which the number of vertices is less than the independence number
• Another way to think about MIS is that for every edge in the graph, no edge is allowed to have more than one of its vertices in the independent set

The Wolfram MathWorld definition of “Maximum Independent Vertex Set” makes an interesting distinction by including the word “vertex” within the term. This is because it is also possible to have independent sets of edges, including maximum and maximal sets of edges, although these may be referred to as vertex matching problems. Vertex matching is conceptually similar, in that MIS thinks about vertices without shared edges whereas vertex matching thinks about edges without shared vertices. 

For more information on MIS, there is an entire book chapter called “Maximal Independent Sets” by K. Erciyes that has been accessed more than 2,000 times. At the time this definition is being written, it has also been cited once. The book containing this chapter is part of the Computer Communications and Networks book series (CCN). 

Quantum Algorithms for Maximum Independent Set

There is no singular maximum independent set algorithm for quantum computers. In fact, there are four high-level approaches to consider, each with their own strengths and weaknesses:

• The Quantum Approximate Optimization Algorithm (QAOA), which is actually a family of algorithms, is used with gate-based universal quantum computers
• The Variational Quantum Eigensolver (VQE), which is also a family of algorithms, is related to QAOA, but is used more commonly for quantum chemistry than for combinatorial optimization
• Quantum annealing, which runs on specialized hardware called quantum annealers, has no proven computational advantages over classical algorithms
• Rydberg blockades, which are a phenomena of neutral atom arrays, are natural solvers of MIS problems

It is important to note that, like quantum annealing, QAOA and VQE also do not have proofs of computational advantages. Among their challenges is the challenge of classically optimizing ever larger counts of parameters. In other words, as their parameterized circuits grow to tackle harder problems, they become increasingly more difficult to work with. Another major challenge is that these parameters are optimized iteratively, and each iteration currently requires waiting in a potentially-lengthy queue for a quantum computer. 

Quantum Implementation of MIS

Using logic maximum independent set problems are best solved with neutral atom quantum computers. First, the graph is mapped to a two-dimensional array of individual atoms. Each vertex is naturally represented by an atom. Then, a mechanism called the “Rydberg blockade” naturally prevents neighboring atoms, representing adjacent vertices on the graph, to be in their Rydberg states at the same time. The atoms that end up in their Rydberg states, therefore, represent an independent set of vertices of the graph. 

Each independent set from a neutral atom quantum computer will at least be maximal. However, quantum computers generally don’t run anything just one time. They’re probabilistic, so jobs might execute hundreds, thousands, or even tens of thousands of times. This means that a single, typical job will return many maximal independent sets, which are statistically likely to include multiple maximum independent sets, depending on the selected shot count. Therefore, retrieving multiple correct solutions becomes much more likely than receiving one or zero correct solutions.

This webinar demonstrates solving MIS and other optimization problems using the QuEra computer.

This application note provides an example of an MIS problem solved by quantum computers.