Encodings of the weighted MAX k-CUT problem on qubit systems

The weighted MAX <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="m2"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> -CUT problem involves partitioning a weighted undirected graph into k subsets, or colors, to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This study explores encoding methods for MAX <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="m3"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> -CUT on qubit systems by utilizing quantum approximate optimization algorithms (QAOA) and addressing the challenge of encoding integer values on quantum devices with binary variables. We examine various encoding schemes and evaluate the efficiency of these approaches. The study presents a systematic and resource-efficient method to implement the phase separation operator for the cost function of the MAX <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="m4"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> -CUT problem. When encoding the problem into the full Hilbert space, we show the importance of encoding the colors in a balanced way. We also explore the option of encoding the problem into a suitable subspace by designing suitable state preparations and constrained mixers (LX- and Grover-mixer). Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes, particularly in optimizing circuit depth, approximation ratios, and computational efficiency.