Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
Abstract
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 based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for k≥3. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general d and k ≥ 2. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths p≥ 9, corresponding to girth g≥ 20, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-k-Cut problem.
Related
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
- Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates
- Shifted Pell–Lucas Polynomial-Based Algorithms for Fractional and Classical Rosenau–Hyman Models
- Polynomial-time classical algorithms for mean-field models up to the glass transition
- Quantum Advantage in Multiple Access Wiretap Channels with Entangled Transmitters
BibTeX
@misc{apte2026provable,
title = {{Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth}},
author = {Anuj Apte and Abid Khan and Edward Farhi and Kunal Marwaha and Sami Boulebnane and Ruslan Shaydulin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39042},
eprint = {2609.39042},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39042},
}
RIS
TY - UNPB
TI - Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
AU - Anuj Apte
AU - Abid Khan
AU - Edward Farhi
AU - Kunal Marwaha
AU - Sami Boulebnane
AU - Ruslan Shaydulin
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39042
UR - https://arxiv.org/abs/2609.39042
AB - 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 based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for k≥3. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general d and k ≥ 2. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths p≥ 9, corresponding to girth g≥ 20, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-k-Cut problem.
ER -