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

Edward Farhi, Sam Gutmann, Daniel Ranard +1

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 Approxi…