Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912847235121152 |
|---|---|
| author | Farhi, Edward Gutmann, Sam Ranard, Daniel Villalonga, Benjamin |
| author_facet | Farhi, Edward Gutmann, Sam Ranard, Daniel Villalonga, Benjamin |
| contents | We study MaxCut on 3-regular graphs of minimum girth $g$ for various $g$'s. We obtain new lower bounds on the maximum cut achievable in such graphs by analyzing the Quantum Approximate Optimization Algorithm (QAOA). For $g \geq 16$, at depth $p \geq 7$, the QAOA improves on previously known lower bounds. Our bounds are established through classical numerical analysis of the QAOA's expected performance. This analysis does not produce the actual cuts but establishes their existence. When implemented on a quantum computer, the QAOA provides an efficient algorithm for finding such cuts, using a constant-depth quantum circuit. To our knowledge, this gives an exponential speedup over the best known classical algorithm guaranteed to achieve cuts of this size on graphs of this girth. We also apply the QAOA to the Maximum Independent Set problem on the same class of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_12789 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA Farhi, Edward Gutmann, Sam Ranard, Daniel Villalonga, Benjamin Quantum Physics Discrete Mathematics Combinatorics We study MaxCut on 3-regular graphs of minimum girth $g$ for various $g$'s. We obtain new lower bounds on the maximum cut achievable in such graphs by analyzing the Quantum Approximate Optimization Algorithm (QAOA). For $g \geq 16$, at depth $p \geq 7$, the QAOA improves on previously known lower bounds. Our bounds are established through classical numerical analysis of the QAOA's expected performance. This analysis does not produce the actual cuts but establishes their existence. When implemented on a quantum computer, the QAOA provides an efficient algorithm for finding such cuts, using a constant-depth quantum circuit. To our knowledge, this gives an exponential speedup over the best known classical algorithm guaranteed to achieve cuts of this size on graphs of this girth. We also apply the QAOA to the Maximum Independent Set problem on the same class of graphs. |
| title | Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA |
| topic | Quantum Physics Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2503.12789 |