{"id":"arxiv/2609.39042","url":"https://arxiv.org/abs/2609.39042","tags":["quant-ph","cs.DS","math.OC"],"score":0,"title":"Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth","domain":"quant-ph","source":"arxiv","authors":["Anuj Apte","Abid Khan","Edward Farhi","Kunal Marwaha","Sami Boulebnane","Ruslan Shaydulin"],"reviews":0,"subject":"quant-ph","summary":"Broadening the study of quantum optimization algorithms from binary to $k$-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-$k$-Cut on $d$-regular graphs of girth $g$. We advance classical algorithms for this problem by developing a local vector algorithm…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}