arXiv preprint ·
Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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\geq3$. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general $d$ and $k \geq 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\geq 9$, corresponding to girth $g\geq 20$, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-$k$-Cut problem.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Decentralized Decision-Making among Heterogeneous Autonomous Vehicles: An $α$-Potential Game Framework
Mean field games as a tool for AI safety: a worked example from the July 2026 Hugging Face incident
Breaking the Shot-Noise Barrier: Cached Recycled Variance-Reduced Gradients for Quantum Optimization
OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.