A Lovász theta lower bound on Quantum Max Cut
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914217349611520 |
|---|---|
| author | Huber, Felix |
| author_facet | Huber, Felix |
| contents | We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_20326 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Lovász theta lower bound on Quantum Max Cut Huber, Felix Quantum Physics Combinatorics We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut. |
| title | A Lovász theta lower bound on Quantum Max Cut |
| topic | Quantum Physics Combinatorics |
| url | https://arxiv.org/abs/2512.20326 |