From Maximum Cut to Maximum Independent Set

Autor:	Wu, Chuixiong, Wang, Jianan, Zuo, Fen
Rok vydání:	2024
Předmět:	Quantum Physics Mathematics - Combinatorics Mathematics - Optimization and Control
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: Independence number of 1dc.2048 updated, new results for 1dc.4096 included, references added; 22 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.06758 Zobrazit plný text záznamu View this record from Arxiv