To main content

Encodings of the weighted MAX k-CUT problem 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 operator for the cost function of the MAX k-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 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.

Category

Academic article

Language

English

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics
  • University of Oslo

Date

15.08.2025

Year

2025

Published in

Frontiers in Quantum Science and Technology

Volume

4

View this publication at Norwegian Research Information Repository