Quantum local algorithms exceed classical ones on max k cut graphs
Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth
Data Structures and Algorithms
Summary
Max-k-Cut is a way to split a network into groups to maximize the number of connections between different groups. The authors studied classical and quantum algorithms that work locally on certain structured networks and found that a quantum approach called QAOA can do better than the best classical local methods when the network is large and has certain properties. They improved classical methods too, but beyond a certain point, the quantum algorithm still outperforms them. This suggests that quantum computing can have advantages on specific graph problems under realistic assumptions.
What this means in practice
- •For quantum algorithm developers: Develop and test quantum algorithms for network partition problems using the provable guarantees on QAOA’s advantage over classical methods.
- •For graph analytics engineers: Implement improved classical local vector algorithms for Max-k-Cut in network analysis tools aiming for better performance on regular graphs.
Authors
Anuj Apte, Abid Khan, Edward Farhi, Kunal Marwaha, Sami Boulebnane, Ruslan Shaydulin
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.