Benjamin Villalonga

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 ≥ 16, at depth p ≥ 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. Furthermore, our guaranteed cut fractions apply to random instances of large 3-regular graphs since they are effectively large girth for our purposes. We also apply the QAOA to the Maximum Independent Set problem on the same class of graphs.