Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth

Anuj Apte; Abid Khan; Edward Farhi; Kunal Marwaha; Sami Boulebnane; Ruslan Shaydulin

Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth

Anuj Apte, Abid Khan, Edward Farhi, Kunal Marwaha, Sami Boulebnane, Ruslan Shaydulin

arXivarxiv/2609.39042Sep 30, 2026quant-phscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.39042
curl -X POST /api/v1/records/arxiv/2609.39042/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.39042/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'