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

Flaviano Morone, Shivang Rawat, Dries Sels

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\le \lim_{g\to\infty}…