Encodings of the weighted MAX k-CUT on qubit systems

Abstract

The weighted MAX k-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 paper explores encoding methods for MAX k-CUT on qubit systems, 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 paper presents a systematic and resource efficient method to implement phase separation for diagonal square binary matrices. 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 to encode 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.

References in corpus (7)

• A Quantum Approximate Optimization Algorithm
• Warm-starting quantum optimization
• Constrained mixers for the quantum approximate optimization algorithm
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• Compact Circuits for Constrained Quantum Evolutions of Sparse Operators