Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

Every 3-regular graph of girth at least g has a cut containing at least a fraction M g of its edges, and the best rigorous bounds at large girth are 0.912 g to infinityM g 0.92386. Lower bounds on M g follow from the performance of local algorithms: on a graph of girth g 2p+2 a depth- p local algorithm sees the same tree around every edge, so its expected cut fraction on that tree bounds M g from below. We apply this strategy to the Variational Iterative Rotation Algorithm (VIRAL), a classical local algorithm, and evaluate it on the depth- p tree for every even depth up to p=32. The resulting bounds exceed those recently obtained from the Quantum Approximate Optimization Algorithm (QAOA) for every p 4, by 0.005 to 0.011, and they extend the range of girths covered from g=36 to g=66. Notably, at g=66 we obtain M 66 0.9127 at 99.99999% confidence level, which raises the asymptotic lower bound from 0.912 to 0.9127.