Noise-Directed Adaptive Remapping Applied to the Maximum Independent Set

Quantum computing is a promising field with rapid research evolution and interest, particularly due to its potential for developing new heuristic approaches to hard combinatorial optimization problems. Regarding nondeterministic polynomial time problems, they are possibly the most significant problems in computing, with the P=NP dilemma, and these have an impact on several real-world applications, with the Maximum Independent Set (MIS) being one of them as a binary combinatorial problem. In this work, we propose a recent method for solving such problems using quantum computing, the Noise-Directed Adaptive Remapping (NDAR), as a possible quantum approach to the MIS. Therefore, this work implemented the NDAR algorithm in a quantum computer simulator and used it to solve instances of the MIS. Results showed that NDAR can perform better for this problem than QAOA, setting NDAR as a promising algorithm for solving binary combinatorial optimization problems.