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

1 Introduction and related work

The quantum approximate optimization algorithm (Farhi et al., 2014)/quantum alternating operator ansatz (Hadfield et al., 2019) (QAOA) is a widely studied hybrid algorithm for approximately solving combinatorial optimization problems encoded into the ground state of a Hamiltonian. Given an objective function f : { 0,1 } n → R, the problem Hamiltonian is defined as H P | x 〉 = f ( x ) | x 〉. Thus, the ground states of H P correspond to the minima of the objective function. In the general framework of QAOA, a parameterized quantum state is prepared as follows:

Starting from an initial state | ϕ 0 〉, the algorithm alternates between applying the phase-separation operator U P ( γ ) and the mixing operator U M ( β ). The goal is to optimize the parameters γ , β ∈ R such that 〈 γ , β | H P | γ , β 〉 is minimized.

Since the original proposal of QAOA, several extensions and variants have been introduced. One such extension is ADAPT-QAOA (Zhu et al., 2022), which iteratively adds only the terms that most contribute to lowering the expectation value. Another variant is R-QAOA (Bravyi et al., 2020), which progressively removes variables from the Hamiltonian until the reduced instance can be classically solvable. A third extension, WS-QAOA (Egger et al., 2021), incorporates solutions from classical algorithms to warm-start the QAOA process. When a given problem has constraints, the design of mixers is vital. For constrained problems, the design of mixers is crucial. A well-known example is the X Y-mixer (Hadfield et al., 2017; Wang et al., 2020), which restricts evolution to “k-hot” states. GM-QAOA (Bartschi and Eidenbenz, 2020) uses Grover-like operators for all-to-all mixing of more general feasible subsets. The mixing operator of GM comprised a circuit U S that prepares the uniform superposition of all feasible states, its inverse U S †, and a multi-controlled rotational phase shift gate. Inspired by the stabilizer formalism, the LX-Mixer (Fuchs and Bassa, 2024; Fuchs et al., 2022) is a generalization of the above methods that provides a flexible framework that allows for tailored mixing within the feasible subspace.

To increase the practical relevance of QAOA, encoding problems with integer values, rather than binary variables, into qubit systems is an important area of research. This process generally introduces considerable flexibility in encoding choices, affecting not only the number of qubits and controlled operations needed but also the complexity of the optimization landscape and the quality of the approximation ratios that can be achieved. In this study, we explore various encoding schemes for the MAX k-CUT problem into qubit systems, building on and improving earlier research (Fuchs et al., 2021). This problem has numerous applications, including the placement of television commercials in program breaks, arrangement of containers on a ship with k bays, partitioning a set of items (e.g., books sold by an online shop) into k subsets, product module design, frequency assignment, scheduling, and pattern matching (Aardal et al., 2007; Ram Gaur et al., 2008). Given a weighted undirected graph G = ( V , E ), the MAX k-CUT problem consists of finding a maximum-weight k-cut. This involves partitioning the vertices into k subsets such that the sum of the weights of the edges between vertices in different subsets is maximized (Figure 1). By assigning a label x i ∈ { 1 , … , k } to each vertex i ∈ V and defining x = ( x 1 , … , x | V | ), the optimization problem for MAX k-CUT can be formulated as

max x ∈ { 1 , … , k } n C ( x ) , C ( x ) = ∑ ( i , j ) ∈ E w i j , if x i ≠ x j 0 , otherwise . (1)

Here, w i j > 0 is the weight of edge ( i , j ) ∈ E. The function C ( x ) is commonly referred to as the “cost function.” For k = 2, the MAX k-CUT problem becomes the well-known MAX CUT problem. The MAX k-CUT problem is NP-complete, and it has been demonstrated that no polynomial-time approximation scheme exists for k ≥ 2 unless P = NP (Alan and Jerrum, 1997). A randomized approximation algorithm for (1) has an approximation ratio α ifwhere x * denotes an optimal solution.

E [ C ( x ) ] ≥ α C ( x * ) ,

Expressing the solutions as strings of k-dits as in Equation 1 is a natural extension of the MAX (2-)CUT problem to k > 2. However, most quantum devices work with a two-level system, so we need to make a suitable encoding on a qubits system (Fuchs et al., 2021; Hadfield et al., 2019). One-hot encoding uses k bits for each vertex, where the single bit that is 1 encodes which set/color the vertex belongs to. Using this encoding requires k | V | qubits. However, k not being a power of 2 results in more computational states per vertex than there are colors. The corresponding subspaces need to be dealt with in a suitable fashion. The Grover or the LX-mixer (which becomes the XY-mixer in this case) can be readily applied. However, the ratio of the dimension of the feasible states to the system size is k / 2 k, which becomes exponentially small for increasing k. Therefore, it is advantageous to use a binary encoding, which does not have this problem. For a given k, we encode the information of a vertex belonging to one of the sets by | i 〉 n k, which requiresqubits. Here, ⌈ ⋅ ⌉ means rounding up to the nearest integer. Binary encoding requires n k | V | qubits, which is exponentially fewer than required by one-hot encoding. The resulting problem Hamiltonian can be written as the sum of local terms, that is,where w i , j is the weight of the edge between vertices i and j. Furthermore, the local term can be expressed aswhere clr is a set of index pairs ( i , j ) representing equivalent colors under an equivalence relation. From the definition, H e has eigenvalue + 1 for a state | i 〉 | j 〉 if i ∼ clr j and − 1 if not. The phase separating operator e − i t H e differs from e − i t H ̂ e only by a scalar factor and a global phase, so it is sufficient to realize the latter.

n k ≔ ⌈ l o g 2 ( k ) ⌉

H P = ∑ e ∈ E w e H e ,

H e = 2 H ̂ e − I , H ̂ e = ∑ ( i , j ) ∈ clr | i 〉 〈 i | ⊗ | j 〉 〈 j | . (2)

More formally, an equivalence relation ∼ clr is defined on X = { 0 , … , 2 n k − 1 }, where clr consists of all pairs ( i , j ) such that i ∼ clr j. For example, if clr = { ( 0,0 ) , ( 1,1 ) , ( 2,2 ) , ( 3,3 ) , ( 2,3 ) , ( 3,2 ) } , the equivalence relation defines the following equivalence classes: [ 0 ] = { 0 } , [ 1 ] = { 1 } , [ 2 ] = { 2,3 } . For convenience, we can work with a generating set. Suppose R is a relation on the set X. The equivalence relation on X generated by a R, denoted R ̄, is then the smallest equivalence relation on X that contains R, which can be obtained by the reflexive, symmetric, and transitive closure (in that order). Hence, only the non-trivial relations must be specified, and the above example can be generated by the closure of the relation R = { ( 2,3 ) } which generates R ̄ = { ( 0,0 ) , ( 1,1 ) , ( 2,2 ) , ( 3,3 ) , ( 2,3 ) , ( 3,2 ) }. The set of colors in the context of MAX k-CUT is then the set of equivalence classes induced by ∼ clr, denotedwith each equivalence class given by

X / ∼ clr ≔ { [ x ] : x ∈ X } ,

[ c ] ≔ { x ∈ X : c ∼ clr x } .

We recognize that the phase separating operator—the real time evolution of H ̂ e—acts by applying a phase on a specific subsets of all computational basis states. When these subsets are sparse, such unitaries can be efficiently realized (Fuchs and Bassa, 2025): let P B be the projector onto a subspace given by set of computational basis states B. The unitary operator e i t P B can be realized by a circuit for mapping the (indexed) states of B to the first | B | computational basis states, which can be achieved by M = ∏ j = 0 | B | − 1 T j , z j , where T i , j is a transposition gate. It follows directly thatTherefore, we find that M P B M † = ∑ j < | B | | j 〉 〈 j | , from which it follows that the exponential has the formwhere C ≤ | B | P h ( t ) is a low-pass controlled phase shift gate as defined in Fuchs and Bassa (2025). For a general subspace, the overall circuit requires O n | B | CX gates and O n | B | + log ( | B | ) log ( 1 ϵ ) T gates.

M P B M † | j 〉 = M P B | z j 〉 = M | z j 〉 = | j 〉 , for j < | B | , 0 , otherwise.

e i t P B = M † e i t ∑ j < | B | | j 〉 〈 j | M = M † C ≤ | B | P h ( t ) M ,

When the subspace is given by the span of a Pauli X-orbit as defined in Fuchs and Bassa (205), the overall circuit requires only O n ⁡ log ( | B | ) CX gates and O n + log ( 1 ϵ ) T gates. Here, ϵ is a given tolerance for approximating rotational gates. Even though span B might not be a Pauli X-orbit subspace, we can always decompose into a direct sum of Pauli X-orbit subspaces and apply the construction individually on the subspaces of the decomposition. We will therefore here aim to divide the subspaces such that they are Pauli X-orbit subspaces if it leads to an efficient circuit.

An overview of possible encoding techniques is provided in Figure 2. When k is not a power of 2, we must deal with the fact that we have non-trivial equivalence classes clr. There are two ways to deal with this. The first is to directly implement the phase separating Hamiltonian on the full Hilbert space (Fuchs et al., 2021) or restrict the evolution onto the relevant subspace. The main contributions of this study are for the cases when k is not a power of 2. We introduce:

• • A systematic way to implement the phase separating Hamiltonian, resulting in a reduction of the complexity of the resulting circuit using the theorems from Fuchs and Bassa (2025).
• • A method to directly work with a feasible subspace with a suitable state preparation and constrained mixer in Section 4.
• • More balanced sets of equivalent colors, which help improve the resulting cost landscape, in Section 3.

We also employ the Grover mixer to all cases, indicating that the resulting landscape might be favorable. Throughout this study, the notation C l U means an l −controlled U gate. For example, a Toffoli gate is C 2 X, and C P h = C P h ( t ) is the controlled phase shift gate, where we mostly omit the parameter. We will make use of the following notation for multi-controlled unitary (MCU) gateswhere c , t is index control and target qubits, and b specifies the control condition.

C b c U t = ( I c − | b 〉 〈 b | c ) ⊗ I t + | b 〉 〈 b | c ⊗ U t , (3)

2 Binary encodings when k is a power of 2

When k = 2 n k, the equivalence relation for the problem Hamiltonian in Equation 2 becomes trivial—that is, clr = { } ̄ = { ( 0,0 ) , ( 1,1 ) , … , ( k − 1 , k − 1 ) }—and hence

H ̂ e = ∑ i = 0 k − 1 | i 〉 〈 i | ⊗ | i 〉 〈 i | . (4)

By definition, H ̂ e is a projection operator P B of rank k onto the subspace spanned by B = { | j 〉 ⊗ | j 〉 , 0 ≤ j < k }, consisting of all states with identical basis vectors in both registers. We notice that the set B is Pauli X-orbit generated as defined in Fuchs and Bassa (2025) since it can be written asthat is, the orbit of the computational basis state | 0 〉 ⊗ 2 n k under the group action of G n k = ⟨ { X i ⊗ X i } i = 0 n k − 1 ⟩. Here, ⟨ S ⟩ denotes the subgroup generated by a subset S of the Pauli group. To construct the phase separating operator for our concrete case, we follow the proof of Theorem 3 in Fuchs and Bassa (2025) which recursively gives us the following permutation matrix in each step, M j = C 1 j X j + n k, which leaves the all-zero state unchanged and maps the state | j 〉 ⊗ | j 〉 to | j 〉 | 0 〉. Overall, this leads toresulting in the following circuit:

B = G n k | 0 〉 ⊗ 2 n k ,

M P B M † = I n k ⊗ | 0 〉 〈 0 | n k , M = ∏ i = 0 n k − 1 C 1 i X i + n k ,

(5)

The number of controlled gates required for realizing the mixer and phase separating operators are as follows.

• • Realizing e − i t H ̂ e through Equation 5 requires 2 n k C X gates and 1 C n k − 1 P h gate. Alternatively, we can also do a direct decomposition of H ̂ e in the Pauli basis and perform Pauli evolution gates with this. For k = 2,4,8, the first approach needs 2C X, (4C X and 1 C P h) and (6C X and 1C 2 P h), whereas the Pauli evolution needs 2C X, 10C X, and 34C X per gate, respectively. Thus, it is better for these cases to realize the phase separation with the circuit given in Equation 5 and not through Pauli evolution.
• • The X mixer does not require any controlled gates, the Grover mixer needs one C | V | n k − 1 P gate, and the G r o v e r □ V needs | V | C n k − 1 P gates, where the box product is defined in Equation 11.

We numerically test the performance of the resulting QAOA algorithm on the same instances as in Fuchs et al. (2021), given in Supplementary Appendix A. Table 1 shows that the approximation ratios achieved are very good for all cases. An overview of the energy/approximation ratio landscapes are provided in Supplementary Appendix Table A3.

TABLE 1. Approximation ratios achieved for the case when k = 2 n k.

3 Binary encodings for k ≠ 2 n k using the full Hilbert space

When k is not a power of 2, the equivalence relation for the problem Hamiltonian in Equation 2 becomes non-trivial. One way to deal with this is what we will refer to as ≤ k-encoding, where we encode the color k into all states with | i 〉 for k ≤ i ≤ 2 n k − 1. This gives us

clr < k k = { ( k − 1 , k ) , ( k , k + 1 ) , … , ( 2 n k − 2 , 2 n k − 1 ) } ̄ .

Of course, in general there are many ways to define k colors through an equivalence relation clr, which influences the cardinality of the equivalence classes. There is, however, always a way to define it such that the maximum cardinality of all equivalence classes is at most 2. In the following, we denote such a relation as clr bal k. This also influences the rank of the Hamiltonian H ̂ e. In the following, we make a concrete construction of the Hamiltonians for k ∈ { 3,5,6,7 }.

3.1 The case k = 3

For k = 3, clr bal 3 = clr < 3 3 = { ( 2,3 ) } ̄, which means that the three colors are given by [ 0 ] = { 0 } , [ 1 ] = { 1 } , [ 2 ] = { 2,3 }. The subspace of the projector is given by B = { | 0000 〉 , | 0101 〉 , | 1010 〉 , | 1111 〉 , | 1011 〉 , | 1110 〉 }. We can realize the phase separating operator using the low-pass controlled phase shift gate C ≤ 6 P h in the permuted basis, as described in Fuchs and Bassa (2025). However, to reduce the circuit complexity, we can instead divide the subspace in two Pauli X-orbit generated subspaces, B 1 = ⟨ X 1 X 3 ⟩ | 0000 〉 and B 2 = ⟨ X 1 , X 3 ⟩ | 1010 〉, which results in the circuit

3.2 The case k = 5

For k = 5, clr < 5 5 = { ( 4,5,6,7 ) } ̄, which means that the five colors are given by [ 0 ] = { 0 } , [ 1 ] = { 1 } , [ 2 ] = { 2 } , [ 3 ] = { 3 } , [ 4 ] = { 4,5,6,7 }. We can divide B into two Pauli X-orbit generated subspaces. The first subspace containing four states is related to the first four colors | 000 〉 , | 001 〉 , | 010 〉 | 011 〉, forming the subset B 1 = ⟨ X 1 X 4 , X 2 X 5 ⟩ | 000000 〉. The second subspace contains all states related to the last degenerated color | 100 〉 , | 101 〉 , | 110 〉 , | 111 〉, forming B 2 = ⟨ X 1 , X 2 , X 4 , X 5 ⟩ | 100100 〉. The resulting circuit is given bywhich realizes the phase separating unitary with one single- and one triple-controlled phase shift gate.

(6)

Looking at the case for k = 3 and k = 5, it becomes clear that the structure of the circuit can be generalized for clr < k with k = 2 l + 1. The feasible subspace can always be divided into two Pauli X-orbit generated subspaces, B 1 = ⟨ X 1 X n k + 1 , … , X l X n k + l ⟩ | 0 ⋯ 0 〉, related to the first k − 1 color states characterized by bitstrings x = y y, where the first digit of y is always 0. The second subspace related to the degenerate color is given by B 2 = ⟨ X 1 , … , X n k − 1 , X n k + 1 , … , X 2 n k − 1 ⟩ | 10 … 0 〉 | 10 ⋯ 0 〉. From this, we can conclude that the resulting circuit is a generalization of Equation 6, where e i t H 1 consists of the M GHZ circuit where the CX between the first and n k-th qubit is omitted and a phase shift gate the with target on the last qubit controlling the first and last n k (without the last) qubits. The circuit for e i t H 2 is a phase shift gate with control of the first and target on the n k + 1-th qubit.

A second possibility is to encode the problem so that the cardinality of the equivalence classes is minimized. This can, for instance, be achieved by clr bal 5 = { ( 0,1 ) , ( 4,5 ) , ( 6,7 ) } ̄. In this case, the five colors are given by [ 0 ] = { 0,1 } , [ 2 ] = { 2 } , [ 3 ] = { 3 } , [ 4 ] = { 4,5 } , [ 6 ] = { 6,7 } and the according Pauli X-orbit generated subspaces are

B 1 = ⟨ X 0 X 3 , X 1 X 4 , X 2 X 5 ⟩ | 000000 〉 , (7)

B 2 = ⟨ X 0 X 3 , X 2 X 5 ⟩ | 000001 〉 , (8)

B 3 = ⟨ X 2 X 5 ⟩ | 111110 〉 . (9)

The resulting circuit for the phase separating operator iswhere the gates in the gray box cancel to the identity.

(10)

3.3 The case k = 6

For k = 6, we have that clr < 6 6 = { ( 5,6,7 ) } ̄, meaning that the six colors are given by [ 0 ] = { 0 } , [ 1 ] = { 1 } , [ 2 ] = { 2 } , [ 3 ] = { 3 } , [ 4 ] = { 4 } , [ 5 ] = { 5,6,7 }. We can divide B into the following two Pauli X-orbit generated subspaces B 1 = ⟨ X 0 X 3 , X 1 X 4 , X 2 X 5 ⟩ | 000000 〉 , B 2 = ⟨ X 2 X 5 ⟩ | 110111 〉, together with B 3 = { | 110101 〉 , | 110111 〉 , | 111101 〉 , | 111110 〉 }, which cannot be generated by a Pauli X-orbit. The resulting circuit is given by

The circuit for the real time evolution of H 2 contains a Toffoli gate for realizing the basis change since the subspace is not Pauli X-orbit generated. In particular, the circuit for the second term H 2 can be derived considering that if we exchange the state | 111110 〉 and | 111111 〉 using a transposition gate (in this case a 5-controlled not-gate C 5 X), the new set B 2 ̃ = ⟨ X 2 , X 4 ⟩ | 110101 〉 becomes Pauli X-orbit generated. Since all the states in the subset B 2 ∪ B 2 ̃ have the bit value 1 in position 0,1,3,5 we can instead replace the use of C 5 X by a Toffoli gate C C X 2,4 → 5.

In order to encode the problem in a balanced way, we can use clr bal 6 = { ( 0,1 ) , ( 4,5 ) } ̄. Since clr bal 6 ∪ { ( 6,7 ) } ̄ = clr bal 5, we can divide B into the subspace B 1 and B 2 shown in Equation 7; the resulting circuit is shown in Equation 10, but the circuit for H 3 is omitted.

3.4 The case k = 7

For k = 7, clr bal 7 = clr < 7 7 = { ( 6,7 ) } ̄, which means that the seven colors are given by [ 0 ] = { 0 } , … , [ 5 ] = { 5 } , [ 6 ] = { 6,7 }. Since clr bal 7 ∪ { ( 0,1 ) , ( 4,5 ) } ̄ = clr bal 5, we can divide B into the subspace B 1 and B 3 shown in Equation 7, where the resulting circuit is shown in Equation 10, but the circuit for H 2 is omitted. Notice here too that the two adjacent C 2 X 5 gates between the circuits for H 1 and H 3 cancel.

3.5 Resource analysis

When k is not a power of 2, the method presented in [9, Section 3.2.2] is not optimal in terms of resource efficiency; for each edge of the graph, it requires the circuit shown in Equation 5 and a ( a − 1 ) times the circuit shown in Figure 3b, where a = 2 n k − ( k − 1 ). Each of these individual circuits uses four C n k X-gates, and one C 2 P gate and requires the use of two ancillary qubits. Concretely, for each edge, 2,12,6,2,56 , ⋯ of these circuits are needed for k = 3,5,6,7,9 , ⋯, respectively, with the cost shown in Figure 3a. The method derived from the theorem in Fuchs and Bassa (2025) on the other hand, requires much fewer entangling gates and does not require ancilla qubits. For a single edge, the size of the relevant subspace B scales as O ( k 2 ) in the encoding using clr bal k and as O ( k 4 ) in the encoding using clr < k k. This quadratic scaling in the latter case is due to the degeneracy of the highest color level, which leads to ( 2 2 n + 1 − k ) 2 valid computational basis states. From the theorem in Fuchs and Bassa (2025), the overall gate complexity for the two encoding strategies is as follows.

• • Encoding using clr bal k: O ( | E | k 2 ⁡ log 2 ( k ) ) CNOTs and O ( | E | k 2 ⁡ log 2 ( k ) ) + 2 ⁡ log 2 ( k ) log 2 ( 1 / ϵ ) single-qubit rotations.
• • Encoding using clr < k k: O ( | E | k 4 ⁡ log 2 ( k ) ) CNOTs and O ( | E | k 4 ⁡ log 2 ( k ) ) + 4 ⁡ log 2 ( k ) log 2 ( 1 / ϵ ) single-qubit rotations.

Here, we have explicitly constructed circuits for k = 3,5,6,7,9 , … using a decomposition similar to that in Fuchs and Bassa (2025), but with a key optimization: we partitioned subspace | B | into ad hoc sums of Pauli X-orbits. This additional structure further reduces the implementation cost. See Supplementary Appendix Table A3a for a comparison.

4 Binary encodings for k ≠ 2 n k using subspaces

When k is not a power of 2, there is an alternative to encoding the problem in the full Hilbert space as presented in Section 3. Instead, the evolution of the QAOA can be restricted to a suitably chosen subspace spanned by a set B consisting of k computational basis states. Consequently, we need a way to prepare an initial state in a k-dimensional subspace for each vertex of the graph and a mixer constrained to this subspace. We observe thatmeaning we can use the circuit for the power-of-2 case. Overall, this approach shifts complexity from the phase separating Hamiltonian to the mixer.

H P bin ( 2 n k ) span B = H P bin ( k ) ,

4.1 Initial state

For the MAX k-CUT problem, one possibility is to define the subspace for each vertex through B k = { | i 〉 | 0 ≤ i ≤ k − 1 }. Since the feasible bit-strings admit a Cartesian product structure, the feasible subspace becomes a tensor product of the form

B k 1 ⊗ ⋯ ⊗ B k | V | .

An initial state can be prepared as the uniform superposition of all feasible basis states—

This can, in general, be efficiently prepared with a gate complexity and circuit depth of only O log 2 ( k ) (Shukla and Vedula, 2024). One way to realize the initial state for k ∈ 3,5,6,7 is shown in Figures 4a–h.

4.2 Constrained mixer

Given a feasible subspace span B ⊂ H, a mixer U M is then called valid (Hadfield et al., 2019) if it preserves the feasible subspace, that is,and if it provides transitions between all pairs of feasible states, where for each pair of computational basis states | x 〉 , | y 〉 ∈ B there exist β * ∈ R and r ∈ N ∪ { 0 }, such that

U M ( β ) | v 〉 ∈ span B , ∀ | v 〉 ∈ span B , ∀ β ∈ R ,

Apart from the Grover mixer, we consider here constraint-preserving mixers in the stabilizer form (Fuchs and Bassa, 2024), in which case the Hamiltonian can be written aswhere α ∈ { 0,1 } n \ { 0 } n is a multi-index, X ̄ α = X 1 α 1 ⋯ X n α n ∈ { I , X } n \ { I } n, and ∏ V α is a projection onto V α. Furthermore, V α is a subspace fulfilling | x 〉 ∈ V α ⇒ X ̄ α | x 〉 ∈ V α. The free parameter c α ∈ { 0,1 } must be chosen such that we have a valid mixer. Let { S 1 , … , S l } be a minimal generating set of the stabilizer group S = ⟨ S 1 , … , S l ⟩ defining the code subspace C ( S ). We can choose the projection operator to be of the form

H M = ∑ α c α X ̄ α ∏ V α ,

∏ C ( S ) = 1 2 k ∑ S ∈ ⟨ S 1 , … , S k ⟩ S .

For more details, see Fuchs and Bassa (2024). In the following, we will use the notation

X ̄ 〈 S 1 , … , S k 〉 : = 1 2 k ∑ S ∈ 〈 S 1 , … , S k 〉 X ̄ S .

Given the independence of the different color constraints for each vertex of the problem, we can then define the following LX-mixer Hamiltonianwhere the Cartesian or Box product is defined as

H M = G □ | V | = G □ G ⋯ □ G ,

G □ H = G ⊗ I + I ⊗ H . (11)

It can be shown that if G is a valid mixer, H M is constructed in this way (Fuchs and Bassa, 2024). Valid mixers with optimal cost in terms of C X gates are shown in Figure 4 for k ∈ { 3,5,6,7 }. We note that this choice is not unique and that other mixers are possible as well.

5 Simulations

We perform numerical simulations for an unweighted Erdős–Rényi graph and a weighted Barabási–Albert graph with ten vertices (Supplementary Appendix A). Since the case where k is a power of 2 is presented in Section 2, we will focus on evaluating the methods presented in Sections 3 and 4. Using an ideal simulator, we compare the results for the binary encoding with the standard X-mixer and different choices of equivalence relations to encode the colors, and we compare the subspace encoding with different choices of mixers. The resulting energy landscapes are provided in Supplementary Appendix A. As expected, the landscapes are periodic in β when using the X- and Grover-mixer, whereas the landscape associated with the LX-mixer is generally not. The resulting approximation ratios are shown in Table 2. Overall, the subspace-encoding using the G r o v e r □ mixer achieves the highest values for these two graphs, although with only a small distance to the LX-mixer. We can also see that balancing the bin sizes for the different colors has a very positive effect on the approximation ratio when using the full Hilbert space and the X-mixer. The effect of increasing the depth is shown in Table 3, which is exemplified for k = 6. Note that the behavior for k = 3,5,6, and 7 were very similar. Overall, the G r o v e r □ achieved the best convergence for these two graphs, irrespective of whether the full Hilbert space or the subspace method was used.

TABLE 2. Comparison of different encoding schemes when k is not a power of 2. The X-mixer uses the encoding of the full Hilbert space presented in Section 3, whereas the LX- and Grover mixers encode the problem in a subspace as described in Section 4. Approximation ratios achieved for the graphs shown in Supplementary Appendix A for depth p = 1. The light gray color indicates methods using subspaces as described in Section 4, whereas the rest indicates methods using the full Hilbert space as described in Section 3.

TABLE 3. Approximation ratio for k = 6 for the different methods as the depth p is increased, employing the interpolation-based heuristic described in (Zhou et al., 2020) and compared with the Frieze–Jerrum semidefinite programming relaxation (Alan and Jerrum, 1997). The subspace methods constrained to subspaces use dashed lines with circles as makers, and the methods using the full Hilbert space use solid lines with ´´x” as markers.

We note, however, that the averaged approximation ratio achieved should be carefully considered with respect to the required circuit depth. For encoding in the full Hilbert space, we can use the X-mixer, but the phase-separation operator requires a deeper circuit. For encoding into a subspace, we can use the phase-separation operator for the power-of-2 case (leading to a more shallow circuit), but the circuit for the constrained preserving mixer is deeper. An indication of the cost is given in Table 4, where we used the compiler from qiskit, assuming full connectivity. Note that for a sparse graph | E | = O ( | V | ) and for a fully connected graph | E | = Θ ( | V | 2 ). Therefore, for graphs with sufficient connectivity, the subspace encoding uses fewer resources than the encoding into the full Hilbert space.

TABLE 4. Cost in terms of CX gates when using the qiskit compiler. Methods from previous research is marked with light gray background: The line with H P old ( k ) is the Hamiltonian presented in Fuchs et al. (2021), and the H P Pauli ( k ) decomposes the Hamiltonian in the Pauli basis. Terms related to the phase-separating Hamiltonian scale with the number of edges and terms related to the mixer scale with the number of vertices. Notice that by encoding the problem in a specific subspace rather than the entire Hilbert space, the complexity is shifted away from the phase-separating Hamiltonian and instead transferred to the mixer.

6 Conclusion

This study presents advances in encoding the MAX k-CUT problem into qubit systems, with a focus on cases where k is not a power of 2. We present new ways of encoding that significantly reduce the resource requirements compared to previous approaches. In our implementation, we compared two different encodings using the full Hilbert space. Empirically, we observed that the balanced encoding consistently produced more compact circuits and achieved higher approximation ratios across all tested circuit depths and for both graph instances. We believe that this improvement is linked to the structure of the cost Hamiltonian, specifically the reduced degeneracy induced by the balanced encoding, which may lead to a smoother optimization landscape. However, we acknowledge that we do not currently have a theoretical guarantee that the balanced encoding results in fewer barren plateaus than the ≤ k encoding. While the empirical results suggest an improvement in trainability, a rigorous analysis of the gradient landscape remains an open direction for future work. Balanced color sets and constrained mixers demonstrate notable improvements in optimization landscapes and approximation ratios.

While our method is designed for digital quantum architectures, extending it to quantum annealers is possible in principle but practically nontrivial. Quantum annealing hardware is restricted to 2-local Ising Hamiltonians, whereas our encoding yields k-local PUBO terms for k ≥ 3. Mapping these higher-order terms to 2-local form would require ancillary qubits and penalty constraints, introducing significant overhead and embedding complexity (Nagies et al., 2025) or the use of hybrid techniques as exposed in (Wurtz et al., 2024). In the future, we plan to do a careful analysis of which ansatz is preferable when k is not a power of 2, using a suite of graph instances. The analysis should take into account the overall circuit depth, the achieved approximation ratio for increasing depth size, as well as if the landscape has barren plateaus or many “bad” local minima.

Generative AI statement

The authors declare that no Generative AI was used in the creation of this manuscript.

Any alternative text (alt text) provided alongside figures in this article has been generated by Frontiers with the support of artificial intelligence and reasonable efforts have been made to ensure accuracy, including review by the authors wherever possible. If you identify any issues, please contact us.

Publisher’s note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Supplementary material

The Supplementary Material for this article can be found online at: https://www.frontiersin.org/articles/10.3389/frqst.2025.1636042/full#supplementary-material

Supplementary material Supplementary material at the source

Footnotes

Edited by: Jaewoo Joo, University of Portsmouth, United Kingdom

Reviewed by: Saravana Prakash Thirumuruganandham, SIT Health, Ecuador

Bikas K Chakrabarti, Saha Institute of Nuclear Physics (SINP), India