Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909580141789184 |
|---|---|
| author | Gribling, Sander Sinjorgo, Lennart Sotirov, Renata |
| author_facet | Gribling, Sander Sinjorgo, Lennart Sotirov, Renata |
| contents | We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11120 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs Gribling, Sander Sinjorgo, Lennart Sotirov, Renata Quantum Physics Optimization and Control 68W25, 90C22, 68Q25, 81P40 We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes. |
| title | Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs |
| topic | Quantum Physics Optimization and Control 68W25, 90C22, 68Q25, 81P40 |
| url | https://arxiv.org/abs/2504.11120 |