Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
Abstract
Every 3-regular graph of girth at least g has a cut containing at least a fraction Mg of its edges, and the best rigorous bounds at large girth are 0.912≤ limg→∞Mg ≤ 0.92386. Lower bounds on Mg 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 Mg 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 M66 ≥ 0.9127 at 99.99999% confidence level, which raises the asymptotic lower bound from $0.912$ to $0.9127$.
Related
- Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
- On local spectra of classical distance-regular graphs with b = 2
- Uniform bounds on symbolic powers in regular rings
- Infinitesimal Hilbertianity for manifolds with Sobolev regular Riemannian metrics through uniform lower capacity bounds
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
BibTeX
@misc{morone2026whither,
title = {{Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs}},
author = {Flaviano Morone and Shivang Rawat and Dries Sels},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17236},
eprint = {2610.17236},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17236},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
AU - Flaviano Morone
AU - Shivang Rawat
AU - Dries Sels
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17236
UR - https://arxiv.org/abs/2610.17236
AB - 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≤ lim_g→∞M_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$.
ER -