From Maximum Cut to Maximum Independent Set
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914951571963904 |
|---|---|
| author | Wu, Chuixiong Wang, Jianan Zuo, Fen |
| author_facet | Wu, Chuixiong Wang, Jianan Zuo, Fen |
| contents | 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ős-Ré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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06758 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | From Maximum Cut to Maximum Independent Set Wu, Chuixiong Wang, Jianan Zuo, Fen Quantum Physics Combinatorics Optimization and Control 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ős-Ré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. |
| title | From Maximum Cut to Maximum Independent Set |
| topic | Quantum Physics Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2408.06758 |