Formulations of the max k-cut problem on classical and quantum computers

Recent claims on "solving" combinatorial optimization problems via quantum computers have attracted researchers to work on quantum algorithms. The max k-cut problem is a challenging combinatorial optimization problem with multiple notorious mixed integer linear optimization formulations. In this paper, we revisit the binary quadratic optimization formulation of Carlson and Nemhauser (Operations Research, 1966) and provide theoretical and computational comparisons between different mixed integer optimization formulations of the max k-cut problem. While no claim on "quantum advantage" is provided, we introduce quadratic unconstrained binary optimization (QUBO) formulations with tight penalty coefficients. For at least 60% of test instances, the computational experiments show the superiority of the tight models over naive ones in terms of the quality of feasible solutions in the quantum context. We also design quantum circuits to find feasible solutions using a quantum approximate optimization algorithm (QAOA). A preprocessing procedure is proposed to make instances manageable for quantum computers. In comparison to the existing fixing procedures, our proposed preprocessing algorithm reduces the number of vertices and edges of some existing benchmark instances up to 30% and 25%, respectively. Finally, we conduct an extensive set of experiments on classical and quantum-inspired formulations. Our codes and data are available on GitHub.


Submitted to a journal.



View Formulations of the max k-cut problem on classical and quantum computers