Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914062560919552 |
|---|---|
| author | Tate, Reuben Gupta, Swati |
| author_facet | Tate, Reuben Gupta, Swati |
| contents | There is a strong interest in finding challenging instances of NP-hard problems, from the perspective of showing quantum advantage. Due to the limits of near-term NISQ devices, it is moreover useful if these instances are small. In this work, we identify two graph families ($|V|<1000$) on which the Goemans-Williamson algorithm for approximating the Max-Cut achieves at most a 0.912-approximation. We further show that, in comparison, a recent quantum algorithm, Quantum Approximate Optimization Algorithm (depth $p=1$), is a 0.592-approximation on Karloff instances in the limit ($n \to \infty$), and is at best a $0.894$-approximation on a family of strongly-regular graphs. We further explore construction of challenging instances computationally by perturbing edge weights, which may be of independent interest, and include these in the CI-QuBe github repository. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24108 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families Tate, Reuben Gupta, Swati Quantum Physics Data Structures and Algorithms Combinatorics There is a strong interest in finding challenging instances of NP-hard problems, from the perspective of showing quantum advantage. Due to the limits of near-term NISQ devices, it is moreover useful if these instances are small. In this work, we identify two graph families ($|V|<1000$) on which the Goemans-Williamson algorithm for approximating the Max-Cut achieves at most a 0.912-approximation. We further show that, in comparison, a recent quantum algorithm, Quantum Approximate Optimization Algorithm (depth $p=1$), is a 0.592-approximation on Karloff instances in the limit ($n \to \infty$), and is at best a $0.894$-approximation on a family of strongly-regular graphs. We further explore construction of challenging instances computationally by perturbing edge weights, which may be of independent interest, and include these in the CI-QuBe github repository. |
| title | Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families |
| topic | Quantum Physics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2509.24108 |