Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA

Understand

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.