From Maximum Cut to Maximum Independent Set
Autor: | Wu, Chuixiong, Wang, Jianan, Zuo, Fen |
---|---|
Rok vydání: | 2024 |
Předmět: | |
Druh dokumentu: | Working Paper |
Popis: | The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erd\H{o}s-R\'{e}nyi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems. Comment: 22 pages, 5 figures |
Databáze: | arXiv |
Externí odkaz: |